差分

このページの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://atcoder.jp/contests/agc040|AtCoder Grand Contest 040]]
-深夜開催で参加者数が少なくなるかと思いきや、（多少は少ないが）そうでもなかった。みんなげんき。
+  * [[https://www.youtube.com/watch?v=qIzuNgDV6O8|AtCoder Grand Contest 040 - YouTube]]
+深夜開催で参加者数が少なくなるかと思いきや、そこまででもなかった。みんなげんき。
 ===== A - >< =====
@@ 行 93: / 行 95: @@
 貪欲に考えられる条件を見つけて境界を全探索。
-グループの分け方が決まっているとすると、1つのグループの共通部分の長さは「グループ内の最小 $R_i$ - 最大 $L_i$ + 1」で求められる。
+つのグループの共通部分の長さは「グループ内の最小 $R_i$ - 最大 $L_i$ + 1」で求められる。
 （ただし0未満にはならない）
@@ 行 129: / 行 131: @@
 として、配列アクセスだけで計算できる。
-===長い方から順===
+===最も長い区間のみ単独グループ===
 区間がまったくバラバラで、ろくに共通部分を持たない場合であっても、
@@ 行 140: / 行 142: @@
 （最も長い区間が複数ある場合が不安だったり、似たような処理を書くのを省略するため、
-下記コードでは区切りを全探索するコードを再利用しているが、
+下記コードでは区間の長さ順にソートした上で区切りを全探索するコードを再利用しているが、
 実際はチェックするのは最も長い任意の1区間を1グループとする場合のみでよい）
@@ 行 149: / 行 151: @@
 「ソートして左右に分けるのが最適」であることを検証するにあたり、
-「ソートした結果、全体で最も右の区間が含まれる方をグループ2とした時、グループ1に含まれる最も右の区間」に着目することで、
+「ソートした結果、全体の中で最も右の区間が含まれる方をグループ2とした時、グループ1に含まれる最も右の区間」を固定することで、
-それぞれのグループ内最大 $L_i$ が固定される。
+それぞれのグループ内最大 $L_i$ が固定されるため、見えやすくなる。
-さらに、最も長いのを単独でグループにする方法が、本当に単独でよいかも理解しやすい。
+さらに、ソートして分ける方法と、最も長い区間を単独グループにする方法の2つで、本当に網羅できているのかも理解できる。
 <sxh python>
@@ 行 234: / 行 236: @@
 そういうわけで、岩盤1文字の削りに爆薬1文字必要なので、1箇所の岩盤を削除するには、その長さと同数の爆薬が最低限必要である。
-ただし、ABAABABAのように、AとBを組み替えた岩盤はもう一方にとっての爆薬になり得る。
+ただし、ABA|ABABAのように、AとBを組み替えた岩盤はもう一方にとっての爆薬になり得る。
 しかし、ABABCBAB → ABABAB のように、初期状態では離れていても「$S$ の先頭から数えて奇数番目がA, 偶数番目がB」が一致している2つの岩盤は、中間を削るとくっついてしまう。