🧪

AtCoder 色変記事（入緑　社会人）

2022/03/08に公開

競技プログラミング

AtCoder

競プロ

idea

素敵な夜ですね。kisihara.cと申します。

競技プログラミングコンテストサイトAtCoderでレート800↑となり、色（段位）が緑になりました。この記事は入緑のお礼とご報告の記事であり、自分向けメモであり、緑を目指している方向けに役に立つと嬉しい文書でもあります。水色を目指す記事は多くありましたが、緑を目指す記事はあんまり見当たらなくて…。

競プロをいつから、なんのために始めたか

最初に始めたといえるのは学生時代ですが興味本位で何問か解いたくらいなので省略します。社会人になってから、非IT職からの転職に役に立つと考え、またCSを勉強する事がプログラミングの根本理解に繋がると考え、始める事決定。2020年5月に登録し数回ABCに参加しました。その後2020年10月から真剣に勉強を開始し、2021年1月に入茶しました。

入茶記事はこちらです。

「10^9が計算量の目安といわれても9という数字が覚えられない」
DictionaryでO(1)アクセスする辞書つづり法はなんとなく使える、素数判定やGCD/LCM等はライブラリにある
XFS、にぶたんは覚えないで済ませている

などなんとなくレベル感が分かる感じです。今同じレベルで入茶できるかは謎です（後述します）。

そしてその後、今回2022年3月に入緑しました。AC数は約650で、白400茶100緑110水20程度です。

AtCoder緑とはどういう立ち位置か（2022年3月）

AtCoderのレベル感で、発言力がある記事はやはりAtCoder高橋社長の以下記事かと思います。

緑色　(Cランク R800~1199　上位30%)
緑色になれれば、「競技プログラミングに熱心に取り組んでいる人」と考えて問題ないでしょう。
if、forはもちろん、それを組み合わせて2次元配列に対して操作をしたり、深さ優先探索や幅優先探索などのキューや再帰を使った実装も出来る。
簡単な動的計画法の問題や、数学的に工夫する問題など、計算量の工夫も出来始める。

これは参加者としては嘘になると思います。対外的な説明としては嘘ではないかもしれませんが、参加者としては嘘だと思います。茶色の記述も参加者目線では嘘です。なぜか？　それはこの記事が2年前のもので、インフレを起こしているからだと考えます。

上記2問をご確認願います。前者は2018年、後者は2021年の問題で、類題です（後者のほうが多少ひねりあり）。それぞれのDiff（レート帯の方が解いた実績によって算出される想定難易度）に着目でき、おおよそ色一つ分（レート300くらい）の違いが出ています（前者は水Diff（水コーダーが半数解けるくらい）、後者は緑Diff（緑コーダーが半数解けるくらい））。N=1で恐縮ですが、3年前に比べて、初心者帯にとってAtCoderは色一つ弱分のインフレを起こしていると考えます。それは新規参入者の増加や共有知の整備によるものと考えられますが、ともかく参加者目線なら上記記事だと水色部分を参照する事が必要だと思います。

水色 (Bランク R1200~1599　上位15%)
計算量に関する感覚が体に染みついており、複雑な処理でも苦もなく実装出来る
深さ優先探索や幅優先探索、順列の全列挙やパターンの全列挙などができる。そこから動的計画法やメモ化再帰などの計算量改善につなげることも多少出来る。
貪欲・DP・しゃくとり法・二分探索などの計算量を改善するテクニックをある程度使い分けることが出来る。
累積和やUnionFind(競プロ外ではDisjoint Set)などのデータ構造を使いこなすことが出来る。
ダイクストラ法やワーシャルフロイド法、クラスカル法などの、基本的なグラフアルゴリズムが扱える。木構造やグラフ構造に対して適切に処理を行うことが出来る。
一定以上の数学に関する素養がある。素数などの性質や、それを利用した素数判定や列挙、約数の列挙等、最小公倍数や最大公約数、組み合わせの計算など、競プロにありがちな典型数学問題に対処できる。

気持ちのレベルではありますが非常に近いイメージです。これこそが平均的な緑コーダーの実力なのではないでしょうか。

実例から遡る形でも示します。緑色になるとはどういう事か？　当然の事ながら、緑以上のパフォーマンスを取り続ける事だけが緑になる方法です。それには以下がありえます。

問題セットに難易度の壁がある時に、A～CorD問題を早解き（見て一分以内に解法が浮かぶレベル）
緑Diff～水Diffを解く（ジャイアントキリングと呼んでいました）（DorE問題）

前述の通り、C問題やD問題のレベル、参加者のレベルは上がっています。2018年なら緑Diffだったような問題が茶Diffになっています。また2021年の緑Diffの問題はひねったXFS/ひねったダイクストラ/他、典型のひとひねり/数学/解法は単純だがかなりの重実装/Xor等の抜けがちな知識をついてくる事が非常に多く、骨が折れます。緑Diffの過去問を100問解いたのですが、本番でジャイアントキリングに成功したのは過去とほぼ同じ問題を見た1回だけです（Union-findを逆から組む問題でした）。水色に書かれているような事が結局要るのではないか、と考えています。

（※まあ、高橋社長は世界ランカーなので、「簡単な動的計画法の問題や、数学的に工夫する問題など」というその「簡単」のレベルが違う可能性（つまり別に2019年のブログ記事も、2022年とそう変わらない感想を書いているだけという可能性）は実際あります）

2020年10月、私は2019年の記述を信じて緑を目指そうと考え、長期化、かなりきつい戦いになりました。ただ、私が競プロを始めた理由は転職とCS理解の為です。試験がどう変質しようと、インフレしてようとしてまいと、意思は変わりません。転職については、全体のレベルが上がっているのならどのみち比較優位を取らなければいけないです。CS理解については、2018年基準だろうが2022年基準だろうがどうやらどのみちもっと究める必要があります。それはつまり、俺々の目標の一つとして、俺々が始めてしまった入緑という目標を俺々の手で終わらせなければならない、という事です。

やったこと

CUI環境整備
https://rian.hatenablog.jp/entry/2017/12/06/040000
https://qiita.com/Camypaper/items/de6d576fe5513743a50e
https://oita.oika.me/2020/05/10/at-coder-csharp/
C#を使っています。この辺りの知恵を拝借し、VsCode + WSL + .Net Core + atcoder-cliの環境を整えています。VsCodeのcliでcode program.csと入力すると立ち上がるので便利です。コピペテスト・コピペ提出に比べて多分五分くらい差がつくと思うので早解き狙いなら最重要です。
典型アルゴリズム・データ構造整備
後で再びまとめますが、緑レベルならUnion-findが一番印象強いです。ほかは優先度付きキュー（＋Dijkstra）ですが、C#にはありません。C#だとmulti setもないしイライラで絶頂してしまいコンテストどころではないので整備すべきです。必要知識については後でまとめます。また、それら全部のせのライブラリも後でリンクを貼ります。
Typical DP Contest https://atcoder.jp/contests/tdpc
よく覚えていないのですが、ナップザックくらいまで解いたと思います。DPはやはり難しく、二次元DPについてある程度理解できた（＝さくっと書けるようになった）のはもう五問くらい二次元DPの変形を解いてからですし、そう言いつつ今でも設定が難しいものは解けません。
アルゴ式　整数論的アルゴリズム https://algo-method.com/lecture_groups/9
理解が深まり有用だったと考えています。
ピラミッド本 https://bookclub.kodansha.co.jp/product?item=0000275430
TLのどなたかにあやかり勝手にピラミッド本と読んでいます。競プロ関連の本は多いですが、入緑の為一冊まるごと読むべきだと判断したのはこの本でした。他の箇所は入緑というただ一点についてで言うと関連箇所が少なかった体感です。
競プロ典型90問 https://atcoder.jp/contests/typical90
～☆4までやったほうが良さそうです。類題のDiffが露骨に下がる事態を見かけました（つまり、皆解いている）。
コミュニティに参加
コミュニティに参加して競プロの話をしていると、いつからか解像度が上がったのか緑Diffの解説がぱっぱっぱと頭に入るようになった実感があります。結局の所解像度を上げる→解く問題の難易度を限界まで上げる→解像度を（略）の繰り返ししか無いのかなと思っています。
緑Diff100問程度
緑Diffの解説がぱっぱっぱと頭に入るようになったタイミングで、正月休みを利用してABCの緑Diff100問程度解きました。結局前述通りジャイアントキリング成功が一回だけだったので、緑Diffを解く役にはあんまり立ちませんでしたが、茶Diffを早く解く訓練にはなったと考えます。
解き直し
ABCの緑は大部分解いた2022年2月、正直何をやればいいかわからず、水色に手を出すか、あるいは海外のアルゴリズムテスト問題などを解くのか、わからず、メソメソ泣きながら既存問題を解き直していました。忘れていた問題が多く、パズルの単純な復習としては有用でしたが、あんまり役には立たなかったと思っています。重要な、未知の問題を解く力がつきにくかった気がします。けっこう途方に暮れていました。一旦落ち着いてよかったです。

必要と思われたこと

概念的なところでいうと、数学力、実装力、及び多くの手札が必要になると考えます。１番目について、数学要求する緑Diffはまあまあ厳しい数学問題が多く、かなりきついです。２番めについては、実装難系の茶Diffで死なない為（茶Diffの実装難は別分野の応用で結構解けてしまう人が多くレート的には辛いです。　例：.と#の地図系問題と画像処理系プログラマなど）、あるいは実装難系の緑Diff（XFSやダイクストラのマイナーチェンジが多いです、他再帰とかも）をジャイアントキリングする為に必要になります。繰り返しになりますが周囲のレベルが上がっているので早解きかジャイアントキリングに成功しないとレートは上がりません。国内外の数学部生/情報学部生が大量参入してきている今、0から我々が緑を目指す事は、情報院生が青色を目指す事と同じくらいの重さがある戦いだと考えます。

茶→緑に必要だった手札一覧

上記3番めについて詳細を入れます。

†二分探索†（最近は見ないですが、超頻出/応用範囲広で体感出現率10/100くらいあります。私は、学生さんやずっとコーディングされている方に比べ基礎力が足りてないので、正直に白状するとにぶたんは本番では時間内に組み切れません。基本捨ててました。ただ話を聞くと「素組みは青or暖色コーダーの方でも面倒といえば面倒」との事で、手元にテンプレを持っておくべきのようだと推定します。実際それを聞いてからテンプレにもなる関数を用意する事にしました。出番はありませんでした）
尺取法（出現率8/100くらい、緑Diffだと重実装が伴います。出現率はにぶたんも含め以下全部体感です）
すぬけプライム法（Snuke Primeの解法を誰かが勝手に命名していたのでそのまま使わせて頂いています。途中出現も含めれば地味に出現率3/100くらいあります）
Union-find（応用範囲広、優先度付きキューまで含めて出現率5/100くらい。ジャイアントキリング向けとも言えますし、最近だともう茶Diffになりつつあるイメージです）
応用XFS（出現率10/100くらい。各頂点から入力の倍数時間で電車が出るとか、辺に色が塗ってあり同じ辺のエッジは通れないだとか、緑Diffだと通常のXFSのマイナーチェンジ版が非常に多いです）
Dijkstra法（応用も含めるとグラフ系だと最重要で出現率3/100くらい）
Floyd-Warshall法（範囲狭そうですが意外と出題回数が多く1.5/100くらい見ました。ベルマンフォードは最後まで見ませんでした）
DP（緑Diffまでなら意外と少ない…はずでしたが、C問題に軽率に二次元DPが出るようになり、インフレの為か余裕の茶Diffで、必須になりつつあります。辛すぎます）
木の理解（木は緑Diff体感出現率10/100くらいあります。性質理解の為木の問題を探して全部解くとかしたほうが良いかもしれないです）
紙とペン（緑Diffで体感出現率50/100くらいあります）
SQLの勘（C#のLINQに馴染めませんでした。変な話ですが、結局SQL関連書をいくつか読んでLINQの勘が身につきました）
回転、2点間の距離、点と直線の距離他（このくらいの幾何公式全部合わせて出現率6/100くらいありました。理系出身の方は解ける事が多いようなので、文系の我々は思いつくもの全て先んじて用意すべきと強く主張します）
デフォルトが0のDictionary（C#のDictionaryは存在しない値にアクセスすると例外を吐きます。実務ならそっちが良いと思いますが、競プロだと邪魔なので、作っている方のコードを頂きました）
再帰（体感出現率3/100くらい）
bit総当り/順列総当たり生成（出現率2/100くらい）
クエリ問題対策（クエリ偽装や先読み、もしくはただデータ構造を工夫するだけなど。場合によっては茶Diffにもなり得、非常に辛いです。稀によく出ます）
Xor等bit演算対策（数点程度の性質について。稀によく出ます）
multi-set（緑までなら出現率1.5/100くらい、ジャイアントキリング向けであり、～緑Diffの問題でmulti-setを使う問題は、multi-setを使いさえすれば非常に簡単な事が多く、落とせない問題にもなりえます。C++にはデフォルトで付いているらしいです）
区間スケジューリング問題（典型なら茶Diffと思われますが、ジャイアントキリングの種になるかもしれないです。出現率は1.5/100くらいですが…）
クラスカル法（緑までなら出現率～1/100、ジャイアントキリング向けです）
mod世界の高速nCrと除法のMod（緑までなら出現率～1/100、ジャイアントキリング向けです）
トポロジカルソート（知ってればジャイアントキリングできたケースが一回ありました。優先度は極低）

TIPS

典型実装問題

実装力不足を補う為、繰り返し解いたもの等です。よろしければどうぞ。

ライブラリ

別記事で、入緑に必要だったライブラリを公開します。よろしければどうぞ。

メモ

コンテスト中見ていたメモです。よろしければどうぞ。

計算量が足りない！
→本当に？（見積もりミスってない？）
→O(1)
→数学でO(1)
→循環性/規則性はない？
　→愚直解法にinしまくって法則を見つけ出せ
→枝刈り
　→自動確定など
→にぶたん
→累積和＋いもす法
→篩法
→グラフの問題ではないか？（ダイクストラ・ワーシャルフロイド・Union-Find）
→データ構造の問題ではないか？（C#）
→DP
→問題文読み間違えてない？
→問題文の意味深な制約を一度素直に信じてみよう
→クエリで、処理を偽装できないか？
→（特にクエリで）償却解析的に大丈夫では？

今後どうしていきたいか

入水します。元々の目標は入水でした。今の知識では自分の本来の目的に足りず、入水してやっと求めていた力が手に入ると思っています。

その為、白チャートを買ってきました。大学数学の教科書の候補も何冊か見繕っています。そのへんでインプットを済ませたら、水Diffをひたすら解きます。俺は文系出身である上、キャリアが浅いです。なので数学力と実装力に強い力不足を感じます。時間かけてカバーします。あとは遅延セグ木・bitDP・桁DP辺りが必要になるのかなと…。

広い意味では、もりもり技術つけていって色々作ろうと思ってます（作りたい志向は技術よりというよりはコンテンツよりですが）。オタクコンテンツが好きな方、ぜひお話させてください。

色々教えてくださった皆様ありがとうございました。

twitter:kisihara_c