はじめに
こんばんは、ももはらです。
AtCoderをはじめてそろそろ一年が経つので、精進記録を書きたいと思います。
今こんな感じのパフォーマンス遷移をしていて、水停滞から青パフォ安定（？）までに精進したことを、具体的に書きたいと思います。（青なりました記事はほぼ日記だったので）
私が水色で停滞していた理由としては、以下のことが考えられます。
- アルゴリズムを覚えても、使い方がわかっていないため、コンテストででるのが一回目だとうまく使えない
- 知識が偏っていて、にぶたん、桁DPなどの典型がかけない
そのため、どうやってアルゴリズムについて勉強して、使えるようにするか、を主に書きたいと思います。
過去問うめ
ABCのCとDを並行して進めており、Cは埋め終わりましたがDはまだ19問残っています。
基本的には1時間位考えてもわからない問題は解説ACですすめています。解説ACするときの注意すべき点は、どうやって考えたらその解法にたどりつくのかを意識することであると思います。同じような問題がでたときに、たどり着けなくては意味がありません。
わかりやすい目安としては制約条件があります。
- n<=1e18：O(1)、O(logn)の解法などが当てはまります。数学か、二分探索などを考えてみましょう。
- n<=1e12：O(1)、O(√ｎ)の解法などが当てはまります。約数などを使ってできないか考えてみましょう。
- n<=1e6：O(n)でも間に合います。文字列とか数列だったら前から見てくのとかを考えてみましょう。
- n<=1e5：ソートO(nlogn)は許されそうです。ソートして前からうまいことできないか考えてみましょう。また、n回二分探索をしたりもできるので、色々できそうです。
- n<=1e5、a<=1e18：決め打ち二分探索O(n*log(a))などによくある制約です。aの値を決め打ちしてうまくできないか考えてみましょう。
- n<=1e3：ここらへんになると色々あります。ABCのEFだとDPの確率高そうです。
- n<=40：半分全列挙O(2^n/2)ができます。20個ずつに分けて全列挙したものを保存して、それについて二分探索したりできます。
- n<=18：bit全探索O(2^n*n)が間に合います。一人につき(0,1)で考えられないか考えてみましょう。
- n<=8：全探索O(n!)が間に合います。迷わず全探索です。お供にnext_permutationの使い方を覚えとくと便利です。
こうやって見てくと、天才じゃなくても解法が思いつけそうな気がしてきませんか？
こういうアルゴリズムがあるんだってなったときは、そのアルゴリズムが「どのくらいの計算量なのか」＋「どんな制約ででやすいのか」を一緒に覚えてあげるようにしましょう。
また、一つ新しいアルゴリズムを覚えたときは、解説ACするだけじゃなくて類題も解くようにするとベストだと思います。
コンテストの復習
最近はAtCoderだけではなくて、Codeforces、yukicoderさんのコンテストに参加するようにしています。そして、精進のためにはコンテストに参加するだけじゃなくて、必ず復習時間を設けることが大事だと思っています。
コンテスト中に問題文を読んで考えてたけどわからなかった問題は、必ず数日以内に自力ACもしくは解説ACするようにしています。この「あと一問」が解けるようになれば着実にパフォーマンスは伸びるので、あと一問を必ずACするようにするのは大事だと思います。
アルゴリズムの勉強
水色になってから蟻本を購入し、本格的に勉強し始めました。
今は下記サイトを参考に進めています。
qiita.com
区間スケジューリングや、個数制限なしナップザック問題など、最近見たことのある問題もあると思います。
また、上記のサイトでは、結構レベル上めの問題も紹介されていて、面白いです。（普通に解けないのが結構あります）
おそらく、蟻本をただ読んだだけでは、具体的にどういう問題に使えるんだろうというところが曖昧で、実際に問題を見ても解法が浮かばない恐れがあります。なので、必ず新しいアルゴリズムを覚えたときは類題をときましょう。（圧力）
まとめ
上でつらつらとやったことを書いたんですが、大事だと思ったことをまとめると以下2つです。
- 新しく知ったアルゴリズムは「どんな計算量か」＋「どんな制約で使えるか」も覚える
- 解説ACした問題は必ず類題をとく
アルゴリズムを覚えるのと、使えるのは違います。覚えただけで満足しないようにしましょう。
おわりに
ここまで読んでいただきありがとうございました。
青になった記事よりも精進内容をわかりやすく書こうと頑張りましたが、どうなんでしょう。（自分でわからなくなってきました）
記述に間違いがあったらTwitterでこっそり教えて下さい。
よい精進生活を。
