Educational Codeforces Round 175

スポンサーリンク

A. FizzBuzz Remixed

mod 15 で 0, 1, 2 であるもの.

B. Robot Program

$x$ からスタート,または $0$ からスタートしたときにはじめて $0$ に戻るのはいつかをシミュレーション.

C. Limited Repainting

二分探索.判定問題では操作しては不可能なセル,操作しなくてはいけないセルがあります.不可能セルの間に必要セルが 1 個以上あるような区間の個数がコストになります.

D. Tree Jumps

$dp[v]$ を $v$ で終わる経路数とし,これを深さ昇順に計算します.直前の深さの数え上げの sum から parent での値を引いたものとして計算できます.最初の一歩だけ親の制約がないことに注意.

E. Game with Binary String

太字部分をよく読む!

単純化して,先手は $0$ を $2$ 個,後手は $1$ を含む $2$ 個を,隣接制約を無視して消せるとして解いた場合の結論と同じになります.010 というような盤面で両端をとれることが利いてきます.あとは条件を適当な累積和で表せば数えられます.

F. Friends and Pizza

すべてが奇数枚のときを考えると,subset convolution を含んでいそうなことが分かります.そこで subset convolution の仕組みを考えると,この設定でも全く同じであることが分かります.奇数枚であるような bit の個数を多項式の係数に持って or convolution すればよいです.$O(N^22^N)$.ある程度高速化した $O(3^N)$ も通るそうです.

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