Educational Codeforces Round 177

スポンサーリンク

A. Cloudberry Jam

よくわからないけど 2n を出力すれば ok っぽい?

B. Large Array and Segments

周期いくつか分と suffix ひとつです.suffix 長を固定して周期の個数の範囲を計算.

C. Disappearing Permutation

$i$ から $a[i]$ に辺を張ったときに,サイクル部分はひとつ変更するなら全部変更する必要があります.

D. Even String

それぞれの文字を奇数インデックスと偶数インデックスのどちらに入れるかを決めます.個数がぴったり上手くいく分割方法において,数え上げは定数です.

E. Zebra-like Numbers

$(4^n-1)/3$ の和いくつで書けますかということです.$n=0$ も許して考えればよいです.このとき判定問題に単調性があります.

$k$ 個で作れるものの個数から,$k-1$ 個で作れるものの個数を引きます.

$k$ 個で作れるものの個数が求まればよいです.$x$ が作れるというのは $3x+k$ が $k$ 個の $4^n$ の和にできるかというのと同値です.$4$ を $1$ にばらすことを考えると個数を $3$ 増やすことはできて最小個数いくつの $4^n$ の和にできるかだけ考えればよいです.つまり $4$ 進法での digit sum です.

整理すると,ある範囲にあって $\mod 3$ で適切な値で $4$ 進法での digit sum がいくつ.という条件になり,桁 dp で数えられます.

F. Online Palindrome

各奇数 $n$ に対して回文からなる集合 $S_n$ を用意して,$S_n$ から 2 手後には $S_{n+2}$ に入っているというようにしたいです.

そもそも適当に回文をとっても,何が来ても 2 手後に回文にできるというわけではないです.

2 手後に回文に至れるものだけを $S_n$ とし,2 手後に $S_n$ に至れる回文だけを $S_{n-2}$ にするという要領で,実験コードを書きました.

$S_n$ に入れられる可能性がある文字列はそれほど多くないものの,まだちょっとパターンが分かりにくかったです.0,1 の個数に対してひとつずつ選んで何とかすることを考えます.2 文字増やしても似たパターンになっていて欲しいので,prefix の形などが一貫した規則がある感じに選びたいです.結論次のようにすると成功しました.

000000000000000
000000010000000
010000000000010
010000010000010
010100000001010
010100010001010
010101000101010
010101010101010
010101101101010
010101111101010
010111101111010
010111111111010
011111101111110
011111111111110

実験でこれを $S_n$ とすれば上手くいくことは分かりました.

あとは実際の手順を求めればよいです.制約が $99$ 以下と小さかったので,これは単にすべての swap を全探索する感じにしました.

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