差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:1104_agc040 [2019/11/05] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:1104_agc040 [2019/11/05] (現在) – [解法] ikatakos | ||
---|---|---|---|
行 3: | 行 3: | ||
[[https:// | [[https:// | ||
- | 深夜開催で参加者数が少なくなるかと思いきや、(多少は少ないが)そうでもなかった。みんなげんき。 | + | * [[https:// |
+ | |||
+ | 深夜開催で参加者数が少なくなるかと思いきや、そこまででもなかった。みんなげんき。 | ||
===== A - >< ===== | ===== A - >< ===== | ||
行 234: | 行 236: | ||
そういうわけで、岩盤1文字の削りに爆薬1文字必要なので、1箇所の岩盤を削除するには、その長さと同数の爆薬が最低限必要である。 | そういうわけで、岩盤1文字の削りに爆薬1文字必要なので、1箇所の岩盤を削除するには、その長さと同数の爆薬が最低限必要である。 | ||
- | ただし、ABAABABAのように、AとBを組み替えた岩盤はもう一方にとっての爆薬になり得る。 | + | ただし、ABA|ABABAのように、AとBを組み替えた岩盤はもう一方にとっての爆薬になり得る。 |
しかし、ABABCBAB → ABABAB のように、初期状態では離れていても「$S$ の先頭から数えて奇数番目がA, | しかし、ABABCBAB → ABABAB のように、初期状態では離れていても「$S$ の先頭から数えて奇数番目がA, | ||
行 241: | 行 243: | ||
それ以外の文字で爆薬が、岩盤の長さと同数必要。 | それ以外の文字で爆薬が、岩盤の長さと同数必要。 | ||
爆薬は、indexが奇数番目(Bと組になるもの)ならA以外、偶数番目(Aと組になるもの)ならB以外なら何でもよいので、1箇所につき2通りずつの選択肢がある。 | 爆薬は、indexが奇数番目(Bと組になるもの)ならA以外、偶数番目(Aと組になるもの)ならB以外なら何でもよいので、1箇所につき2通りずつの選択肢がある。 | ||
+ | (奇数番目がAの岩盤の場合) | ||
+ | |||
+ | 常にindexの偶奇は不変なので、奇数番目がAの岩盤を考えている間、ある瞬間に岩盤の' | ||