真面目なやつ

精進の記録

AtCoderで青になるまでにやったこと

先週のエクサウィザーズコンテストで、念願の青になりました！ f:id:veqcc:20190404220010p:plain

ということで、例のごとく青になりました記事を書こうと思います。

ほんとは「コードギアス見てたら青になってました！」だけ書こうと思っていたんですが、結構真面目に書いちゃいました。

目次

  • 簡単な自己紹介
  • 水色になるまでに必要なこと
  • 青になるまでにやったこと
  • 青になるためにやったけど多分必要なかったこと
  • 競プロをやる上でめっちゃ参考にしたブログ

どんな人ですか

今年から東京大学工学部システム創成学科4年になります。

研究室は確率統計をやることになりました。大学院は型システムを専攻したいなぁと思っております。

プログラミングを始めたのは2017年夏くらい。

本格的に始めたのは2017年11月。

競プロを始めたのは2018年6月10日です。

約10ヶ月で青になりました。（世間には1年経たずに黄色になったりする人がいて怖いですね...）

パフォーマンスの遷移はこんな感じ f:id:veqcc:20190404220820p:plain

水色になるまでに必要なこと

水色になるには

  • DFS, BFS
  • ダイクストラ法, ベルマンフォード法, ワーシャルフロイド法
  • UnionFind
  • 累積和
  • 二分探索, 二分法
  • 約数とか素数とかnCkとか数学っぽいやつら
  • 全探索, bit全探索
  • DP
  • 貪欲法
  • しゃくとり法

あたりをやればいいと一般的に言われていますし、実際そうだと思います。（要は蟻本の初級編を全部やる！）

一部の人に反感を買いそうですが、僕はあまり精進をせずにレート1000くらいの実力があったと思います。（レート推移的に）

競プロを始めてすぐ上記のアルゴリズムたちを覚えることで、約3ヶ月で水色になることができました。

しかし、これらのアルゴリズムしか勉強せず、惰性でコンテストに参加していたせいで、水色に上がっては緑に落ちる、ということをその後3ヶ月繰り返してしまいました。

そこで11月ごろから、「青になるにはどう精進したら良いだろう」と考え始めました。

青になるまでにやったこと

大きく分けて、

  1. 300-500点問題をひたすらやる
  2. 分野別に集中的にやる

をやりました。

青になった時点での解いた問題数はこんな感じです

AtCoder Scores f:id:veqcc:20190404222449p:plain

AtCoder Problems f:id:veqcc:20190404222553p:plain

300-500点問題をひたすらやる

競プロの問題では、「別に特定のアルゴリズムってわけではないけど、よく使う考え方」が存在します。

操作は逆順から見ると良いとか、値の小さい順に見ると実は貪欲でできるとか、一見グラフではないのにグラフにして考えるとわかりやすいとか。

こういうのは分野別に分類しにくく、問題を色々解く中で覚えていくしかないかなーと思っています。 そこで、300-500点の過去問をやるというのは、「難しいアルゴリズムはほぼ必要ないけど結構考察が必要」という意味で効果的でした。

「DPの更新を累積和で高速化する」的な、基本的なアルゴリズムの組み合わせもここで練習できた気がします。

分野別に集中的にやる

これは1とは逆に、よく聞くアルゴリズム名だけどまだ使えないなぁというものを、分野別に問題を集めてやってました。 分野別に集める方法は、はまやんはまやんはまやんさんのブログ(https://www.hamayanhamayan.com/)を参考にしたり、yukicoder(https://yukicoder.me/)のタグから探したりしました。

以下に、青になるためにやってよかったなぁというアルゴリズムたちを載せます。

  • Segment Tree : セグ木です。応用範囲が広く、セグ木が想定解でない場合にもセグ木で無理やり解く（いわゆるセグ木で殴るというやつらしい）ことができます。
  • Binary Indexed Tree: BITです。転倒数を数えたりするときに使います。
  • bipartite patching : 二部グラフのマッチングです。フローで解けることが後に判明しますが、フローじゃなくてもDFSでいけるので青になるには必要かと。高校数学の美しい物語がわかりやすい(https://mathtrain.jp/bipartitematching)
  • bitDP : 単純に考えたらN!かかりそうなDPを、2Nでやるやつです。巡回セールスマン問題とかハミルトンパスとか。
  • 桁DP : 問題が典型になりがち、という意味でコンテストでは出にくい(?)ですが、考え方を学ぶという意味でやったほうがいいと思いました。
  • 包除原理 : (A or B) = A + B - (A and B) という高校でやったやつを、集合2個ではなくN個にしたらどうなる？というやつです。知らぬ間に包除原理を使っていることもあります。
  • 行列累乗 : フィボナッチ列の第N項をO(logN) で求めるには？というやつです。DPでたまに登場します。
  • トポロジカルソート : 有効グラフにおいて、頂点に順序をつけて、順序を守るようにソートすること（説明が下手）。閉路の検出にも使います。
  • Longest Common Subsequence : LCSです。最長共通部分文字列。DPの復元という意味でも重要です。
  • Nim : ゲームの一種です。2人対戦のゲームで、実は対戦前に勝敗が分かる系問題の考察で参考になります。
  • ガウスの消去法 : 行列のrankを求める、線形代数のあれです。実は競プロでも使うんです。

（思いつくままに書いているので、これもそうじゃない？とかあったら教えてください。）

青になるためにやったけど多分必要なかったこと

決して「これはやっても無駄！」というわけではなく、あくまで「青になるために必須ではなかったかな」という意味です。

  • フロー : 最大流とか最小カットとか燃やす埋めるとかです。蟻本中級編にあるにも関わらず、AtCoderではほとんど見ない気がします。青->黄->橙でめっちゃ必要なイメージ！
  • 文字列アルゴリズムたち : ZAlgorithm, SuffixArray, RollingHash, Manacher とかのことです。こどふぉではよく使う(?)のでちゃんと復習したいアルゴリズムたちです。
  • バケット法・平方分割 : 問題で出会わないので忘れました。

書き出してみると思ったより少なかったかも...

競プロをやる上でめっちゃ参考にしたブログ

分野別に精進するとき紹介したはまやんはまやんはまやんさんに加えて、わかりやすくて参考にすることが多いブログを紹介します。

初心者向けから難しい問題まで...一番参考にしてます。

実装が綺麗で、解説もめちゃくちゃわかりやすいです。

コードが読みやすく、なぜその着眼点に至ったのかなどがわかりやすく解説されています。

というわけで、青を目指す人の参考になったら幸いです！