AtCoder赤の自分が考える効率の良い練習法を紹介します。
効率の良い、といっても決して「楽な方法」ではないことはあらかじめ申し上げておきます。
私はAtCoderとProjectEulerぐらいしかやっていないので以下ではAtCoderの問題を使った方法を紹介しますが、別のサイトを使用する場合でも基本的に考えは変わりません。
無駄に長くなったので急いでいる人は最後のまとめだけ読んでください。
解く問題を選ぶ
AtCoder Problemsを利用して適当に問題を選びます。
このときなるべく機械的な方法で問題を選んだほうが良いです。(ABCの青diff以下をを新しい順に埋める、Recommendationで1番目に出てきたものを解く、等)
なぜそうするのかというと、苦手な種類の問題を避ける言い訳を作らないようにするためです。
得意を伸ばすよりも苦手をなくすことのほうが実力は上がりやすいです。 *1
加えて、問題の解法を知らないまっさらな状態で問題に取り組める利点もあります。
ただし、解説AC前提で自分の実力を大幅に超えた問題に取り組むのはあまりおすすめしません。*2
1問の解説を理解するための壁が多すぎると、内容を追うだけになり、どこが重要なのかが不明瞭になるからです。
1問につき1つのテクニックを覚える・復習する、という感覚で取り組めるぐらいの難易度帯にとどめておくのがいいでしょう。
問題を解く
選んだ問題をコンテスト時と同様に解いてみます。
本番のコンテスト時と違って時間のプレッシャーがないので、やや丁寧目に取り組むのがよいでしょう。(解法の証明をしてから実装する、提出前にコーナーケースを確認する、綺麗な実装を心がける、等)
普段から丁寧に解く癖をつけておくと、コンテスト時の焦りの中でもミスに気づきやすくなります。
自力で解けた場合
おめでとうございます。早く次の問題にいきたいところですが、以下の点を確認しましょう。
- 解説・別解を読む。
自分の解法よりもずっと簡潔な想定解があるかもしれません。ただし、「レベルの高すぎるユーザー解説」は適当に流してかまいません。 - 実装や場合分けで苦労した部分は他の人の実装を見てみる。
たとえ自力でACしたとしても、面倒な実装方針を選んでしまっていた、というのは十分反省点たりえます。
公式解説の実装例、もしくは「同じ言語+提出が早い順」で何個かチェックして読みやすいものをピックアップすれば十分でしょう。
解けない場合
諦めて解説を開きます。
どれぐらい考えてから解説を見るのが良いか？という所が悩ましいですが、私は「もう何も思いつかないだろうと思ったら」解説を開きます。時間にすると大体長くて1時間ぐらいで、本当になんの手立てもなければ30分以内に開くこともよくあります。
個人的な感覚ですが、集中力が持続している間に解説を見てしまったほうがより記憶に定着するような気もしています。
解けなかった問題の反省
解説を読むときは「どこまで解けて、どこでつまづいたか」をチェックしましょう。 例えば「DPで解くという予想は立ったが、何をキーに置けばよいかわからなかった」「決め打ち二分探索にする発想がまったく頭になかった」「式変形を間違えていてサンプルが合わなかったため、正しい解法なのに諦めてしまった」など、自分が解けなかった理由を言語化して明確にすることが重要です。
ただ、ここで「自分が全く知らないテクニックだった」という場合はあまり悲観する必要がありません。知らないものはどうしようもないので、覚えるだけです。
むしろ反省すべきなのは「過去に見たテクニックが思い出せなかった」「過去の自分と同じミスをした」という場合です。テクニックが使える問題の特徴やミスの原因を必ず明確にしておきましょう。
自分はこのような反省すべき問題を記事にまとめて、Ratedの直前に見返していました。
当然ですが、解説を読むだけでなく必ず実装・提出してACを得ておきましょう。
方針だけ理解したつもりになって重要な部分を見落としている危険があるためです。
苦手な問題を見返す
先ほど述べましたが、自分は解けなかった問題をメモにまとめて定期的に見返していました。
まず問題文を読んで、解法のざっくりとした流れが即座に頭に浮かぶかを確認します。基本的に「もう一度解く」ということはしません。
一度解いた問題なので解法はすぐに思い出せなければなりません。思い出せないようであれば再び解説を読む、もしくは自分のACコードを見るなどして解法を再確認します。
とはいえここには時間をかけず、短いスパンで全体を一周するのを繰り返したほうが(多分)良いです。
解法を抽象化する(レベル高め)
問題のレベルが上がると、1つのアルゴリズムやテクニックで解決する問題が少なくなり、アドホックな解法ばかりに思えてきます。
そのような場合でも、本当に他の問題に応用できないか？ という視点で解法を考察することが重要です。
たとえば「この問題において、解法のDPで計算量が削減できるのは状態数が十分少ないから」ということが言えると、そこから「状態数が少ないのは問題に特殊な制約があるから」「ということは同じような制約がある問題には同様の解法が使えるのではないか」「別の形の制約だったらどうなるか」「前に解いた問題と似ているかもしれない」と考察を深めていくことができます。
テクニックは抽象化することで応用できるようになるので、このような作業は非常に重要です。
ただし、これは十分に解法の引き出しがある状態でないと難しい練習法です。解いてない問題があるうちは、基本的にはたくさん問題を解くことを優先したほうが良いでしょう。
その他のトピック
ライブラリ整備について
重要な点として、持っているライブラリの個数は実力とは無関係です。「必要になったら作る」「同じ実装を何度もやっていると感じたら作る」ぐらいの感覚でいいと思います。
もちろんライブラリ整備自体が楽しくなってそれを目的とするのは否定しません。虚無埋め(簡単ですぐに解ける問題を大量に解くこと)について
タイピング練習に使えたり、ABC361-Bのような穴になりやすい問題もあったりするので、言うほど無駄ではないと思います。座学(問題を解かずに勉強すること)について
個人的な感覚では、必要性が薄いです。基本的にはアルゴリズムやデータ構造は問題の解説で出会った時に覚えれば十分で、「どういう問題なら使えるのか？」をセットで習得できていないと意味がないです。バーチャルコンテスト(本番を想定して、過去のコンテストと同じ問題セット・制限時間で解くこと)について
私はほとんどやったことがありません。本番と同じ緊張感で取り組めるならよいが、後半の時間を持て余すぐらいならさっさと解説を見たほうが無駄がないと思います。
まとめ
- 解けた問題よりも解けなかった問題の振り返り・反省に力を入れる
- 初めて学んだ知識よりも2回以上見た知識をきちんと定着させる
- そのために解法やテクニックはなるべく抽象化・一般化して覚える
参考になれば幸いです。
