Haskell / AtCoder 緑到達

Haskell で AtCoder を始めて 11 ヶ月、レーティング 800 を超えました！

背景

AtCoder を始める以前、自分の実力はレーティング『緑』に匹敵すると思っていました。実際に取り組んでみると、レーティング『灰』の日々が続きます。

さらに周りを見回すと、僕より遥かにナードな Haskeller が目に入り、アイデンティティが崩壊します。プログラミングができずナードでもないなんて、僕は一体……

やがて鉄則本が登場し、入茶できました (入茶記事) 。競プロはアルゴリズムの盆栽であると捉え直すことで、競プロ自体にもモチベーションが湧きました。

手続型 Haskell の使用機会が増えて来ました。ネストが深くなりがちで、可読性とパフォーマンスの両立は厳しいです。 Haskell に continue や return が無いのが原因だと思います。

久しぶりに Rust を書くと、最強のモナドが ON になっているようなもので、全く抵抗無くコードを書けました。全く抵抗無く 5 重ネストを書いた時には愕然としました。

何かを手に入れるということは、何かを失うことなのかもしれない。俺たちの盆栽はこれからだ……！

手続型のコードを削除することです。

AtCoder 界隈では『典型』という言葉が頻出します。この問題は典型、この解法は典型、この考察は典型……。振り返ると、むしろ典型ではない問題を知りません。

おそらく過去問と類題はすべて『典型』です。典型ができたらとっくに水色コーダーになっていますよ！　典型をこそやっていきます。

AtCoder プレイヤーの実力は Chokudai さんのブログで語られています。主観的には以下となります:

『校内』は Haskller のレーティングからイメージしています。緑後半の Haskeller たちが偏差値 65 くらいのイメージです。

ふぉっふぉっふぉ

僕の Haskell は競プロ専用であり、非常に限定されたサブセットです。新しい Haskell を人から吸収すべきだと思いますが、今のところ失敗に終わっています。

リスト達人 (緑後半の人たち)
Richard Bird の系譜です。強い。この手のコードは頑張れば読めますが、実際真似すると TLE しがちです。難しい。
手続型 Haskell でぶっち切りの優勝 (レックウザ)
由来から謎です。どう頑張っても読めません。やがて Haskell は AtCoder で 2 番目に速い言語だったことに気付き天啓を受けます。 Haskell は AtCoder ガチ言語だったかもしれない。

Haskell は競プロ (アルゴリズム) 限定だと減点要素が見つかりません。ライブラリも優秀ですし、水色までは全く障害の無い言語だと思います。

ユーザが使いこなせるかは別の問題ですが、ナードにとって Haskell はハンディにならないでしょう。だから半年灰色だったのは純粋な実力不足なのだ……！

AtCoder で 1,000 問解けば、水色コーダーになれると言われています。根拠は解いた問題数とレーティングの統計です。そうか、 1,000 問解けば良かったのか！

でも 1,000 問は厳し過ぎませんか…… (´･_･`)

これからは水 diff を 100 問解いたら水色コーダーになれることにします。このシステムだと、僕は 3 ヶ月以内に水色コーダーになれるのでした。願掛けシステムに採用！

2023 年の AtCoder 言語環境更新がやって来ます！　Rust, Haskell, Common Lisp や OCaml のバージョンアップが入り、 V, Zig など新規言語も投入されます。

最大の注目株は Emacs Lisp です。他の言語が次々に exit, return する中、一人だけ kill-emacs してプロセスを終了します。この奇行、見逃せない。

PAST (アルゴリズム実技検定) 上級を目指して 6 月に受験してみます。

これまでの競プロ経験では、リスト・配列・木しか出て来ませんでした。もっと魔法的な何かがあるのではないかと思っています。

『高度典型』には『Mo』『HL 分解』など未知のアルゴリズムが登場するそうです。ここまで来ればきっと魔法的なので楽しみにしています。

連休はビームを打とうと思います。もとい、『ビームサーチ』『焼きなまし法』を始めとした『ヒューリスティック』的技法に取り組んでみたいと思います。

ヒューリスティックは今でも十分魔法的に見えます。例えば巡回セールスマン問題にいい感じの解を出したりできるようになるのか……！　期待です。

今回のコンテストでも全探索が解けませんでした。半年間の灰色コーダーは伊達じゃないのだ……！

緑になったのでエアロバイクを買います。