Educational Codeforces Round 54

スポンサーリンク

A. Minimizing the String

$s_i>s_{i+1}$ となる最小の $i$.

B. Divisor Subtraction

$1$ 手以内には偶数になりそれ以降は $d=2$ ばかりなので偶数が維持されます.

C. Meme Problem

$(a-b)^2=d^2-4d$ から $a-b$ を求め,$a,b$ を求めます.

D. Edge Deletion

最短路木をひとつとって,根を含むような連結部分グラフをとります.

E. Vasya and a Tree

頂点を $(in order, depth)$ とする平面上の点と見なすと,矩形への加算,点取得になります.

F. Summer Practice Report

各ページについて,そのページの最後にあるものの種類ごとに,その時点で連続している個数の最小値を求めます.二分探索で最小化します.

G. Array Game

まず $Q=1$ ならば,後ろから dp で解けます.$\dp[i]$ を $i$ からゲームを始めた場合の先手の勝敗として,$\dp[i+1]$ から $\dp[i+5]$ までの 01 列から $\dp[i]$ が決まるという要領です.

すると各 $i$ は,関数 $[0,32)\longrightarrow [0,32)$ と見なせます.連続 $5$ 個の dp の列を $[0,32)$ の要素と見なします.

変更クエリがなくクエリが区間で来る場合には,これで解けています.関数合成をセグメント木にのせればよいです.変更クエリがある場合も,何もない時の関数合成,すべて flip した場合の関数合成という 2 つ組を遅延セグメント木にのせれば同様に解けます.

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