競技プログラミング初めて１年経ちました

競技プログラミング（競プロ）を初めて１年くらい経ったので、１つの区切りとして競プロについて得られた知見や感想を書いておきます。
強くなる方法とか競プロお役立ちテクニックとかそういう話は一切書いてません。

パソコンのプロじゃなくても出来る

何かいきなり馬鹿みたいな話ですが、競プロはパソコンのプロじゃなくても簡単に参加できます。
競技プログラミングやってる人っていうと、日常的にLinuxとか使っててコマンドプロンプトとかめっちゃ使いこなしているスーパーハッカーみたいなイメージでしたが、私みたいにWindowsしか使えない、マウスが無いとまともに操作できない、プログラミングは大学で習った程度のことしかできずアプリとかも作れない……みたいな人でも何とかできます。サンプルコピペするときにカチッペタッカチッペタッてやるのは何かアホっぽいですがそれでもコンテストに参加していくつかの問題を解くことができます。

pythonで競プロ続けていくのはなかなか厳しい

最初半年ぐらいはpythonでやってたんですが、それからはだいたいD言語でやるようになってしまいました。ひねくれ者だったので「pythonで競プロは厳しい」みたいな風潮を見てもいけるとこまでいってやろうとか思ってましたが……散々言われてたことですが、「やっぱりpythonは遅い」です。経験的に、pythonって反復処理が10^6超えるとTLEするかも？って感じなんですよね。10^7だったら絶対TLEします(pypyで出せるならもうちょっとマシになりますが10^7になると相当不安です)。でも競プロの問題って想定解が10^7とか普通にあって、何なら10^8ってこともありました。Atcoderの簡単な問題やyukicoderでやる分にはpypyで提出したりすることで割といけるのですが、こどふぉとかJOIの過去問とかはどうしてもpythonじゃきついなあっていう場面が結構ありました。あと再帰深さの制限を上げても再帰深さのせいで（？）REしたりしたこともありました。いろいろあって辛くなるのでpythonで競プロをやるのは止めました。

こどふぉに参加すると生活リズムが狂う

日本で流行ってる競プロサイトといえば、一番はAtcoder、二番はCodeforces、三番Topcoderって感じっぽいです。私が初めて「競技プログラミング」という存在を知ったころはTopcoderというサイトしか知らなかったので今もそんな感じでTopcoderが一番栄えてるんだろうな～と思っていたんですが、どうやらそうではないらしいです。

それは置いといてCodeforces、通称こどふぉですがこれはロシアの競プロサイトです。「なんでロシア？」と思いますが、ロシアは競プロが一番強い国らしいです。ここのコンテストにも結構日本人が参加しています。問題文はロシア語ではなく、英語なので何とか読めます。コンテストの質（？）は正直あまりよろしくないというのが競プロ界隈での定評です。サイトが重い・つながらない、ジャッジキューが詰まりすぎ、問題の質も悪い（こどふぉはストーリー付きの問題文であるのでそれが邪魔みたいなのとか、考察が軽く実装が重いみたいな問題は嫌われる傾向にあるからかもしれません。あと想定解が誤解法だったとか）などなど。デメリットは多いですが、それでも世界規模で見ると一番栄えている競プロサイトです。こどふぉはSNS的な側面もあって、コンテストが終わるとフォーラムが賑わうので見ていると面白いです。そういう意味ではAtcoderよりお祭り感があって楽しいです。あとはAtcoderにない特徴的なシステムとして、他人のコードを撃墜できるHackというシステムがあってそれも面白いかもしれません。

そんなわけでこどふぉのコンテストに参加するのはなかなか刺激的で楽しいんですが、大きな欠点としてだいたい日本時間で深夜に行われるというのがあります。通常24:00~26:00くらいでそっからシステムテストが終わるのを待ったり、寝ようと思ってもコンテスト後は目が冴えてしまっているのでうだうだやっていると27時とか28時くらいになってしまいます。なので結構な頻度でこどふぉに参加してしまうと完全に昼夜逆転生活になってしまいます。

全探索すればいい

私が競プロ始めた頃によくあったこととして、問題を解こうとしたときに「賢く解こう」としてしまうということがあったなあと思いました。賢く解こうというか数学的に解こうとか、貪欲で解こうとか、そういう感じです。

例えば、yukicoderの「No.90 品物の並び替え」という問題があります。
https://yukicoder.me/problems/no/90

これはある程度慣れた人なら「N <= 9と制約が小さいから、全ての並び順を全探索するO(N! * N^2)の解法でも十分間に合うな」とぱっと分かる問題です。しかし１年前の私のコードを見ると、「各アイテムをどの位置に挿入したら最も点数が高くなるか？」という怪しい貪欲で解こうとしてWAを食らってます。

このエピソードから得られる教訓として「証明できない貪欲は出来るだけ避けよう」という話もありますが、それ以前の問題として「全ての並び順を調べればいい」という全探索の思考が全く無かったからこのようなコードになってしまったのだと思います。

全探索っていうと何となく「頭の悪い解法、非効率的で競プロには向かない」みたいな先入観があったのですが、全然そんなことは無くて基本中の基本でとっても大事なので全探索の心は常に持っておきたいなと思いました。

まとめ

結構飽き症なので競プロ始めた頃はすぐ飽きるかな～と思ってましたが、意外と１年くらい続きました。（２ヶ月くらい飽きてやってない時期ありますが）
競プロって見た目は地味ですが、多種多様な問題が出されるので「またこの問題か……」みたいなのがあんまり無くて毎回凄く考えさせられます。面白いです。パズルとか考えるゲームが好きな人にはおすすめです。