数強コーダーが年内に入緑しました。

AtCoder

Last updated at 2025-12-28Posted at 2025-12-28

私は今回ABC438をもって入緑を達成できました。

全体的に最近は緑色以上のパフォーマンスを安定できて、特に昨日の夜はパフォーマンス1524を叩きだせました。

何をしたのか

・『競技プログラミングの鉄則』を中心としたアルゴリズムの勉強
(正味これだけで入緑の実力は手に入る)
・E問題をコンテスト中にACするための、ABCのE問題の演習

具体的に何のアルゴリズムを勉強したか

○n^kの形の全探索
・順列全探索
○累積和
○いろいろなDP
　・ナップザック
　・部分和
　・区間DP
　・編集距離
　・ダイクストラ法
　・LIS
　・木DP
○DFS
○BFS
・素因数分解
・ミラーラビンテスト
・ユークリッドの互除法
・約数列挙
・nCrの高速な計算
・行列累乗
・エラトステネスの篩
○二分探索
・解に対する二分探索
○座標圧縮
・半分全列挙
○尺取り法
○セグメント木
○遅延セグメント木
・ダブリング
○deque
○連想配列
・最大フロー
・燃やす埋める問題
・ローリングハッシュ
・グランディ数
・分割数
・ヒストグラム最大長方形

○をつけているのが特に大事だと思うやつです。

私が特に愛用したアルゴリズムが座標圧縮です。
座標圧縮が必須になる問題がよく出題されるのは勿論、
解に対する二分探索で美しく解ける問題、平衡二分木が想定解法の問題、
こういった問題が座標圧縮でゴリ押しできることが結構あります。
連想配列を学ぶ前は連想配列を全て座標圧縮で代替していました。頭おかしい。

私が座標圧縮で解いた問題(初級、二分探索なし、応用、本来座標圧縮が要らない問題)
https://atcoder.jp/contests/joi2013yo/tasks/joi2013yo_e
https://atcoder.jp/contests/abc429/tasks/abc429_d
https://atcoder.jp/contests/abc424/tasks/abc424_e
https://atcoder.jp/contests/abc434/tasks/abc434_e
他にも座標圧縮でゴリ押しできる問題が見つかったらどんどん追加します。

私は数学が大好きだったので数学系のアルゴリズムを優先的に学んでいましたが、
それが実際にコンテスト中で役立つことは殆どありませんでした。
一方で、「数学的な考察」は頻出だったので、「一見難しい問題を如何に(累積和、二分探索を用いた)簡単な問題に帰着させる力を鍛える方が強くなりたい人には大事だと思います。私は数学的な考察の素質が既に備わっているので、少ない演習量で解ける問題を増やすことができました。

数学的考察と実装力を鍛えられる問題、つまり良問(最後はかなり難しい)
https://atcoder.jp/contests/abc438/tasks/abc438_d
https://atcoder.jp/contests/joi2021ho/tasks/joi2021ho_a
https://atcoder.jp/contests/joi2026yo2/tasks/joi2026_yo2_d
https://atcoder.jp/contests/joi2023ho/tasks/joi2023ho_b
https://atcoder.jp/contests/joi2025yo2/tasks/joi2025_yo2_c
https://atcoder.jp/contests/abc433/tasks/abc433_f
https://atcoder.jp/contests/joi2026yo2/tasks/joi2026_yo2_f
joiはこの類の問題が多いんですよね。

また、セグメント木、遅延セグメント木の汎用性の高さに驚きました。入緑、入水を目指している人はさっさとソースコードをコピペして使い倒せるようにしましょう。(応用、応用、応用、応用)
セグ木の仕組みそのものは非常に面白いのでぜひ学んでほしいですが、
実用上は仕組みを知らなくても全く問題ありません。
https://atcoder.jp/contests/abc432/tasks/abc432_e
https://atcoder.jp/contests/abc424/tasks/abc424_f
https://atcoder.jp/contests/abc435/tasks/abc435_e
https://atcoder.jp/contests/abc437/tasks/abc437_f

DFSは頻出な割に何故か事故りやすいのでDFSをやりましょう(初級、応用、応用の順)
解けば解くほど得をします。
https://atcoder.jp/contests/abc435/tasks/abc435_d
https://atcoder.jp/contests/abc434/tasks/abc434_e
https://atcoder.jp/contests/joi2026yo2/tasks/joi2026_yo2_e
ちなみに「頂点倍加」なのか「ラベルを複数にする」かどちらにするかは
実装、解釈共に人の好みです。私は「頂点倍加」がしっくり来ません。

ついでにBFSも演習しましょう(初級、初級、応用、応用)
DFSに比べると使用頻度は下がりますしそんなに事故らないです。
https://atcoder.jp/contests/abc425/tasks/abc425_d
https://atcoder.jp/contests/joi2015yo/tasks/joi2015yo_e
https://atcoder.jp/contests/abc420/tasks/abc420_d
https://atcoder.jp/contests/abc431/tasks/abc431_e

基本的なアルゴリズムを学んだ後の茶色辺りの人に是非解いてほしい良問
https://atcoder.jp/contests/abc322/tasks/abc322_d
https://atcoder.jp/contests/abc411/tasks/abc411_d

茶色ぐらいの人には難しい問題ばかりですが
基本的なDPとこの辺りの問題を演習していたら余裕で入緑できると思います。
もちろん全然分からない人は無理に演習する必要はありません。
私は3月までに入水を実現したいと思っています。
まだ学んでいないアルゴリズムも勉強して、本気でレートを上げていきます。

事件その3

ABC438で茶色コーダーが5完に成功してしまいました。

A問題

読解力の無さがWAを生み出して、ACは7分後でした。この段階で10min程度のロスがランキングに響いています。最近のA問題はサンプルを確認せずに提出する攻めチャートに慣れていたので、基本に忠実になる重要性を改めて知りました。

B,C問題

苦労しなかったので特になし。Cはたまに少し難しめになっていることがあります。

D問題

数ヶ月前はこのD問題が解けるか解けないかで一喜一憂していましたが、今となっては
殆どのD問題が簡単に見えるようになりました。成長。
「E問題のために時間をどれだけ残せるか」が勝負どころです。
ちなみに問題をぱっと見てD,Eがどちらも解法がすぐ思い付いたら、Dを解いてEの実装が
間に合わないのを防ぐためにEを先に解きます。Eの方が簡単そうな場合も同様です。

今回のD問題は、「xを確定させた際に残りのB,Cの和を最大にするyを瞬時に計算できたらよい」と分かったので、予め「Ci-Biの末端からの総和が過去最高になるタイミング」をdequeなどを用いて記録しておくと
$O(N)$で勝てます。24分かかりました。

E問題

この問題が解けるとレートが一気に上がるのでここでACできるか否かが非常に重要です。
E問題を安定できたら入水できます。普段はE問題で、解法がすぐに思い付くのに実装が間に合わなくてパフォーマンスが微妙、って感じだったので、20分でACできたのが成長だと思いました。

問題文を読んですぐに、ダブリングを使えばよいということがわかりました。
$f_{k}(x)$を「バケツが人xにいる状態でk回動かしたらどこへ行くか」
$g_{k}(x)$を「バケツが人xにいる状態からk回動かしたら何L入るか」
として、次の性質が成り立ちます
$f_{1}(x)=A_i$
$g_{1}(x)=x$
$f_{a+b}(x)=f_{b}(f_a(x)))$
$g_{a+b}(x)=g_{a}(x)+g_{b}(f_a(x)))$
$f_{2^{k+1}}(x)=f_{2^k}(f_{2^k}(x)))$
$g_{2^{k+1}}(x)=g_{2^k}(x)+g_{2^k}(f_{2^k}(x)))$
これらの漸化式を用いて全てのxとk=0,1,2,...,29に対して$f_{2^{k}}(x)$,$g_{2^{k}}(x)$
を予め計算したら$O(NlogT)$で勝ちです。運よくデバッグに時間がかからなかったので20分でAC。Dよりも速く解けました。

勝因

E問題が速く解けたことです。今回E問題は比較的簡単だったのか、ACした人が1948人もいました。私は最終65分に対して友達が95分で、順位は479差がありました。これは、この30分間でEを解いた人が多く、周りを出し抜けたことを意味します。

これから

今回のABCは私の100%に近い能力を発揮できたと思っているので、この経験を今後もイメージしてコンテストに毎週参加し、入水にグングン近づいていこうと思います。5完が安定してきたらARCにも挑戦しようと思います。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up