Tea break

ちょっとした息抜きに

AtCoderで緑色になるまでにしたこと

競プロ

こんにちは、Wisteria30です。
ABC138で始めた時の目標であった緑色になることができました。
なので備忘録と今後の人のために緑色になるまでにしたことなど書きます。 f:id:wisteria30:20190819015130p:plain

やったこと・やってよかったこと

茶色から緑色になるまでやったこと・やってよかったことを書いていきます。

過去問を解く

超大事。みんなやってるよ。（やってないのは俺だけ）
茶色成り立ての時はCの300が難しい回だと解けずに二完という感じでした。 Cはそれから30問ぐらい埋めて安定してそこそこの速さで解けるようになりました。（それ以外にICPCの過去問を90問ほど解いたが、直結してるかは不明）

f:id:wisteria30:20190819024600p:plain

また、Educational DP ContestはDまでしか解いてないですが、かなり恩恵があったと思います。 解いてからは「それまでCやDに出てくるDPだと分かっていても手も足も出ない問題」たちを攻略するきっかけになりました。

長考するクセをつける

ABCのコンテスト時間は100分とかなり長い時間あります。最初の方は30~40分ぐらいでCまでを解いて、Dを30分ぐらい考えて撤退みたいなムーブをしていました。正直Dは30分考えてダメなら知識足りないし、無理だろという気持ちで諦めていました。
しかし、ICPCの過去問で無限に詰まった問題があって(超高層ビル「みなとハルカス」)、それを長考してACした時に階段を１つ登った感覚を持ちました。（これを解くのに１日ぐらい考えました笑）この長考で知識が足りないで済ませずに基本的なところを考察する力が身についたと思ってます。

長考するクセをつけると問題を多角的に考察する事が出来る力、いわゆる考察力を鍛える事が出来ると感じます。典型と呼ばれる問題でもその考察力の違いで、応用力が大きく変わるという印象を受けます。（この辺りがレートに反映されている？）
また、長考していると今の自分に足りていない知識が明確に浮き出てくるので、今自分に足りないものは何か考えるときには少し難しめの問題を長考するようにしています。

ただ、このあたりは「配点/20 分考えて分からなければ、解説を見る」といったような精進方法もあるそうですし、スッカスカの知識で考えても何も分からないのでバランスが大事だと思います。

アルゴリズムとデータ構造の知識を手に入れる

知識をインプットすると解ける問題が増えます。（小並感）
いくつか選択肢があると思いますが、けんちょんさんのQiita記事が一番触れやすいと思います。DPとビットの記事は特にお世話になっています。
また、競プロ本としては蟻本が有名ですが、正直最初の方しか読んでいないです。良い本なので買って損はないですが、簡単な本ではないので注意です。（kindle版はコピペできず取り扱いも悪いので、買うなら絶対紙の方がいいです）

個人的には茶色の最初の方に読んで、DFS・BFSを学んだ「銀髪赤眼の後輩と学ぶ競技プログラミング」を推します。（銀髪赤眼の後輩に競プロ教えてもらいたい人生だった）
表紙が最高に可愛くて、0から競プロを学べる良本です。boothでpdf版が売っているのでサクッと買えます。

booth.pm

PythonからC++へ移行

ICPCを解く上で問題制約とチームの使用言語の都合上、PythonからC++に乗り換えました。乗り換えてよかったと思う点は以下２つです。

  • アクセスできる情報が増える
  • 計算量を考えるとき、心に余裕ができる

特に1つ目の恩恵が意外と大きいです。競プロでPython記事は増えてきましたがそれでも、C++の記事量に遠く及ばないので、C++をPythonに書き換えるなどの手間が発生したり、部分的な構文が分からなかったりと以外と辛いです。 上節の記事なども大体言語がC++なので、非本質なところでつまづきたくないなら乗り換えをおすすめします。（鋼の意志を持った方々は己が道を突き進んでください）

Twitterで競プロerと繋がる

これ最重要だと思います。
モチベーション維持とコンテスト忘れを防止できるのでとりあえず競プロerをフォローするのがいいと思います。 また、コンテスト前後がお祭りになったり、ジャッジの言語アップデート要望に関するスプレッドシートが流れてきたり、物議醸し出したりとAtCoderは良くも悪くもTwitter依存なので、アカウント作ってない人は作ることをお勧めします。

緑色になるための考察

AtCoderは高学歴以外お断りコンテストや天才以外お断りパズルコンテストと揶揄される側面があり、素晴らしい能力を持った人たちはすごい精進量とスピードでどんどん上を目指して強くなりますが、私のように他ジャンルの学習をしながら緑色を目標にしている人も一定数いると思われます。

なので私自身が緑色になれたので、その経験を基に、緑色を目標にしている方を対象に何が必要なのか考察したいと思います。 （この考察は緑色になることを当面の目標にしている方を対象にしているので、緑をぶち抜いてもっと上を目指そうとしている方はあまり参考ならないかもしれないです）

戦略

当然ですがパフォーマンスが800以上は絶対にないといけないです。

以下が私の緑色になるまでの順位とパフォーマンスになります（外出先でコンテストに出て終電を逃すとunratedになるジンクスがありました）

f:id:wisteria30:20190819202128p:plain

それを考慮した私の直近のパフォーマンスは以下のようになっています。

  • 三完遅解　→　600~800
  • 三完速解　→　800~1000
  • 四完遅解　→　1000~1200

また、体感的ですが旧ABCと新ABCを比較した場合

  • 速解と呼べる基準の時間が以前より早くなっている
  • D問題が易化している
  • 三完速解はパフォーマンスが伸びにくい

といったことが感じられます（個人の感想です）。

実際これが真実かは分からないですが、私が緑色になったABC138はCまで10分ほどで解きましたがパフォーマンスは839と緑になれるかギリギリでした。（この回はDを2000人ほど通しているのでDが易化したこととも繋がると思います）

なので、緑色を目指すのであれば、三完速解よりも四完遅解を目指す戦略の方が安定して良いと思われます。

それを踏まえて考えると以下のような戦術が緑を目指す上で良いのではないでしょうか。

  • 優先的に新ABCの過去問から解く

  • ABCのA、Bはあまり埋めない

  • Cは15~20問ぐらい埋めて高確率で解けるようにする

  • Cの速解を目指して埋めるよりDに取り掛かる

  • AGCに出るのはリスキーなので、着実に目指すのであれば出ないのが賢明

緑色になるのに使った知識

緑になる上で必要だったアルゴリズムやデータ構造の知識などです。

記憶のあるやつは問題のリンクを貼ります。（aoj-icpcも混ざってたりします）

必要そう

スタック、キュー、デキュー、ハッシュマップ

全探索・bit全探索

累積和・いもす法

貪欲法

二分探索

しゃくとり法

簡単なDP

ソート

頭

文字列操作など

あると嬉しい

DFS

BFS

約数・素数関連

XOR関連

ダイクストラ

UnionFind

今後の目標

ICPCに一緒に参加した水色Coderから色々教えてもらい、水色の凄さを知ったので次は、水色を目指したいと思います。ユーフォを見ると水色になれるらしいので多分見ます。 ただ、緑になるための考察で考えていた三完速解ではいけないというのが、緑から水に上がる際も四完速解ではいけないという形で、見えていそうなので400と500の勉強を効率よくこなしていきたいです。（いい加減蟻本ちゃんと読もうな）