AtCoder Beginner Contest 223
ABC223でついに入緑を果たしました。39回目のratedコン参加でした。D問題までの4完でしたが、実際のところDはトポロジカルソートを使うまでは思い付いたものの複数パターンあるソート結果から辞書順最小を導出する方法が思いつきませんでした。んでヒントないかなーとググったらドンピシャの記事を発見してしまいACしたので、完全に実力とは言い難いです。どちらかと言えばC問題まで15分弱で解けたことの方が嬉しかったですね。今後は安定してD問題が解けるよう精進を続けていきたいです。
以下では、入緑の記念にこれまでの振り返りと所感を述べたいと思います。
精進の記録
最初に触れておくと僕は大学時代情報系専攻でした。めっちゃハンデをもらってるのになんだこれは…たまげたなあ…という気持ちでいっぱいです。速攻でレートを上げてる方たちは本当にすごいと思います。
本題の精進記録ですが、僕は最初AtCoderではなくAOJから競プロデビューしました。理由はなんとなくデザインが好きだったのと、コースリストで様々なアルゴリズムを勉強できたからです。そしてAOJでPyPyが使えないことにキレた僕は速攻でAtCoderに鞍替えし、Codeforces、yukicoderにもたまに出るようになりました。AtCoder対策という意味では効率が落ちた気はしますが、AtCoderの問題にマンネリを感じた時にAOJのチャレンジ問題(JOIやICPCの過去問)とかに取り組むと、趣が違って良い気分転換になりました。AOJやyukicoderの、問題を解けば解くほどレートが上がっていくシステムも努力の数値化という点でモチベーションになって良かったですね。
ただいつからか「AtCoderのレートを上げたい！」という欲望に支配されて無事闇堕ちし、AtCoder ProblemsでABCのC、D問題(茶～緑diffメイン)や競プロ典型90問の☆2～4を解くようになりました。この過程でABCのC問題まではほぼ確実に解けるようになりました。Shapes？知らない子ですね。
入緑に役立ったと思うこと
詳細は各項で述べますが、僕はどちらかと言えば純粋なアルゴリズム力以外の部分(快適なコーディング環境整備、検索力)でレートを底上げしてると思います。それ自体は現実世界での問題解決にも応用が効く能力だと思うのですが、競技プログラミングという種目で純粋に測りたい能力からは外れている気がしています。
精進
それはそうですね。何より大事です。最近ではABCのC問題で基本的なDPや座標圧縮が出たりと、教育コンテンツの充実に伴い問われるアルゴリズムの多様化が進んでいるように感じます。対策として、競プロ典型90問の☆2～4埋めからのABCのC、D問題(茶～緑diffメイン)演習が良いかと思います。補助的にAOJのコースリストでアルゴリズムを学ぶのもいいと思います。分野別 初中級者が解くべき過去問精選 100 問で自分の弱点分野を補強するのも良さそうです。
既に多くの方が言及されていますが、僕の感覚だと入緑するために習得した方がいいと思うアルゴリズムやデータ構造は以下です。
- 習得しておきたい
⇒全探索、bit全探索、順列/組合わせ全列挙、BFS/DFS(グラフ、木に関する知識もセット)、二分探索、優先度付きキュー(heapq)、両端キュー(deque)、連想配列(dict)、貪欲法、累積和、素数判定、エラトステネスの篩、約数全列挙、最大公約数、最小公倍数、基本的な動的計画法(EDPCのA～F等) - できれば習得
⇒しゃくとり法、いもす法、座標圧縮、平衡二分探索木、Union-Find、ダイクストラ法、ワーシャル・フロイド法、発展的な動的計画法(累積和DPとか)
実際に使ったことがなくても、①どういう条件下で②どれぐらいの計算量で③何ができるアルゴリズムかを知っておくだけでもコンテスト中に調べて適用できる可能性が増すと思います。
※余談ですが数学力に自信がある場合はARCのA、B問題とかが予備知識無しで解ける算数パズル多めでレートを伸ばしやすそうな気がしてます(僕は無理です！)。
コーディング環境の改善
競プロ関係メモの記事でも触れてますが、競プロにハマり始めたら自分のPCに快適なコーディング環境を整備するのは優先度高めで取り組んでいいと個人的には思っています。コンテスト中のコーディング速度&精度向上だけでなく普段の精進もやりやすくなるからです。過去に自分が書いたコードの再利用性も高まります。
僕はVSCodeとonline-judge-toolsを併用して、サンプルケースのダウンロード～テストやコードの提出をTASK RUNNER(画像左下ペイン)で1クリックでできるようにしています。最近はonline-judge-tools/template-generatorによるランダムテスト機能を覚えて、数ケースだけWAが取れない…といった場合にもランダムなサンプルケースを増やしてデバッグできるようになり大層助かっております。
スニペット機能もとても便利です。上の画像はABC223のB問題のコードですが、文字列のシフト処理も予めスニペット登録しておけば呼び出すだけになります。基数変換(10進↔n進)とかのたまに出てくる実装がめんどいやつらもとりあえず登録しておくと時短＋余計なバグの埋め込み防止で一石二鳥です。AtCoderのレーティングシステムでは早解きがパフォーマンス向上に大きく寄与するので、「解ける問題をノーペナで早く解く」というのもレートを上げる際に重要かと思います。仮にスニペットまでいかなくとも、例えばテキストファイルによく使う関数をメモっとくとかそれをコードテンプレートにするだけでも十分効果があると思います。
参考までに、僕の競プロ用VSCode設定やスニペットを格納したgithubリンクはこちらです。
検索力
これに関しては自分の中でも良心の呵責に揺れている部分ですが、例えば「大方針は思いついて適用するアルゴリズムが分かったけど具体的な実装が思いつかねぇ～」といった場合にGoogle先生に質問すると、たまにまんま答えが返ってきたりします。経験上日本語のサイトで見つからなくても英語のサイトも含めると見つかることが多いです。エンジニアとして英語での検索力は重要な気がしますが、競プロという文脈だとどうなのか。
ヒントを組み合わせて解けたならいいんですが、まんまコピペだと「すまぬ…すまぬ…」という気分になります。ちなみに僕は入茶の時も入緑の時も検索して見つけたコードでACしてしまいました。そういう運命なのかもしれません。まぁ実力以外でレートが上がっても実力でレートが下がるからいいか！(思考放棄)
所感
ここからは競プロ関連で最近思うことです。
競プロerのレベルについて
目に見える範囲のアクティブユーザに関して言うと尋常じゃない集団だと思います(いろんな意味で)。
つよつよ大学生erや将来つよつよ大学に行くであろう中高生erが大量にいて驚きますし、社会人erさんも強い方が多いです。以前どこかで「競プロ界隈にいると灘、開成、筑駒生が珍しいと思えなくなる」みたいなツイートも見た気がします。ツイッターを始めた当初は「過言やろ」と思ってましたが、最近「過言じゃなかったわ」と認識を改めました。
冷静に考えて中学生でとかが入った問題文を読みこなしてる時点で異常ですし、時々変なところに異世界転生したような気持ちになります。どうせなら「この問題はでしか解けないはず！！何をしたんだ！？」「何って…累積和を求めただけだが？」ぐらいの異世界が良いです。
そんな強者が目立つ世界故に新規参入者の心理的ハードルは高くなりがちに思えますが、最近登場したアルゴ式がうまく架け橋となって広くプログラミングの普及に繋がれば素敵やなぁ、と思います。
競プロの持つ魔力について
競プロは中毒性が高いと思います。気にしまいと思ってもレートの増減に一喜一憂してしまうからです。僕が競プロを始めた当初の目的は、実生活で使われているアルゴリズムを学びたいだとかじっくり問題を考えて脳トレしたいというものでしたが、いつの間にやら「C問題を何分で解けるか」と「D問題まで解けるか」しか考えられないレートの奴隷と化していました。
レートの魔力は多くの人を虜にするようで、上がらないレートに苦しみ退会される方も出る一方、「はいクソー 二度とやらんわこんなクソゲー」「…スッ」の流れも時々見かけたりと、なんだかんだ続けちゃうコンテンツだよなぁと感じています。個人的に「競プロ」はレジリエンスを学ぶ実践教材としても良い気がしています。ガクッとレートが落ちるとやっぱりショックですが、結果は覆りませんからね…僕はレートが冷えた時のネタツイを妄想したりして、「次ガッツリ冷えたらこいつを投稿するチャンスやな」みたいに捉えたりしています。
関係ないですがアンガーマネジメントの実践教材としては「スプラトゥーン」が僕の中で最高峰に位置付けられています。ガチマをイライラせずにプレイできる人はもはや人の域を脱してると思います。
今後の目標
緑色タッチの目標は達成したので、今後はひとまず緑維持を目標に競プロを続けていきたいと思います。長期的には1年後に入水できてたら理想的ですが、それまで競プロを続けられていたらそれだけでも十分ですね。
あとは当初の目的に立ち返って、のんびりといろんなアルゴリズムを学びたいです。特に文字列アルゴリズムが気になっています。
以上です。