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