競プロ入門

競プロといえばということで、AtCoderを始めてみました。

適当に動くものであれば作ることができるようになってきましたが、自分が書いたコードを見るとなんともダサい＆計算量が増えると設計変えるorクエリ変える以外取れる手段がなく、アルゴリズムで解決しようとしても太刀打ちしようがないという状況だったので、少しずつアルゴリズム力を鍛えようと思って始めました。

また、ちょうど大学の授業でもアルゴリズムに関する話題が増えてきていたところだったので、その予習復習兼ねてという意味合いもあります。

始めてみて

3回ほどコンテストに出てみましたが、まず感想としてむずい。。。

ABCのA,Bは必ず解けて、Cはたまに解けない。解けるときにはDまでが限界でパワープレーになることもある。そしてその先は一切解けない。というのが自分の現状です。現状色は灰色。

そのためまずは基礎から叩き込むために、問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本を極めていく作戦を取ることにしました。（著者が2000年台生まれってところにもめちゃくちゃ刺激を受けますね。。。！精進せねば）

始めた感想としては、全然知らなかったアルゴリズムばかりが登場し、確かに言われてみれば分かるけど、知らない状態で時間内に１から考えてその解き方は自分ではできないなーという感想です。

まだ2割もできていないのですが、久しぶりに高校のFocus Goldを解いている時のような懐かしい気分になっています。もしこの感覚が正しくて、高校数学と同じようなものだとすると、やりこんでいる期間はめちゃくちゃ解けるようになるはずだけれども、数年放置すると解き方をほとんど忘れてしまい、肌感を取り戻すためにはまた触り直す必要があるなーという感触です。今センターを解いたら何点取れるのか想像できません。少なくとも9割とかは取れなさそう。

目標

こんな感じでふわっと進めていても、中々進まなさそうなので、目標を決めようかと思います。

chokudaiさんのブログを参考にして、2022年終わりに水色を目掛けることができるように頑張っていきたいと思います。最低緑は必達でいきたいところです。

AtCoder（競技プログラミング）の色・ランクと実力評価、問題例 - chokudaiのブログ

コード

AtCoderにはPythonで出ているのですが、本の練習問題はTypeScriptで解いています。

https://github.com/shogo-nakano-desu/math-and-algorithm-ts

Pythonの方が楽なはずですが、TypeScriptでのコーディング力を鍛えたいという理由でTypeScriptにしてみました。実際にはアルゴリズムを考える方が難しくて、僕レベルぐらいであればTypeScriptでもPythonでも大差ないと思うのでまあどっちでもいいでしょう。 TypeScriptで本の練習問題を全部解いたリポジトリは見つけられていないので、完成したら誰かの役に立てばいいなーとも思っています。

また進捗があったら報告できればと思います。