はい、writerをしていました。
Div2Easy
概要
文字列に「ある文字を全部ある文字に置き換える」という操作をして全ての文字が同じな文字列になるようにするとき、最小何文字(操作の数ではない)置き換えれば良いか。
解法
(文字列長) - (一番多く含まれる文字)
Div2Medium
概要
歯車が円周上に並んでいて、それぞれの歯車に回ることの出来る方向が決まっている。
最小いくつ取り除けば全ての歯車を回転させられるようになるか。
解法
先頭の歯車を残すか消すかで場合分けして貪欲に前から舐めて同じ文字が続いたら取り除く
run length圧縮をする解法が多分楽
Div2Hard
概要
長さNのビット列とNの約数Mが与えられる。
A. １つのビットを反転
B. 前からMの倍数個のビットを全部反転
C. 後ろからMの倍数個のビットを全部反転
の操作を繰り返してビット列を1111...111にするには最小何個の操作をすれば良いか。
解法
操作Bは「全部反転してから、操作Cをする」と同じなので、操作Bについてのみ考えれば良い。(ただし0000000000という、コーナーケースあり。) DP。
Div1Easy
概要
文字列に「ある文字を全部ある文字に置き換える」という操作をして回文にするとき、最小何文字(操作の数ではない)置き換えれば良いか。
解法
同じにしないといけない文字間に辺を張って、各連結成分ごとにmaxをとる。
Div1Medium
概要
歯車が３色あって、なんか噛み合ってる。
・同じ色の歯車同士は噛み合っていない
・同じ色の歯車同士は複雑な構造により、同じ方向にしか回らないようになっている
解法
３色を同じ方向に回すよりは２色・１色に回る方向を分ける方が良い。
２色の方は噛み合っては行けない。→最大安定集合を求めれば良い。
２部グラフなのでマッチングを求めれば良い。
Div1Hard
概要
長さNのビット列とN以下の整数Mが与えられる。
A. １つのビットを反転
B. 前からMの倍数個のビットを全部反転
の操作を繰り返して長さN-Mの接頭辞と長さN-Mの接尾辞が等しくなるようにするのに必要な最小の操作の数
1 <= N <= 300
解法
どんな文字列が条件を満たすかと言うと、長さMのパターンが繰り返されているようなものです。(どことどこが同じになるかを書いてみると分かる) M > N/2のときはコーナーケース
Mが18以下の時とそうでないときで場合分け
Mが18以下の時はパターンを全探索してD2HみたいなDP
Mが18以上の時はN/Mが18以下になるので操作Bをやるかどうかを全探索
