Yet Another 雑記

AtCoder のすすめ

2019/10/28

6 月にちょっとした興味から AtCoder のコンテストに出てみた結果、今なお毎週のコンテストに出来るだけ参加したいと感じる程度には嵌まっている。AtCoder がどういったものであって、どういった点が魅力的なのかを紹介したい。

AtCoder では専門性よりも数理力が問われる

自分がもともと競技プログラミングに対して抱いていたイメージは「データ構造やアルゴリズムの深い知識と実装力が問われる分野」のようなものだった。だとすれば、勿論そういった領域の知見も深められたらいいなとは思うものの、日々の業務に強く関連するようなことが無い限りは、コンテストに出て継続的に学ぶ程のモチベーションは沸かなかった。

しかし、上記の認識は少なくとも AtCoder に関してはズレていたと今は思う。実際にコンテストに出される問題を見てみよう。

https://atcoder.jp/contests/agc036/tasks/agc036_a

https://atcoder.jp/contests/abc132/tasks/abc132_f

専門知識がなくても、少なくとも考察することができそうに思われないだろうか?

これらは恣意的なチョイスではあるけれど、AtCoder における問題の傾向として、「データ構造・アルゴリズムの深い知識と実装が問われる問題」というよりも、「第一に数理的な考察・処理が求められ、補助的に基本的なデータ構造・アルゴリズムの知識やプログラミング力が問われる問題」が多い。

勿論データ構造やアルゴリズムの知識は必要となるのだけれど、初中級レベルでは高度なものは求められない。押さえておくべきそれらの手法・概念は幾つか問題を解けば自然と身に付くようなボリューム感と難度だ。

専門性が問われないことが人を虜にする

高い専門性が問われないため、誰でも参加しやすく、最初から楽しみやすいというのは一つの魅力だ。

しかし、それとは別に「専門性を問わない」ことには強い引力がある。

専門知識が無くとも解ける問題、言い換えると誰でも解けうる問題を確かに解ける人のことを「地頭が良い」と形容することがある。これはどうもその人の基盤となる「賢さ」として認識されている節があり、その粗い評価故に「地頭」「センス」「IQ」等と掴みどころの無い指標が使われている。

専門性や個別具体的な処理能力を問われても「まあその領域は門外漢なので..」と心が動かない人も、漠然とした「賢さ」が問われるとなると興味を持ち、結果を出したくなるのではないだろうか。AtCoder に嵌まってしまう理由の一つにこれがあるのではないかな、と思う。

ところで自分は所謂「地頭」は経験とパターン認識によるものだと考えていて、 AtCoder についてもそれが強く働くと考えている。上位陣は見事な解法を一瞬で思いつくようで、そのあまりの天才的な強さと、それを導き得たのに導けなかった自分の無力さに溜め息が出てしまうけれど、あくまでも圧倒的な鍛錬で得た莫大な解法パターンの引き出しがある故のものだと考えている。

数学力はさほど問われない

AtCoder は競技プログラミングであるのに、それとは別の「数学力」が問われることがある、といった声を見ることがある。最近だと以下の問題が話題になっていた。

https://atcoder.jp/contests/agc039/tasks/agc039_d

https://atcoder.jp/contests/abc144/tasks/abc144_d

前者の解説を見ると確かにこれはわりとキツいなと感じはするのだけれど、この点数の問題はそもそも上位層でないと相手にしない問題なので初中級者にはあまり関係が無い。

後者は参加者の 1/3 以上が解ける点数の問題なのだけれど、これは三角比の知識が無いと厳しそうに思う。とは言え定義を知っていればどうにかなるものであって、応用が求められるわけではないので大きな問題ではない。

ということで確かに数学の知識が必要となることはあるけれど、基本的には定義さえ知っていれば、あるいは知らなくても調べることができれば十分で、そこがボトルネックになることはあまり無い。

ところで個人的には上記のようなものよりも、剰余の性質とか、確率や期待値の性質が重要になる問題の方が高い数学力が求められていることが多いと感じるのだけれど、あまり上記のように取り上げられないので、このあたりは「常識」なのだろうと理解している。

数理力が問われるということ

AtCoder では数理力が問われると前述した。数理力という言葉が適切なのかはわからないが、具体的には、問題を簡単な問題に帰着させるための同値変形であったり、アプローチが正しく答えを導けることの証明みたいなものは、頻繁かつ高いレベルで要求される。

これらは専門知識は必要としないものの、数学の強さとこれらの能力には強い相関がある印象があって、それ故に数学が強い人は有利だろうとは思う。

成績へのインパクトを考慮すると前節よりもこの点の方が遥かに数学強い人が有利となる所以になるのだけれど、如何せん専門知識を要しないポイントなので指摘しづらく、前節の点が取り上げられがちという構図がある。

いずれにしても、再三言っていることではあるけれど、知識で殴るものというよりじっくり考えさせられるようなものが多く、毎度新しい発見があり、味わい深い。

まとめ

AtCoder 、おすすめです。


tsugitta

Yet Another 雑記
Twitter