目次
この記事は7分で読めます。
はじめに
この記事の目的
AtCoderという競技プログラミングサイトで緑色のランク（上位16%相当）に到達したので、どのような取り組みをしたのかを紹介します。
参考）AtCoderのレーティングについて
対象読者
- AtCoderで色変したい人
- プログラミングが上達したい人
自己紹介
- 職業
- IT系
- 主に上流工程を担当しており、仕事でコーディングすることはあまりない
- AtCoder歴
- 初参加は2023年7月
- レート200程度で放置し、2024年4月下旬から再開
- 数学やITに関しての背景
- 東工大（非情報系・非数学系）出身
- 基本情報技術者取得済み
- 2024年4月に再開するまではif-for文が書ける程度
- 累積和やBFS・DFSなどの基本的なアルゴリズムも再開後に習得
入緑までの振り返り
レート推移
AC数やStreak等のデータ
精進記録
灰色時代（2023年7月〜2024年6月）
やったこと
- ABCに参加するだけ（2023年）
- 競技アルゴリズムの鉄則本A問題埋め（2024年4月以降）
2023年は、標準入出力、if文・for文などの基礎文法を学ぶためにコンテスト参加していました。
当時は二分探索や累積和などの典型的なアルゴリズムをほぼ知らず、毎回B問題まで40分くらいかけて解き、C問題以降は全くと言っていいほど手がつけられませんでした。
2024年4月までずっとプログラミングは放置していましたが、突発的に競プロモチベが上がり、鉄則本でアルゴリズムを体系的に学ぶことにしました。
勉強時間や勉強内容としては、毎日平均2時間程度プログラミングの勉強に充て、2ヶ月ほどでA01~A77を2,3回ずつ解いています。ここで二分探索や累積和、グラフなどの典型アルゴリズムのエッセンスは網羅的に身につけることができたと感じており、鉄則本には非常に感謝しています。
所感ですが、灰→茶の色変についてはC問題を安定して解くことができるかどうかが鍵だと思います。
C問題以降は計算量を意識しないと解けないような問題が多く出題されるので、まずは計算量を落とすための初歩的なアルゴリズムである二分探索や累積和をしっかり使えるようになることをおすすめします。
一応セグ木や最大フロー最小カットも鉄則本で学習しましたが、そういった高度典型の問題は基本水diff以上になるので、灰→茶の色変には不要な知識かなと感じました。
茶色時代（2023年6月〜2024年10月）
やったこと
- ABCに参加、コンテスト中に解けなかった問題は水diffまで解説AC
- 競技アルゴリズムの鉄則本のB問題埋め
- ABCの過去問埋め（50回分くらい、灰〜水diffまで）
茶色になってからは平日1~2時間程度、休日3~4時間程度の学習を継続していました。
社会人としては時間を割けている方だとは思いますが、自分含め社会人は学生さんと比べあまり多くの時間を取れないので、効率的に学習する必要があります。
そこで、私が茶色から緑色になるまでの期間で取り組んでいたことを、主に灰色〜茶色の社会人コーダーの方に少しでも参考になればと思い共有します。
そもそも、AtCoderで高いレートを取るための方法は「多く問題を解く」か「早く問題を解く」の２つしかありません。
私はこの二つの力を伸ばすために、以下のように課題を分解して対策を講じています。
1. 多く問題を解く上での課題
2. 早く問題を解く上での課題
- 解法が見えるまでに時間をかけすぎている
- 実装方法を考えるのに時間をかけすぎている
- 間違った実装方法であることに気づかず最後までコーディングしてしまう
- 再利用できるライブラリを持っていない
- 実装時に多くのバグを埋めてしまう
- バグ取りに時間をかけすぎている
※あくまで筆者の整理であり、異論は認めます。
1-1. 想定解のアルゴリズムを知らない
二分探索を利用しないと解けない問題は、二分探索を知らないと解けません。
コンテスト中に調べたり、自力で生み出すことも可能ですが、アルゴリズムを知らない時点で大きく不利になってしまいます。
ARCやAGCならいざ知らず、ABCは基本的には典型的なアルゴリズムしか出てきませんので、まずは鉄則本やけんちょん本、蟻本等でしらみつぶしに典型アルゴリズムを習得しておくというのが対策の一つになります。
なお、ABCで知らないアルゴリズムが出たら都度覚えていくのも普通にありです。
ただ本番はなるべく覚えたアルゴリズムを応用できるかどうかの確認の場としておきたいのと、本番で玉砕してから覚えるよりは解ける状態で臨んだ方がレート上昇も見込めること、また本番で知らないアルゴリズムが出て萎えるのを避けたいというモチベ維持の面からも、あらかじめ典型は網羅しておくのが個人的にはおすすめです。
-
まとめ
- 鉄則本などで典型アルゴリズムをあらかじめ覚えておく
- それでも学習が漏れたアルゴリズムは本番で都度覚えていく
1-2. 想定解のアルゴリズムは知っているが、解法が見えない
アルゴリズムを覚えたての時や、解法を見つけるのが難しい難問に当たるとこうなりがちだと思います。
筆者自身、まだまだ暖色の問題とか全くわからないので、今回は「考察は簡単（数学要素が薄いorひらめき要素が少ない）なのにアルゴリズムの応用力が足りないせいで解けない」というパターンに絞って話をさせていただきます。
そもそもここで言うアルゴリズムの応用力とは、「問題や制約を見て、どのアルゴリズムを使えば良いかわかる」程度のふわっとした定義です。
応用力を身につける方法としては、量をこなして慣れるというのと、アルゴリズムの理解度を上げるという２要素があるかなと思います。
前者については、量をこなしていくうちに問題を読んだ時どのアルゴリズムを使えばいいかが雰囲気でわかるようになってきます。
後者については、例えば「制約が$N≦10^5$なので$O(NlogN)$までなら大丈夫だから二分探索が使えるな」とか、「$N$人を$A$,$B$の2グループに分ける方法は$2^N$通りしかなく、$A$グループを0、$B$グループを1とすれば$N$桁の2進数表現で全列挙できるからbit全探索でいけるな」など、アルゴリズムごとの特徴を生かすような使い方を理解しておくとかなり問題が解きやすくなります。そのため、わからない問題が出たら都度解説を読んで、どうしてそのアルゴリズムの使い方で解けるのかをちゃんと理解できるまで復習することが大切だと思います。
また、この両方の要素を効率的に伸ばしていくために、ただ闇雲にやるのではなく、自分の実力より少し上か目標としている色のレベルの問題をうまく選んで解くのがよいです。
私は水色を目標に始めたので、割と初期からChatGPTを駆使しながら水色までの問題は全てACするようにしています。
※ただし1時間以上考えて全くわからない問題や解説を読んでも理解するのに2時間以上時間がかかってしまう問題を粘っても効率はあまり良くありません。自分の実力やどれだけ時間をかける価値があるのかを考える必要があります。
↓水色までは全てACするようにしている図
下図、筆者の過去の色別AC数を見ての通り、水色まで満遍なく解いています。
私見ですが、緑〜水の問題は灰〜茶の問題をモジュール単位で組み合わせたような問題が多く、緑〜水の問題を1問解くのと灰〜茶の問題を2~3問解くのとでは同じくらいの演習量に相当するというのと、難しい問題の解法の考え方を身につけることができるという二重の意味で、少し背伸びして水色まで解いて良かったと思っています。
-
まとめ
- 自分より少し上〜目標にしたいレベルの問題をより多く解く
- 解けなかった問題は解説ACできちんと解法を理解する
1-3. 解法は見えるが、実装方法がわからない
あるアルゴリズムを使えば解けるということがイメージでわかったとしても、具体的にコーディングして解を導く方法がわからなければACできません。
正直なところ、実装方法は習うより慣れろな気がします。理屈を学ぶより自分の手を動かして沢山コードを書いていくのが良いです。
ABCの灰〜茶あたりの問題は「このアルゴリズムを正しく実装できますか？」というノリの問題が多いので、実装力が不安な人はここを重点的に解くのがおすすめです。
また、次のステップとして複数のアルゴリズムを組み合わせて書く問題があります。
例えば「尺取り法+imos法」や「セグ木+座標圧縮」がありますが、単体だと書けるのに組み合わせるならどのようにコーディングすればよいかは最初は結構難しいです。
ABCの緑〜水の問題は典型アルゴリズムの組み合わせで解けるような問題が多いので、単体としてのアルゴリズムはある程度わかってきて、上手く組み合わせるのが苦手な人はこの辺の問題を解くのがおすすめです。
-
まとめ
- アルゴリズム単体のコーディングが不安な方は灰〜茶くらいの問題を解く
- アルゴリズムを組み合わせるコーディングが不安な方は緑〜水くらいの問題を解く
2-1. 解法が見えるまでに時間をかけすぎている
次に、いかに早く問題を早く解くかですが、こちらは意識や経験がメインな話になるのでサクサクいきます。
解法が見えるまでの時間は個人の数学力や考察力などの地頭も寄与しますが、ABCの序中盤の問題は基本的に典型ばかりなので、どれだけ類題を見たことがあるかというのが大きいと思います。初見ではどうしても時間を食ってしまうので、過去問を沢山解いて解法がすぐピンと来るようになっておいた方が良いです。
緑色を目指すのであれば灰くらいの問題なら一瞬で解法が見えるくらい解き慣れているとgoodです。
余談ですが、私は最近黄色以上の問題の解説もチラ見して解法を雰囲気だけでも掴むようにしてます。今すぐにそれが生きる気はあまりしないのですが、知識の引き出しを増やしておくという意味では良いかもしれません。
-
まとめ
- 過去問を多く解いて初見問題を減らす
2-2. 実装方法を考えるのに時間をかけすぎている
1-3.と関連しますが、まずアルゴリズム単体の実装方法があまり身についておらず時間がかかるようでしたら、簡単目な類似の問題を沢山解いて実装方法を定着させたほうがよいです。
また、アルゴリズムを組み合わせる問題での実装方法を考える際に時間がかかる方も問題演習量が不足しているので量をこなした方がいいと思います。
かく言う私もまだまだ知らない組み合わせ方が多いので緑以上の問題を沢山解くようにしています。
-
まとめ
- 過去問を多く解いて実装量を増やす
2-3. 間違った実装方法であることに気づかず最後までコーディングしてしまう
問題を誤読したり、証明をサボって嘘貪欲を書いたりして結局ACできなかったというのは競プロerあるあるなんじゃないかなと思います。
微修正なら少しのダメージで済みますが、根本的に利用するアルゴリズムが違ったりすると一からコーディングし直しとなるので大幅なタイムロスとなります！
それを避けるために重要なのは、本当にこの解法で正しいのかを頭の中で証明すること、また制約をきちんと読んで計算量が絶対に間に合うのかどうかコーディングする前に検証しておくことだと考えています。
これはどちらかというと意識を体に染み込ませるようなものだと思うので、日頃から意識して問題を解くようにしましょう。
-
まとめ
- 手を動かす前に証明や制約に間に合うかどうかを考える意識を持つ
2-4. 再利用できるライブラリを持っていない
AtCoderではネットやライブラリの利用は制限されていないので、それをうまく活用できた人が勝ちです。
ダイクストラ法やUnion-Findなどソラで書ける人はかっこいいと思いますが、そのような典型アルゴリズムはコンテスト前に書いておいて本番はコピペできるようにした方が時間を大幅に節約できます。
再利用できそうなアルゴリズムに出会ったら、都度ライブラリにしておくよう心がけると良いと思います。なお、鉄則本を埋める中でライブラリをある程度網羅して作れたのはかなり良かったです。
-
まとめ
- 典型アルゴリズムは出会った都度ライブラリ化しておく
2-5. 実装時に多くのバグを埋めてしまう
書いたコードにバグがなく、WAやTLEせずに一発でACできるかどうかがこの競技においては重要です。
最初からバグを埋めないためには、自分がどんなバグを埋めやすいのかの傾向に気をつけながらコーディングする必要があります。
ありがちなバグは下記のE8さんの記事に網羅されていますので、そちらを参照ください！
-
まとめ
- 自分が埋め込みやすいバグを意識しながらコーディングする
2-6. バグ取りに時間をかけすぎている
私の今の課題なのであまり大層なことは言えませんが、私が30分バグで悩んでいたところ強い人に聞いてみると一瞬で解決できたことがあります。
多分、どこにバグがあるのか大体あたりをつけながらコードを読む力が備わっているのだと推測します。
私見ですが、バグ取りの力を伸ばすためには、問題演習をたくさんやりバグ取りを経験した回数が大事なのではないかと思います。実際に、最初期に比べると私もバグを取るスピードが速くなっています。
もし特別に意識している方法がある方がいればむしろ教えて欲しいです。
-
まとめ
- 演習量を増やし多くバグ取りを経験する
以上1-1.〜2-6.までの観点を踏まえ、メインは過去問として、解く順番や問題を解く上での意識を考えながら取り組んでいたって感じです。
今後の目標
次の目標ですが、1年程度で水色を目指してまったりとやっていきたいです。
今は水色までの問題を解いていますが、今後は青下位の問題にも手をつけていきます。
最後に、これまでに役に立ったツールを紹介します。
- AtCoder Type Checker
自分が「多く解くタイプ」か「早く解くタイプ」かを統計的に教えてくれるサイトです。
筆者は下図の通り、グラフの上の方におり比較的「多く解くタイプ」だとわかるので、早解きを伸ばせばレートが上がりやすいというのが一目でわかります。
- AtCoder Replay
コンテスト中のレート推移がわかります。他のユーザーと比べて早く解けてるのかどうかが一目でわかるので良いです。
- Graph Graph
グラフを可視化してくれます。サンプルケースのグラフを描画してもらい考察に役立ちました。
もし他にもあれば追加します。
少し長くなってしまいましたが、最後まで読んでくださりありがとうございました。