A. 1-1
操作は可逆なので，とりあえず可能な限り 1 を作ってしまってよいです．最大値は確定します．
最小値は連長圧縮状態ごとに考えます．0 が連続させられないことなどからそれっぽいやつが上界になります．
B. One Night At Freddy’s
未証明AC
- イベントは最大値が $0$ に戻るものとしてよい（それはそう）
- $m$ が将来的なリセット回数より $2$ 以上大きいとき，最小値はもう使わないとして捨ててよい．（それはそう）
- これをやった上で，最小値のところに足してバランスよく育てていく．（なんでだろう）
正しいなら帰納法で証明できる気はするが．
→ 理解できた
言い換え問題文．
箱が $M$ 個ある．最初は値が全部 $0$．インクリメントする箱を選べる．最大値の削除操作が $N$ 回来る．とします．インクリメントでは単調性を保つことを強制し，最大値削除は「末尾削除し，先頭に $0$ を挿入」となります．
するとさらに言い換えると，「はじめから無限個の箱がある．その時点で末尾 $M$ 個にしかインクリメントできないというのと，単調性を保たなければいけないというルールがある．末尾の箱が消えるイベントがある．そして，最終的に最大化したい目標の箱が決まっている」という状態です．
目標の箱の値を増やすことができるならばそれを足せばよいです．そうでないなら単調増加を目指すために，増やすことができる最寄りの箱の値を増やす，という貪欲で解くことができます．
C. Where’s My Water?
$A[i][k]$ を，$i$ に drawin を設置した場合の $k$ から得られるスコアとします．
$(i,j)$ を選んだときのスコアは，$\sum_k \max(A[i][k],A[j][k])$ です．
「$i$ を $i\pm 1$ に変えると明らかに得するような $i$ は調べない」というタイプの枝狩りを入れます．
この $O(N^3)$ で AC でした．最悪ケースで $i,j$ は $N/2$ 通り，$k$ は $N$ 通り調べるタイプですが，どうでしょうか？
D. Boxed Like a Fish
後退解析風に考えると
- good に到達すると勝ち．という good な頂点全体を考える．
- leaf は good である．
- $v$ に居るときに good に行けることが保証できる点は good である．
- 根は good ですか？
ということです．はじめ，$2$ つの good から距離 $k$ 以下だと good だと思ったのですが，違いました．
阻止側が $1$ 手パスできるからです．長さ $2k$ のパスの場合を考えると，阻止側は leaf の隣接まで来たときに態度を決めればよいです．
次はいえます．
- good 同士が距離 $k+1$ 以下のとき，この $2$ 点を結ぶパス上は good
これはそのパスだけでゲームをすると思えば示せます．この条件を満たす点がなくなったとき，good でない点は負けです．阻止側は good に隣接したら阻止，というようにすればよいです．
あとは $v$ を根として木 dp をして，bottom up に $v$ が good にできるかどうかを調べます．これで誤判定するのは，祖先の good な頂点とパスを作る場合ですが，このときは $v$ を good にする操作は無視しても祖先側で good を作れるため，考慮しなくてよいです．
E2. N-MEX (Counting Version)
サンプルのように $[6,6,6,4,3,3]$ に対応する解を考えます．後ろから考えます．
末尾が $3$ というのは，全体の頻度列が `+++0???` という状況です．
その次に，つまり $b$ の末尾削除によって $3$ のままなのですが，これは $0,1,2$ のどれかの頻度が $0$ になるということを意味します．
この時点で $3$ 未満の数同士の区別は不要なので，これが来た場合には，操作方法数え上げには $3$ 倍し，$0$ の頻度が $0$ になったとします．
- $3$：`+++0???`
- $3$：`0++0???`
- $4$：`0++00??`
$3\to 4$ のように増えました．これは何かを削除した結果，$4$ の頻度が $0$ になりましたが，ここで削除したものは上のケースだと $0$ だと確定しているもの $0,3$ 以外ならなんでもありえます．数え上げにこの方法の個数をかけます．
以降，上述のように頻度が $0$ になる要素が発生するときの値をひとつ決め打ってしまうことで，各時刻での頻度の状況が決まっていきます．
F. Hanabi
種類は $a,b,c$，ランクは $x,y,z$ と書きます．
- $(a,x)$ ごとに $0,1$ を定める．$1$ とは種類側でとること．
- $x$ ごとに $0,1$ を定める．$0$ とはランク側でとること．
これで min-cut になります．
- $(a,x)$ を $1$ にできるのは，同じ種類で大きなランクのカードが手前にないときだけ．不可能ならば sink に $\infty$ 辺を張る．
- とらないカードがあるとまずい．これは $(a,x)$ に $0$ を当てて $x$ に $1$ を当てるのが禁止．$(a,x)\to x$ の $\infty$ 辺を張る．
- $x$ に $0$ を割り当てるとコスト発生．これは $x$ から sink に容量 $1$ の辺．
- $(a,x)$ が $0$ で $(a,x+1)$ が $1$ だとコスト発生．$(a,x)\to (a,x+1)$ に容量 $1$ の辺．
計算量 $O(NM\cdot ANS)$ しか言えてないつもりで，$ANS\leq N$ としても計算量わからない状態です．
G.
まだ
H.
まだ
