AtCoderBeginnerContest426 D問題400点 「Pop and Insert」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
気持ち
解法
文字列 $ Sをすべて 0 にするパターンを考えます。
0 にするパターンが解けた場合、文字列 $ Sの 01 を反転させれば同じ計算で 1 にするパターンも解けます。
文字列 $ Sにおいて、 1 は必ず反転させる必要があります。
よって、 1 という数字はできれば 1 回の操作で済ませたい、という方針で考えていきます。
よって、問題は 0 の扱いです。
サンプルケースでわかるように、位置によっては同じ 0 を 0 → 1 → 0 のように 2 回操作しないといけないです。
ここで、操作しなくてもよい 0 はあるか？について考えます。
https://gyazo.com/cbe39ed8f09fc5f1f31eb73c5e4e3888
上記画像のように、連続した 0 の区間 $ A, Bがあり、それに囲まれている 1 の区間を $ Cとします。
$ A, Bを両方操作しない、ようにすると $ C区間の 1 が絶対に反転できないことがわかります。
このことから、操作しないで済む 0 の区間はたかだか 1 つのみであることがわかります。
ここから ある 1 つの操作しない 0 の区間を決めたとき、それ以外の区間にある 0 を 2 回操作、 1 を 1 回操作することですべて 0 にできるか？を考えます。
これができれば最長の 0 の範囲を決めれば、あとはその範囲外の 1 と 0 の処理を行えばよいです。
https://gyazo.com/880c9966453b50a4fb396f7e56a8f5a0
上記の画像のようなケースを考えます。
keep の範囲の 0 を操作せずに残すとします。
このとき、以下のように操作すればよいです。
keep の外にある 0 は右端に 1 に変換して置いておく
keep の外にある 1 は keep 区間の 0 が連続している領域 においておく
この操作によって、すべて 0 に揃えられることがわかります。
これより少ない操作回数はどうやってもできず、この回数が答えになります。
最長の 0 の区間の求め方、は しゃくとり法のように求めればよいです。 計算量
$ O(T + N)
新たな学び
「すべて 0 にするとき、 1 は最低でも 1 回は操作しないといけない」など部分的な性質を明らかにしていく
反省点
コード
code: cpp
func Reverse(s string) string {
r := make([]rune, len(s))
for i := 0; i < len(s); i++ {
} else {
}
}
return string(r)
}
func solve() {
T := mio.NextInt()
solve := func() {
N, S := mio.NextInt(), mio.NextLine()
ans := 1_000_000_000
for q := 0; q < 2; q++ {
S = Reverse(S)
// mio.PrintLn(S)
l, r := -1, -1
for i, j := 0, 0; i < N; i = j {
j++
}
if Si == '0' && (l == -1 || (j-i) > (r-l)) { l, r = i, j
}
// mio.PrintLn(i, j, l, r)
}
if l == -1 {
continue
}
cost := 0
for i := 0; i < l; i++ {
cost++
cost++
}
}
for i := r; i < N; i++ {
cost++
cost++
}
}
// mio.PrintLn(cost, S, l, r)
if cost < ans {
ans = cost
}
}
mio.PrintLn(ans)
}
for t := 0; t < T; t++ {
solve()
}
}