入緑しました

 こんにちは。天才以外お断りコンテストサイトに一般の部で参加するタイプの魚です。

早速ですが入緑したので色変記事を書いていこうと思います。おそらくほとんどの人には役に立たないのではないかと疑っていますが。

緑になるまで

一番大きかったのはACL Beginner ContestのEに遅延セグ木をやるだけの問題が出たことです。これを解いて青パフォを出し、一気に+185しました。

習得したデータ構造・アルゴリズム

役に立ったと思ったものは上の方に置いています。

マーク

• 探　探索
• デ　データ構造
• グ　グラフ
• 列　配列
• 数　数学

初めから持っていたもの

• 　列　ソート
• 探　　全探索
• 　数　ビット演算（Red Scarfを解いて水パフォを出しました。XORおいしいです）
• 　数　繰り返し二乗法
• 探列　配列上の二分探索

茶になるまでに習得したもの

• 　列　累積和
• 探　　境界値の二分探索
• デグ　UnionFind
• 探グ　BFS
• 探グ　DFS
• 探列　しゃくとり法

緑になるまでに習得したもの

• 　列　簡単なDP（01ナップサック程度のものです。EDPCをIまで解きました）
• 　数　modの計算（累乗、組合せなど）
• 探グ　01-BFS
• 探グ　ダイクストラ法
• デ列　遅延セグメント木（実装したことはないです。Replace Digitsで役に立ちました）
• 　グ　クラスカル法
• デ列　BIT（セグ木でよくないですか？）
• 探列　半分全列挙
• デ列　セグメント木（うし木ならソラで書けます。upsolveする時役に立ちます）
• 　グ　最大流・二部マッチング（まだ使いこなせていません）
• 　列　座標圧縮
• 　　　平面走査（実はまだRange Set Queryを解けていません）
• デ列　スプレー木（実装だけして、使ったことはないです。RubyでSmart Infantsを解く時などに使えそうですが）
• 　列　FFT（NTT）畳込み（使いこなせてないです）
• 　グ　強連結成分分解・トポロジカルソート
• 　数　行列累乗（使ったことはないです）
• デ列　Sparse Table（使ったことも実装したこともないですが）
• 探　　焼きなまし法（マラソン）

はい。

マラソンたのしかったのでまたやりたいなという気持ちになりました。

もしかすると過分なくらいに知識を身に着けたかもしれません。螺旋本はひととおり読んだ気がします。蟻本もすこし読みました。

おそらく緑に行くには知識より地頭の方が重要かなという気分です。精進しているうちに地頭の方も少し成長した気がします。

正直、頭が特段悪いわけでもなく、全く精進していないわけでもなかったので、緑に行けるのは当たり前という気持ちです。このまま緑停滞芸をすることにならなければよいと思いますが、それは厳しいかな・・・。

学んだこと

コンテスト中にやたらと休息を取らない！中だるみすると時間が足らなくなります。