差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/04/19] – ikatakos
+++ programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/04/21] – ikatakos
@@ 行 14: / 行 14: @@
   * 数列 $b_1,b_2,...,b_N$ がある
-  * 空の配列 $a$ に以下の操作を $N$ 回繰り返して $b$ と同じにできるか判定し、可能なら操作手順を示せ
+  * 空の数列 $a$ に以下の操作を $N$ 回繰り返して数列 $b$ と同じにできるか判定し、可能なら操作手順を示せ
     * $i$ 番目の操作では、$1 \le j \le i$ なる $j$ を1つ選び、$a$ の $j$ 番目に整数 $j$ を挿入する
   * $1 \le N \le 100$
@@ 行 28: / 行 28: @@
 最後に挿入した数字は、$a_i=i$ となっているはずである。
-そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作しないと困ったことになる。
+そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作したことにしないと矛盾が発生する。
   i   1   2   3   4   5
-  a   1   1   3   2   5   → 1,3,5 が i = ai となっている
+  a   1   1   3   2   5   → 1,3,5 が i = ai となっている。このどれかが最後に挿入された
   i=3を最後に操作したことにすると、1つ前の状態は
@@ 行 87: / 行 87: @@
 ==== 解法 ====
-なんかこういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。
+自身の頂点の和を調整するために、ある辺を無くすと、その相手の和にも影響してしまうため、考え出すとこんがらがる。
+こういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。
   １  ２  ３
@@ 行 99: / 行 101: @@
 ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。
-自身に対する辺のみが無いので、頂点 $v$ に隣接する頂点の和は $S-v$ となる。
+自身に対する辺のみが無いので、このままでは頂点 $v$ に隣接する頂点の和は $S-v$ となる。
 ここで、ペアへの辺を1本だけ無くすと、$S-T$ となり、これは全ての頂点で同じとなる。
@@ 行 105: / 行 107: @@
 ==$N$ が奇数の場合==
-$T=N$ （頂点 $N$ だけぼっち）となるので、上記と同様に構築すると、完全グラフの時点で頂点 $N$ は $S-v=S-T$ となり、他の頂点と等しくなっている。
+$T=N$ とする。頂点 $N$ だけぼっちとなる。上記と同様に構築すると、完全グラフの時点で頂点 $N$ に隣接する頂点の和は $S-T$ となり、他の頂点と等しくなっている。
 <sxh python>
@@ 行 232: / 行 234: @@
   【こういう風に、毎回indexを定義しなおさなくてもよい】
   i  1  2  3  4  5  6  7  8  9
   p  5  3  4  7  6  1  2  9  8
      ,--------------'           1を左へ
@@ 行 355: / 行 358: @@
 グラフを作って最短経路で解く。
-通過する頂点は、位置を変化させない数字。通過しない頂点は、位置を変化させる。
+通過する頂点は、位置を変化させない数字。通過しない頂点の位置を変化させる。
 通過する頂点の位置を変化させないために、その間で前や後ろに持っていく必要のある数字の移動コストが、辺のコストになる。
 <sxh python>
-from collections import defaultdict
+from bisect import bisect
-from operator import itemgetter
 n, a, b = map(int, input().split())
-ppp = list(map(int, input().split()))
+ppp = map(int, input().split())
-qqq = list(map(itemgetter(0), sorted(enumerate(ppp, start=1), key=itemgetter(1))))
+qqq = [0] * n
+for i, p in enumerate(ppp, start=1):
+    qqq[p - 1] = i
-dp = {0: 0}
+dp = [(0, 0)]
 for i in qqq:
-    ndp = defaultdict(lambda: 10 ** 18)
+    s = bisect(dp, (i,))
-    for j, cost in dp.items():
+    ndp = [(j, cost + b) for j, cost in dp[:s]]
-        if j < i:
+    stay_cost = dp[s - 1][1]
-            ndp[i] = min(ndp[i], cost)
+    ndp.append((i, stay_cost))
-            ndp[j] = min(ndp[j], cost + b)
+    remain = iter(dp[s:])
-        else:
+    for j, cost in remain:
-            ndp[j] = min(ndp[j], cost + a)
+        if stay_cost > cost + a:
+            ndp.append((j, cost + a))
+            break
+    ndp.extend((j, cost + a) for j, cost in remain)
     dp = ndp
+print(dp[-1][1])
-print(min(dp.values()))
 </sxh>
@@ 行 389: / 行 395: @@
   * 正整数 $M$ がある
-  * $2N$ 個の整数 $a_1,a_2,...,a_{2N}$ があり、全て $0 \le a_i \lt M$
+  * $2N$ 個の、$0 \le a_i \lt M$ の整数 $a_1,a_2,...,a_{2N}$ がある
-  * これを2つずつ組み合わせて $N$ 個のペアを作る
+    * これを2つずつ組み合わせて $N$ 個のペアを作る
-  * ペアの数字をそれぞれ $x,y$ として、「$(x+y) \mod{M}$ の、$N$ 個のペアの中での最大値」を$X$とする
+  * ペアの「醜さ」を、ペアの数字をそれぞれ $x,y$ として、$(x+y) \mod{M}$ とする
-  * $X$ が最小となるようにペアを作ったときの $X$ の値を求めよ
+  * $N$ 個のペアの中での醜さの最大値を $Z$ とする
+  * $Z$ が最小となるようにペアを作ったときの値を求めよ
   * $1 \le N \le 10^5$
   * $1 \le M \le 10^9$
@@ 行 398: / 行 405: @@
 ==== 解法 ====
-解説pdfを読んだら理解と実装は比較的簡単だが……発想の飛躍が……
+解説pdfを読んだら理解と実装は比較的簡単だが、考察の時点で結構地道なパターン分けが必要。
 ===いろいろ試す===
@@ 行 404: / 行 411: @@
 最大値をなるべく低く抑えるということは、ペアの合計を均等にした方が良さそうなので、大きいのと小さいのを組み合わせる方向性が思いつく。
-  M=10
+  ,---------,  M=10
-  ,---------,
   |   ,-,   |
 2 3 4 5 9
     `-----'
-仮に、$\mod{M}$ の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。（解説pdfの、青色同士の組み替え参照）
+仮に、$\mod{M}$ の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。
-でもこの問題だと $X=9$ になり、$M=10$ なのであまり有効そうではない。$\mod{M}$ を有効活用したい。
+<WRAP>
+これを確認する。$a \le b \le c \le d$ として、ペアの組み方は3通りある。
+  A              B              C
+  ,--,        |  ,-----,     |  ,--------,
+  a  b  c  d  |  a  b  c  d  |  a  b  c  d
+        `--'  |     `-----'  |     `--'
+ある2通りのペアの組み方 $A,B$ があって、醜さの最大値の比較で $Z_A \le Z_B$ と言うためには、
+「$A$ の全てのペアについて、それぞれ、より醜さが大きいペアが $B$ に存在する」ということが言えればよい。
+すると、$C$ のペアは、
+  (C) a + d  <=  (A) c + d    (C) b + c  <=   (A) c + d
+  (C) a + d  <=  (B) b + d    (C) b + c  <=   (B) b + d
+となり、$A,B$ より醜さの最大値は小さくなることが分かる。
+もっとペアの数が増えても、上記のことを1つ1つ順に適用していくことで、最終的に「小さい方と大きい方から順に組み合わせていく」方針が最適となることが分かる。
+</WRAP>
+ただ、先ほどの例だと $Z=9$ になる。$M=10$ なので、答えとなり得る値の中で最大であり、そのまま適用するのはあまり有効そうではない。$\mod{M}$ を有効活用したい。
   ,-----,
@@ 行 424: / 行 452: @@
 ところで、各数字は $0 \le a_i \lt M$ なので、2つ足しても $2M$ を超えることはない。「和が $M$ を超えるペア」のスコアは必ず「2数の和$-M$」である。つまり、「和が $M$ を超えるペア」同士の間では、2数の和がそのまま大小比較に使える。
-なので「和が $M$ 未満のペアに使われる数字」「$M$ 以上のペアに使われる数字」に分類した際、その中での適切なペアの作り方は、やはり大きいのと小さいのを組み合わせる方針である。
+なので「和が $M$ 未満のペアに使われる数字」「$M$ 以上のペアに使われる数字」に分類した際、各分類の中での適切なペアの作り方は、やはり大きい方と小さい方から順に組み合わせる方針が適用できる。
-  ※a～hはソート済み
+  ※a～hは昇順にソート済み
           ,--------------,
           |     ,--,     |
@@ 行 434: / 行 462: @@
              `-----------------'
-ここから、分類を組み替えることで、より $X$ を小さく出来ないか考える。
+ここから、分類を組み替えることで、より $Z$ を小さく出来ないか考える。
 こんなペア（左）があった時、こうする（右）と、
@@ 行 448: / 行 476: @@
   * $b+d$ で $M$ 以上なのだから、$c+d$ は $M$ 以上
-よって、組み替えた後も $M$未満/以上の分類は正しい。
+よって、組み替えた後も $M$未満/以上という分類は成立している。
-また、$a+c \ge a+b$、$b+d \ge c+d$ が成り立つので、最終的な $X$ の値も $X_左 \ge X_右$ となり、常に改善される。
+また、$a+c \ge a+b$、$b+d \ge c+d$ が成り立つので、最終的な $Z$ の値も $Z_左 \ge Z_右$ となり、常に改善される。
 他のケースも、考えていくと同じ事が言える。
@@ 行 479: / 行 507: @@
 残る問題は、
-  * この分類が正しいのか（実際に$b+c$はちゃんと$M$未満か？）
+  * この分類が正しいのか（たとえば$b+c$は実際に$M$未満か？）
   * 正しい分類が複数ある場合、どれが最小なのか
-番目の問題から考える。
+番目の問題から考える。仮に $M$ 未満の個数を1減らしてみる。
-変化させられるのは、$M$ 未満と以上のペアの個数である。個数を決めればペアは決まる。仮に $M$ 未満の個数を1減らしてみる。
           ,--,
@@ 行 493: / 行 519: @@
                 `--------------'
-変化前と変化後で、変化後の全てのペアのスコアが、変化前のいずれかのスコア以下、ということが言えれば、$X$ は変化後の方が小さいと言える。そしてそれは実際に言える。
+$\mod{M}$ の条件を取り除いたときの考察と同様に、変化前と変化後で、変化後の全てのペアのスコアが、変化前のいずれかのスコア以下、ということが言いたい。
+そしてそれは実際に言える。
   変化前          変化後
@@ 行 502: / 行 529: @@
 よって、分類が正しく成立してるなら、$M$ 未満の個数はなるべく少ない方がよいと言える。
-（厳密にやるなら、項数 $N$ や変化前後の分類の個数について一般化する必要があるが）
+（厳密に証明するなら、項数 $N$ や変化前後の分類の個数について一般化する必要があるが）
-分類が成立するという前提のもと、$M$ 未満の個数が最も少ない境界を、2分探索で求める。
+分類が成立していて、$M$ 未満の個数が最も少ない境界を、2分探索で求める。
+$a_1,a_2,...$ をソート後、真ん中に境界を仮定して、分類の成立を調べる。
+  * 成立、$M$ 未満グループが不成立（和が $M$ 以上のペアが出来てしまう）なら左半分から境界を探索
+  * $M$ 以上グループが不成立（和が $M$ 未満のペアが出来てしまう）なら右半分から境界を探索
+両方のグループが同時に不成立となることは無い。仮に $M$ 未満グループから $a,b$、$M$ 以上グループから $c,d$ が不成立だったとすると、矛盾する。
+  小←        分類の境界       →大
+  ... a ... b ... | ... c ... d ...
+  ソート順: a <= b <= c <= d       =>  a+b <= c+d
+  成立条件: a + b >= M、c + d < M  =>  a+b >  c+d
 <sxh python>