Codeforces Round 1118

ブログにも解説を載せるのは，2026/08 中くらいにします．ちょっと管理や，自分のための検索資産としていまいちなので．

のお知らせも見てください．

A. Odd Eraser

両端は必ず残るし，両端以外を消すことは可能です．

B 問題のわりに難しかった．

操作回数 $op$ を固定して考えます．

$K=2^{op}$ として，目標とする長さ $X$ も固定します．

おおよそ $\min(\lfloor a/x\rfloor, K-1)$ 個ずつ作れる（ $a=Kx$ だけ補正）みたいな感じになります．

これは単独のアイテムしかないときでもそうで，たくさんあるときは共通の操作 $x,2x,4x,\ldots$ により達成できるからです．

すべての $(op,X)$ で計算することを考えます．これらを固定すると， $x$ での商ごとに累積和で数えるやつで， $O(M\log M)$ 時間． $op$ が十分大きいときは計算しなくてよいので $O(M\log^2M)$ 時間程度です．

double sweep で直径を求めます．

while(check(u,v,ANS+1)) ++ANS;

の形でインクリメンタルに判定すれば，$(u,v)$ ごとに失敗は $1$ 回以下，成功は最終的な $ANS$ 以下でおさえられて，全体で $2N+ANS$ 程度のクエリ回数になります．

入力の区間は $N+M$ 個区別なくまとめてよいです．

という感じです．

さらに，次を行っておきます：$I\supset J$ なら $J$ を削除．

これをやったあとで座圧すると，それぞれの区間の長さが $O(1)$ になります（長さとは座圧後のやつ）．

$dp[i]$ を $[0,i]$ 部分の最適な区間配置としてこれを昇順に計算します．

$dp[i]$ を計算するときの $[l,i]$ の候補が，上のような区間削減と座圧のあとには $O(1)$ 個になっています．よってすべての遷移をためし，長さ列の辞書 max で更新する，ということを愚直にやっても大丈夫です．

とはいえ長さ列への挿入などもあって私の解法は $2$ 乗 log 計算量で，2sec 以上かかりました．

素べきだけ試せばよいです．

$d=2,3,4,5,7,8,9,11,\ldots$ と試していきます．

各 $L$ に対して，$R$ を分類すると，

という状態になっています．このような境界となる $R$ の列 $dp$ を管理します．

すると，

というような処理を反復すればよいことになります．このような組 $(d,a,b)$ は $O(M\log M)$ 通りくらい．判定とアップデートは区間 min のセグメント木への遅延作用という形でかけます．

subtree ごとに，

という dp テーブル（関数）を保持することを考えます． $x=\sum a_v$ を変数にする方が自然だと思うんですけど，parity 片方が欠けたりして大変になると思いました．

すると結局やるべきは，

という感じ折れ線関数は，上のような $x$ を使うと，subtree size の parity に応じて，

のどちらかになります．

結局

ということができればよいです．すべての操作は凸関数を保ち，強めの slope trick を使うとできます．