2019/6/2のAGC034で青になりました。
嬉しいですね、これからも精進を続けていきたいと思います。
青になるまでにやったことのメモなどを書きます。
・水色まで
→こちらの記事をご覧ください。
https://i7-yoc.hatenablog.com/entry/2019/01/29/000626
・青になるまで
・500-700点をたくさん解きました
→過去問になれるのは重要ですし、パターンも身につきます。
JOIが終わって競プロを1ヶ月ほど中断してしまったのですが、AtCoderの問題を解いて頭を使うのが楽しいということに気づいたので精進をしました。
(AtCoder Scoresより)
ご覧の通り、4月あたりから精進レートが急に傾きを変えていますね、それと並行するようにレートも伸びています。
・「令和ABC」の存在
→2019年5月以降のABCはRating変化対象が〜1199から〜1999に、パフォーマンスの上限も1600から2400に変更されました。Ratedコンテストの回数が増え、かつ自分にあっているセットだったのでこれでいい感じにレートを上げることができました。ちなみに元号の変化と同タイミングでABCの制度が変わったので「令和ABC」と呼ばれることがあるそうです。
・JOIの問題での基礎力
→(水色の記事でも書きましたが)2月のJOI本選に備えて過去問をたくさん解きました。JOIの問題はしっかりとした考察を要する問題が多く、春合宿にはいけなかったもののこの時期に精進をしたことで基礎力がだいぶついたと思います。データ構造にもなれることができました。(難易度9までを少しずつ埋めました。)
・習得したアルゴリズム
→ないようで意外とあるので、メモしておきます。
・DP全般
・二分探索
・priority_queue
・modの逆元、fermatの小定理
・コンビネーション(nCr)のmod(上と内容がかぶっているかも)
・累積和/imos法(例えばGCD(最大公約数)やXORのように、和でなくても累積的に扱えるものがあります。)
・XORの性質(2回に1回はXORが登場しているイメージがあります。
・繰り返し2乗法
・グラフ理論全般(木の直径、トポロジカルソートなど)
・セグメントツリー・BIT(「令和ABC」はセグ木で殴れる問題が出やすい傾向がありそうなので(まだ3回しか開催されていないのでなんとも言えませんが)、セグ木はもっておくとおすすめです。ただしABCの問題はほとんど想定解はセグ木以外なので、決して必須というわけではないです。
・Union-Find(自分はそんなに使いませんが、他の参加者が使っているのはまあまあ見ます)
このあたりは持っていたほうがいいと思います。あとは問題を解いてひたすら着想過程の練習をしましょう。
水色になるまでに200問近く解いたのですが、青になるのにさらに100問ほど解きました。
<自分の問題の解き方>
ここまで散々「問題を解け」と言っていますが、それでは自分がどのような思考過程で問題を解いているか、少し説明したいと思います。
・アルゴリズムを覚えるときは「○○がO(△)できる」くらいの認識でいい。使うときに呼び出す。
・考察用紙にしっかり性質を書き出す。実験をたくさんする。
・構築なら自分でいくつか構築してみる。構築はサンプルケースが当てにならないことが多いので、自分でサンプルケースを生成する。
・(あまり出ないが)インタラクティブなら99.8％位の確率で二分探索をさせようとしているので、どうしたら二分探索できるか考える。
・実装が重くなりそうならもっと軽実装で済む解を考える。
・貪欲でできそうだと思ったらまずはコーナーケースを探す。(あとから値が良くなる場合。) なさそうなら証明を考えるが、感覚で理解できれば良い。
・行動パターンをまとめる。一見複雑に見える問題でも、実は最適解は2〜3パターンのうちのmax、などといった場合が多い。
…適当すぎますが、思いつく限りだとこんな感じです。
同じ配点でもARCとAGCの問題では難易度が違っていたりして、AGCのほうが体感的には簡単です。
半分半分の割合くらいでAGCとARCを埋めるのをおすすめします。
こんな記事が誰かの役に立つのかわかりませんが、とにかく青になれたのは嬉しいですね。これからも精進を怠らずさらなる高みを目指したいと思います。では。
(記事書いたの2月以来らしいです。。。もっとちゃんとやれ。)
