差分
このページの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 - >< ===== | ||
行 93: | 行 95: | ||
貪欲に考えられる条件を見つけて境界を全探索。 | 貪欲に考えられる条件を見つけて境界を全探索。 | ||
- | グループの分け方が決まっているとすると、1つのグループの共通部分の長さは「グループ内の最小 $R_i$ - 最大 $L_i$ + 1」で求められる。 | + | 1つのグループの共通部分の長さは「グループ内の最小 $R_i$ - 最大 $L_i$ + 1」で求められる。 |
(ただし0未満にはならない) | (ただし0未満にはならない) | ||
行 129: | 行 131: | ||
として、配列アクセスだけで計算できる。 | として、配列アクセスだけで計算できる。 | ||
- | ===長い方から順=== | + | ===最も長い区間のみ単独グループ=== |
区間がまったくバラバラで、ろくに共通部分を持たない場合であっても、 | 区間がまったくバラバラで、ろくに共通部分を持たない場合であっても、 | ||
行 140: | 行 142: | ||
(最も長い区間が複数ある場合が不安だったり、似たような処理を書くのを省略するため、 | (最も長い区間が複数ある場合が不安だったり、似たような処理を書くのを省略するため、 | ||
- | 下記コードでは区切りを全探索するコードを再利用しているが、 | + | 下記コードでは区間の長さ順にソートした上で区切りを全探索するコードを再利用しているが、 |
実際はチェックするのは最も長い任意の1区間を1グループとする場合のみでよい) | 実際はチェックするのは最も長い任意の1区間を1グループとする場合のみでよい) | ||
行 149: | 行 151: | ||
「ソートして左右に分けるのが最適」であることを検証するにあたり、 | 「ソートして左右に分けるのが最適」であることを検証するにあたり、 | ||
- | 「ソートした結果、全体で最も右の区間が含まれる方をグループ2とした時、グループ1に含まれる最も右の区間」に着目することで、 | + | 「ソートした結果、全体の中で最も右の区間が含まれる方をグループ2とした時、グループ1に含まれる最も右の区間」を固定することで、 |
- | それぞれのグループ内最大 $L_i$ が固定される。 | + | それぞれのグループ内最大 $L_i$ が固定されるため、見えやすくなる。 |
- | さらに、最も長いのを単独でグループにする方法が、本当に単独でよいかも理解しやすい。 | + | さらに、ソートして分ける方法と、最も長い区間を単独グループにする方法の2つで、本当に網羅できているのかも理解できる。 |
<sxh python> | <sxh python> | ||
行 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の岩盤を考えている間、ある瞬間に岩盤の' | ||