より正確には、ABC の A–E をうめました。
自己肯定感が低く、「何々をうめました」というときに「まだうめてなかったのか」という声が自分の中から聞こえてくるタイプの人もそれなりにいるのではないでしょうか。えびちゃんはそういう人です。 他の人がうめていなくても蔑んだりしないのに不思議です。
ふりかえり
E をうめようと思ってから解いた問題を挙げてみます。多少のネタバレを含む場合があります。
- ABC 163 E - Active Infants
- 当時は天才発想だと思ったが、落ちついて考えると解けた
- feasible な解を固定して、隣同士を swap してみると方針が立った
- ABC 204 E - Rush Hour 2
- 当時は下手な三分探索をしようとしてこわした記憶がある
- 待ち時間を全探索するとつらそうなので、手計算したら解の構造がわかった
- 今見ている頂点から時刻 $t$ で出発しても $t+1$ で出発しても到着時刻が変わらない場合、$t$ で出発しても損しない
- 解説と off-by-one が異なるケースがありそうだったので計算をがんばって、記事 も書いた
- ABC 207 E - Mod i
- 当時は頭のいい DP だと思って、自力だと無理だと思った
- この手のやつは dp[i 個見て][j ブロックで][総和が k と合同] とかじゃんという先入観があった
- ブロックとして valid なものだけ考えるような遷移をできるじゃんと思い至るのにだいぶかかった
- DP の遷移を表すグラフを考えると、(総和 mod ブロック番号) の同値類ごとに完全グラフの有向版みたいな感じがある
- 辺の最大ケースは $a_i = 0$ になりそうだが、制約を考えると $a_i = \lcm_{1\le j\le 36} j$ とかになりそう
- 結局は想定解とほぼ同じようであった。配り方はちょっと違うかも
- ABC 212 E - Safety Journey
- ABC 213 E - Stronger Takahashi
- あんまりやる気がしなくて放置していただけ、特に感想なし
- ABC 227 E - Swap
- むずかしかった
- 全部で $3^{30}/10!^3$ 通りあって列挙はつらそう
- 転倒数は $O(n^2)$ なので操作回数が多いのは見かけ倒し。そういうのしばしばある
- 先頭から文字を決めていくとして、次に特定の文字を持ってくるまでの操作回数は、使った文字を数えておけばわかる
- 操作回数で分類すればよさそうで、最短の操作を採用することで重複もなくせる
- 次を持ってくるまでの操作回数は前計算したが、毎回やっても大丈夫という想定だったらしい
- ABC 231 E - Minimal payments
- 愚直にやっちゃだめでしょうという見た目をしているが、慣れていないと愚直にやってしまいそう
- 特定の硬貨を一つ上の硬貨にしたときに、解がどういう変化をするかを考えた
- $X$ 円ちょうど払う場合と比べて、（払い手側が）特定の硬貨を 2 枚以上多く使うことはない
- 硬貨 $i$ を $j$ 枚多く使った、とかで分類した
- ABC 243 E - Edge Deletion
- 三角不等式
- ねむかったので謎のことをして変になった
4 4 1 2 1 2 3 1 3 4 1 1 4 3
- ABC 249 E - RLE
- 圧縮前が $i$ 文字で圧縮後が $j$ 文字とかで DP でしょうという感じ
- とりあえず愚直に遷移を書くが、区間に足す感じにできるので on-the-fly で imos しましょう
- ABC 260 E - At Least One
- $(A_i, B_i)$ に辺があるグラフを考える？と一瞬思ったが、区間 $[A_i, B_i]$ を考えるのがよさそうだった
- 左端で分類して、固定した左端に対して valid になる選び方を考えた
- ABC 262 E - Red and Blue Graph
- これが一番しんどかった。いろいろ迷走した
- 先頭 $i$ 個見て $j$ 個を赤にして、異なる色を結ぶ辺の偶奇を持つ？？そんなんできなくない？？
- 辺の寄与を考える？ 頂点の制約を考えられなくない？？
- 結局、解説の先頭一文だけ読んだら残りはわかった
- これが一番しんどかった。いろいろ迷走した
- ABC 265 E - Warp
- これが二番目にしんどかった
- 最初に踏む障害物を固定したら包除みたいにできる？と思ったが、重複がやばそう（包除パートを高速にできなさそう）
- とりあえず一次元の場合（$B=D=F=0$）とかを考える？と思ったが、あまりうれしくない
- 操作の個数が一つ、二つの場合（$(A, B)$ だけ、$(A, B)$, $(C, D)$ だけ）を考えたところ、あーとなった
- 具体的な経路全体の集合がどうなるかを考えた
- 「$300\times 10^5$ はぎりぎりなんとかなるか？」と最初考えていたが、素直に $300^3$ を考えてみるのが無難そう
- あまりそういうメタ読みっぽいのは好きではないが、メタ読みをせずに固執するのも賢くなかろうので
- ABC 309 E - Family and Insurance
- 当時事情があって忙しくて放置していただけ。特に感想なし
- ABC 313 E - Duplicate
- 具体例を挙げて考えた。
2以上が連続すると発散するのでだめ → `1...1 x 1...1 x ... のような形式になる1...1,1...1 x,1...1 x 1... のように、順々に操作回数を考えた- 結果的に RLE して実装したが、各数字の答えへの寄与を考えることで、RLE は不要になるらしい
- そういうのちゃんと考えられるようになるとよさそうね
- Zero-Sum Ranges で、予め全部の個数を数えるか、on-line で個数を更新しながらやるかの方針の違いみたいな
- ABC 146 E - Rem of Sum is Num
- これは昔解いてたけど当時あまりわかってない感があったので解き直し
- 区間 $[l, r)$ を固定したときの値を実際に書いてみた
- $(\sum_{i=l}^{r-1} a_i)\bmod k = r-l$
- $s(n) \triangleq (\sum_{i=0}^{n-1} a_i)\bmod k$ としてみる
- $s(l) \le s(r)$ なら、$s(r)-s(l) = r-l$
- $s(l) \gt s(r)$ なら、$s(r)-s(l)+k = r-l$
- $s(r)-r = s(l)-l$ とか $s(r)-r+k = s(l)-l$ みたいに変数分離
- 左辺は $k$ 未満なので、古い区間を捨てながら順に見る
考えたい操作だったり解だったりを、適当に固定して探ってみるといいのかなと思いました。 あとは contribution を考えたりとか。 愚直な DP を考えたりそれ以外をすることで、解ける形に帰着できることに気づけたりするかも。 DP するときは、状態がどう分類されるかを意識するとよさそう。
ABC 313 F - Flip Machines も解きました。
- グラフとして考える
- 期待値の線形性からいい感じにできる
- 実際に計算してみると単純な形になると気づく
- もしかしたら計算する前に気づくべきことなのかも
- カードを $D_i = B_i-A_i$ に言い換える
- 自己ループを持つ頂点は予め答えに $D_i$ を足して $D_i \gets -D_i$ で更新しておく
- $D_i$ の正負で頂点集合を分ける
- それぞれの頂点集合のサイズを $n_+$, $n_-$ としたとき、$\min(n_+, n_-)\le 20$ とわかる
- 大きくない方を基準にして別々のアルゴリズムを構築すればよさそう
- 片方は貪欲でよさそう、もう片方は？？
このあたりまでは自力でできました。フローをがんばる？とか無理じゃん？とかいろいろ考えたあと解説を見ました。 上記の流れがそのまま載っていたのでうれしくなりましたが、残り一歩を思いつけなかったのが悔しいです。
自信のない考察をしているとき、その方針でいいのか不安になって、解説とかに頼って「あってるよ」というのを得ないと進めない癖がありました。 6 問時代の ABC の頃にだいぶ訓練して克服したつもりでいたのですが、今回は負けた気がします。
どうやら difficulty が 3100 だったらしいというのを見て、（ほぼ）自力でできたのでうれしかったです。difficulty 信仰はあまり好きではないつもりだったのですが、人間なんてのは単純なものですね。 とはいえコンテスト中に解き切れる自信はあまりない気がします。
おわり
ABC-F もうめたいです。
