AtCoderBeginnerContest329 E問題475点 「Stamp」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
気持ち
解法
これ難しいです(苦手)。
https://gyazo.com/84dd2eab40377cf1bbe0fc56423363a3
# だけからなる文字列 X があります。(上記の画像で T と書いてしまっていますが、正しくは X ですね。)
この # だけからなる文字列を自由に T の文字列で置き換えて、 S を構築します。
https://gyazo.com/d765d14137f054332f6a3031418e8a94
最初から文字列 $ Sと同じ文字列 $ Xができているとします。
そして、 文字列$ Tと同じ要素があったら、逆に ### に書き換える、をおこなってすべて ######## に変換していきます。
つまり、操作を逆に考えて、最終的に戻す文字列を ####### にします。
このとき、以下がいえます。
文字列 X を ### で置きかえるとき、i 文字目が # もしくは T[i] と一致すればよい
一度置き換えた場所を再度置き換える必要はない
よって、以下がいえます。
最初にすべての文字列 $ Xの位置 $ i から、 文字列 T があれば ### におきかえる
その後前後 $ M文字を確認して、もしさらに文字列 $ Tから ### に置き換えられそうなら queue に積む
という BFS をすればよい。
計算量
$ O(NM)
新たな学び
上書きするような操作は逆から行うべき
逆から操作を考える場合、「最終的な状態はなにか」「操作 A の真逆の操作はなにか」を分離して考えるべき
反省点
「逆から考える」を踏み込んで捉えていなかった
「逆」をかんがえれば、最終的な状態は ### であり、 ABC を ### に置き換えること と気づけた
コード
code: go
func solve() {
N, M := mio.NextInt(), mio.NextInt()
S, T := []rune(mio.NextLine()), []rune(mio.NextLine())
checked := make([]bool, N)
queue := make([]int, 0)
check := func(i int) bool {
return false
}
for j := 0; j < M; j++ {
return false
}
}
return true
}
push := func(i int) {
if check(i) {
queue = append(queue, i)
}
}
write := func(i int) {
for j := 0; j < M; j++ {
}
}
for i := 0; i < N-M+1; i++ {
push(i)
}
for len(queue) > 0 {
write(x)
for d := -M; d <= M; d++ {
p := x + d
if p >= 0 && p < N-M+1 {
push(p)
}
}
}
ans := N == strings.Count(string(S), "#")
if ans {
mio.PrintLn("Yes")
} else {
mio.PrintLn("No")
}
}