Educational Codeforces Round 69

スポンサーリンク

A. DIY Wooden Ladder

$k$ 以上が $2$ つ存在し,$k+2\leq N$ というのが条件です.

B. Pillars

移動前がちょうど $1$ 枚である必要があることから $2$ 枚以上になった山はゴールにするしかないです.するとそうならない間常に相対的な位置関係が保たれるため, max から見て左右に降順であることが必要になります.

C. Array Splitting

列が単調増加なので,それぞれ右端から左端を引くことになります.$a_r – a_l = \sum_{l\leq i<r}(a_{i+1}-a_i)$ であることを考慮すると,$a_{i+1}-a{i}$ を指定個数加算できるということになります.

D. Yet Another Subarray Problem

$m$ の制約が小さいです.$R$ を固定して $L$ を最適化しますが,$L\pmod{m}$ を固定するごとに最大化したい式を考えると,累積和を少し変換したもののこれまでの min が必要だと分かります.

E. Culture Code

ソートして内側か外側どちらかから dp していけば,$O(N^2)$ 時間で解くことができます.この dp の遷移はセグメント木区間クエリでまとめられます.

F. Coloring Game

まずすべてのマスに色が塗られていれば,各テープの grundy 数は手前から dp で求まります.

この dp 遷移は行列で書けます.末尾 $3$ マスの grundy 数の組み合わせを状態とします.各 prefix の grundy 数は $3$ 以下なので,状態数 $64$ です(これら全種類現れる入力がなかったりするかも?必要な状態だけ作ると定数倍が良くなりそう).

色が塗られていないですが,これはすべての色の行列の和で遷移すればよいです.色が決まっていないところを行列の累乗で遷移すれば各テープの grundy 数の分布が求められます.

同じ行列 $A$ に対して $A^nv$ を計算するというタイプの計算がたくさん発生します.$n$ を binary よりも大きな単位で分割したり,$A^{n+m}v = A^{n}(A^mv}$ のように行列行列積を回避したりすれば,毎回行列積を $O(\log n)$ 回行うよりも高速になります.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました