セットを開くと 2 問 intractive で驚いた。とりあえず Batch の C を見るもだいぶ苦手そうな問題だった。色々と試して S = 0 を大胆予想で通して 50 点を得て一旦逃亡した。(max(辺 i - i+1 を跨ぐ荷物の個数,1) * 2 の総和を取るが、右端で p_k = k となっている部分を除く)

A を見てみると意味のある景品が 500 個程度だったのでそれぞれについて二分探索をするだけでかなり良さそうじゃないか？となり乱択をして 1 個飴を見つけて飴以外の個数を知り、二分探索を行う。ただし、mid が飴以外の場合は mid+1 を見て、それも飴だったら mid +2 を見て...としていく。ジャッジが adaptive なのを忘れていて始めの飴を見つけるパートで 10 回だけ聞くとしていたのが落ちてしまったがこれに気付けずかなり時間を消費してしまうも、97.41 点を得る。ここから、30 回程度の節約になると思い飴が見つかったら break を入れると 100 点になった。飴以外を始めのうちに渡すケースは元々通っていて、それ以外のケースは 200 回以上改善されたらしい。飴以外を始めのうちにどんどん渡すと二分探索で最悪ケースに出来ないので確かにそうなりそう。

A が簡単だったので B が難しいのか？と思い一旦 C に戻ってくる。やりたいこととしては、交わらないサイクル間の移動を出来るだけ減らしたいということになる。1 回通った頂点のサイクルに含まれる頂点までは無料で行けて、コスト 1 を払えば今いるところから右か左に 1 歩歩ける。ここで重要なのは S を跨ぐまだ付いていないサイクルがあるかどうかでそれについて考えるとあるならば左右のうち近い方を、ないならば左右にただひたすら歩いてワープを繰り返すだけとなり、書いてみると通った。大胆予想を置きながら考えていくタイプの問題はふわふわした思考回路になってしまい苦手だ...

時間がなかったので B で全域木を取り、後退辺を付けてサイクルの辺を 1 個消す方法を全部試して共通の辺が増えた場合全域木を置き換えるというクエリ回数 O(N^3) を投げたが N <= 50 まで通った。定数倍がかなりいいのだろうか。改めて考えてみると 2N 回か 3N 回使えば全域木の辺については使うか使わないかが分かり、それ以外の辺については頂点ごとに二分探索すれば通るはず？実装はしていない

100-30-100 = 230 点となった。day 1 の A のマラソンで超当たり方針を引いたので総合だと 455.33 点だが、あまり安定性のあるムーブを出来た気がしない。特に、C については 10 回やって満点が取れるのが 2,3 回な気がしている。