私はARC227をもちまして、入青を達成しました！！！
やったアルゴリズム、テクニック
思っていたより、数学系が少ないですね...
・セグ木に変なの載せる
・遅延セグ木に変なの載せる
・クエリ先読み、イベントソート
・オイラーツアー
・ならし計算量を使うやつ
・Segment Tree Beats
・凸包
・sparse table
・強連結成分分解
・トポロジカルソート
・tatyam set(平衡二分木)
・suffix array
・bitsetを用いた高速化
・DFS木(これおもろいよ！)
・MST応用
・LIS応用
・転倒数応用
・確率,期待値DP
・MEX
・包除原理
・不変量に着目
絶対必要ないと思われるアルゴリズムだが、やったもの
・ラベル無し木の種類数
・length of look and say sequence
アルゴリズム以外のテクニック
・ランテス
・OEISエスパー
・codonを用いた加速
やりたかったけど時間足りなくてできなかったもの
・桁DP
・DAG上DP
・永続セグメント木
・2次元セグメント木
ゆーてるの歴史 水色~青色
水色~青色の期間を分割するとしたら
①連勝期間
②停滞期間
③なぜか伸びた期間
に分けられると思います。
①連勝期間(4/5~5/31)
ABCで早解き５完するのが非常に安定していた時代です。
やはり安定できた最大の理由は、精進を加速したことだと思っています。
２月後半～５月に急に精進量が増加していますが、数学オリンピックで大失敗したことで気持ちが切り替わったんだと推測されます。
この勢いのまま
入青できるんじゃないかと思っていましたが、現実は甘くないです。
②停滞期間(6/1~7/18)
３連勝緑パフォ負け、３連続水パフォ負け、と、負けが連続した期間。この期間でレートを７５溶かしました。なぜか分かりませんが、急に早解き５完のやり方を忘れてしまったようです。
やはり、手が慣れていなかったんだと思います。６月に入ってから精進量が減っていますが、これは自作コンテストの準備、学園祭、受験勉強などで忙しくなったためです。
精進量が減った時期と停滞し始めた時期がぴったり一致しています。
特に緑パフォを3連続で出したときは、実力のなさを実感してかなり絶望していました。
③なぜか伸びた期間(7/19~)
青パフォ後半を連発し、急に伸びています。この状況を改善するために何か特別なことをやったかと言えば、そういうわけではありません。運が良かったということにしておきましょう。
実際にデータを解析してみて
abcにおいて青パフォ以上を出したことは今までに7回ありますが、その週に精進した問題数は15,16,16,28,14,15,19でした。なので、ゆーてるは、その週に14問以上精進しないとABCは絶対に勝てません！ということが分かりました。
ちなみに、この25週間のうち、精進AC数が13以下の週は9つありますが、それらはことごとく上手くいっていません。
じゃあ安定してレートを上げるには
(私を反面教師にして)1週間に14問以上精進するといいと思います。1日2問のペースです。14問精進できなかったらratedするなとは言いませんが、やはり、習慣って大事なのだと思います。
精進時間が確保できないけど入青したい！助けて！
逆に言うと、精進時間が確保できないなら、のんびりやるのが大事になると思っております。負けるパターンを押えていって、同じ過ちを繰り返さないようにすれば、長期的にはレートが上がっていくので...
私は精進時間が十分に確保できない時期もあり、そのときに、レートを落として絶望しました。今思えばもう少しのんびりするべきだったと思っています。
やるべき勉強
①ABC-Fの縦埋め
一番大事です。
ABCを5完するのが安定してできる人が入青するのに躓く原因として、F問が解けないことが挙げられます。実は、ABCDFのような、Fを含めた5完を安定させれば、パフォーマンスは大きく向上します。Eが8割、Fが5割解けるようになれば9割は5完できるので、大敗しにくくなります(と言っている人が5完できなくて緑パフォを連発したのは内緒)。
しかし、F問題ってパターンが多すぎるんですよ
C...二分探索、累積和、DFS、貪欲、UFなど簡単なアルゴリズム
D...DP,DFS,BFS,いもす法、解に対する二分探索、簡単な数学系など基本のアルゴリズム
E...DP,セグメント木、遅延セグメント木、ダイクストラ、などなどの典型のアルゴリズム
F...セグメント木に変なの載せる、遅延セグメント木に変なの載せる、SCC,平衡二分木、確率DP,場合分け地獄や重実装...(以下略)
アルゴリズムを当てはめるだけで解けることは少なく、パターンが多すぎて全てを対策するのは困難
そうです、E問題と比較して、F問題ってテスト範囲広すぎるんですよ！
逆に言うと、このFを安定できたら基本のアルゴリズムや考察アプローチを概ねカバーできると思いませんか？
というわけで水色さんは、F問題を100ACするのがおすすめです。ゆーてるは100ACまでする予定でしたが、完走する前に入青してしまいました。
②典型90
ABC-C,Dが安定しなくなってきたなあと感じて手をつけ始めました。
多くの競技プログラマーは入水のために使ったようですが、私は入水後にするためにとっておきました。一般的には、まだ体に入っていないアルゴリズムを導入するために、積極的に解説ACすることが推奨されています。
私が意識していることは、絶対に解説ACしないことです。
アルゴリズム知らなかったら解けないじゃんって思うでしょう。
ゆーてるは典型のアルゴリズムを全て自ら導出して、解こうと思っています。なぜなら、体ごとアルゴリズム理解することで応用性を最大化できると思っているからですね。現在2/3が埋まっています。残りの1/3には黄diff,橙diffレベルの難しい問題もありますが、必ず自力で攻略します。
③ARC精進
時間がなくて十分にはできませんでしたが...これは大事です。
入青を目指しているのにARCに向き合っていない水色コーダーは危機感を感じた方がいいと赤色コーダーさんが言っていました。
ARCの問題はABCとタイプが違うので、慣れておいた方がいいです。可能ならば、ARCに出題されるいくつかの分野のうち、得意なものを見つけてください。可能ならば、分野の偏った精進をした方がいいです。これは、コンテスト中に的確に立ち回る上で非常に重要です。
最も大事なこと
負けたコンテストから、敗因を分析して、同じ過ちを繰り返さないようにすることです。
ごく当たり前のことです。この意識があるか否かで、敗北の連続を絶望と捉えるか、経験の蓄積と捉えるかが変わります。
ダイジェスト
①ABC454
初めて黄パフォをとれて大喜びした回です。
この期間は連勝期間の中ごろで、気分的には全盛期でした。
0:31 AをAC
3:17 BをAC
8:29 CをRE
CはDFSするだけで解くことができます。しかし、(python特有の)再帰上限の設定を忘れていたのでREしました。
26:00 EをAC
多くの人が苦戦した青diff。ゆーてるは瞬発的に解きました。
ゆーてるは構築問題が強い！
パリティを利用して、N=奇数だと解なしだと説明できるのが前提。
N=偶数のときは、上下にうねうねする解法を使います。
りうるさんのポスト
https://x.com/masp_3/status/2045677744814747791
で分かります。
適切な実装方針において実装は軽いので、瞬殺です。
29:15 CをAC
Cを再帰上限設定を修正しました。
52:24 DをWA
60:29 DをWA
66:30 DをAC
ゆーてるは実装方針を大きく失敗します。それによって想定以上に沼ってしまいました。
具体的には、
・今何が連続している状態かを管理して、場合分け
・これまでに連なった(,x,)の個数を管理する
・条件を満たせば(((...(xx)...))の(,)をまとめて削除
状態の場合分けや末端処理、((..((が))..))より短い場合など、コーナーが多く
正確に処理するのが困難です。
この処理は、ラングレス圧縮をした方が簡単に実装できると後々気づいて反省しました。
しかし、「まとめて削除する」という発想自体が非本質的で、
・(xx)の形が末端に来たらxxに置き換える
それだけで容易に処理できます。場合分けや末端処理は一切不要です。
解けた問題も解説をちゃんと読む、そちらの方が良いなら自分に導入する
って本当に大事ですよ。
ABCにおいて、70分以内にABCDE5完は、非常に安定します。この段階で高確率で水パフォ後半であり、30分あればFが解けるか解けないか～という感じだからです。
その点において今回はOK！あとはFを通せるかどうか～
88:27 FをWA
96:19 FをWA
98:19 FをAC
嬉しいすぎて絶叫しました。
段階的な考察が必要で、それによって難易度が大きく上がっている問題です。
水diffの考察→青diffの考察→緑diffの考察
の3段階です。
コメント：後で詳しい説明を書く
ARC226(入青回)
ゆーてるが入青を決めた、記念すべきコンテストです。
土曜のABC,日曜のARC,両方大勝ちしてレートが+102上がりました。
5:36 AをAC
さすがの瞬発力。いもす法を使うのが楽だと思います。
23:18 BをTLE
30:46 BをWA
う～ん、解に対する二分探索だと思ったけど、なぜか通らない。
O(60TM^2)はだめ？python民はつらいよ...
99:32 FをAC
元々C,Dどちらかを必ず解くと決めていたので、諦めてCに行きます。
これは構築問題です。79人も提出していて、2人しかACしていないので、罠であることは容易に分かります。
Kの上界は、$H \leq W$として、$\lfloor\lfloor H/2 \rfloor \times W/2 \rfloor$です。これは、
・各列の黒の数は偶数
・黒の数は4
から示せます。あとは、それを成立させる配置をかんがえたらよいですが、
H,Wがどちらか偶数なら2×2を敷き詰めれば最善です。あとは、H,Wが両方奇数のとき。
2×2敷き詰め方式で最善にならない可能性があるのは、5×5が最小です。
$\lfloor\lfloor H/2 \rfloor \times W/2 \rfloor$>(H-1)(W-1)のため。
実際、風車型の配置を作れます。
これを9×9,13×13...と拡張していき、残りを2×2で埋めたら、上界を常に達成できるので、これで考察が完了しました。
風車型の配置の実装に苦戦し、思っていたより苦戦しました。
あとは残り20分でBを通そうと努めましたが、通せませんでした...
これが通せたら黄パフォだったので少し悔しいです。