差分

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

--- programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/03/23] – ikatakos
+++ programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/04/19] – ikatakos
@@ 行 1: / 行 1: @@
-======AtCoder Grand Contest 032 A,B,C 問題メモ======
+======AtCoder Grand Contest 032 A～E 問題メモ======
 [[https://beta.atcoder.jp/contests/agc032|AtCoder Grand Contest 032]]
@@ 行 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>
@@ 行 224: / 行 226: @@
 ==== 解法 ====
-最小カットで解く方法は分かったけど、辺数が多くなりすぎるためTLE。
+最小カットで解く方法はありそうだけど、辺数が多くなりすぎるためTLE。（数字の大小が入れ替わっている場所では、小を右に持っていくか、大を左に持っていくか、少なくともどちらかは実行しなければならない、というのに見立てたグラフを作る）
-FIXME
+解説pdfによると、DP。
+この問題が行っているのは要は挿入ソートであり、最終的な順番のみが大事な挿入ソート系の問題では、途中段階において厳密なindexを考慮する必要は無い。「indexの間」にも入れられると考える方法がある。
+  【こういう風に、毎回indexを定義しなおさなくてもよい】
+  i  1  2  3  4  5  6  7  8  9
+  p  5  3  4  7  6  1  2  9  8
+     ,--------------'           1を左へ
+  p  1  5  3  4  7  6  2  9  8
+  ↓    ,--------------'        2を左へ
+  p  1  2  5  3  4  7  6  9  8
+  ...
+  【indexの間の位置も許して挿入すると考えてよい】
+  i      1      2      3      4      5      6      7      8      9
+  p      5      3      4      7      6      1      2      9      8
+     ,--------------------------------------'                         1を左へ
+  p  1   5      3      4      7      6             2      9      8
+       ,-------------------------------------------'                  2を左へ
+  p  1 2 5      3      4      7      6                    9      8
+         `----------------,                                           5を右へ
+  p  1 2        3      4  5   7      6                    9      8
+  ...
+ので、元のindexに加えて区間にも通し番号を付ける。これを  $x$  とする。
+  i      1     2     3     4     5       6       7       8       9
+  x   0 )1( 2 )3( 4 )5( 6 )7( 8 )9( 10 )11( 12 )13( 14 )15( 16 )17( 18
+括弧内は両端を含まないその間の任意の位置、括弧外はもともとの  $i$  ちょうどの位置を示す。
+各数字の初期位置は括弧外であり、数字の移動では必ず括弧内に挿入する。
+同じ括弧内の区間に入った数字同士は、昇順になるように自由に並び替えられるとしてよい。
+（括弧内に入っている数字は全て操作によって動かされた数字であり、操作では好きな箇所へ挿入できる）
+こうすることで、 $p_i$  を小さい方から順に、ソートされた状態を保ちながら挿入していくDPが可能になる。
+ $DP[k][x]$ :  $p_i=1～k$  まで考えて、 $k$  の位置が  $x$  だった場合の、最小コスト
+  * 初期化:  $DP[0][0]=0$
+  * 答え:  $\min(DP[N])$
+ $p_i$  の小さい順に挿入していくことで、DPで保持すべき状態が、1つ前の数字の位置だけで良くなる。（それより左の数字の並びがどうなっていようと、どうせそこには挿入しないので気にしなくてよい）
+  k=5  x=8
+  x  0  1  2 ...... 8  9
+     ~~~~~~~~~~~~~~ 5
+～4がどこかで |→ 6の挿入は5より右なので
+     この順に並ぶ   |   1～4の位置は考慮しなくてよい
+ $k→k+1$  の遷移は、「 $k$  の移動後の位置  $y$ 」と「 $k+1$  が最初に存在していた位置  $z$ 」の大小関係によって決まる。
+==  $y < z$  の場合==
+ $k+1$  は動かさなくても昇順を保てる。
+ $DP[k+1][z] = DP[k][y]$
+ただ、この後の数字の位置関係によっては動かしておいた方が最小的なコストが小さくなるかも知れない。その場合、出来るだけ左に寄せておいた方がよい。
+ $k+1$  が移動できる最も左の位置は、 $y$  が括弧内の場合  $y$ 、 $y$  が初期位置の場合、 $y+1$  となる。
+$$
+  \left\{ \begin{array}{ll}
+    DP[k+1][y]   &= DP[k][y]+B & (y=even) \\
+    DP[k+1][y+1] &= DP[k][y]+B & (y=odd)
+  \end{array} \right.
+$$
+==  $y > z$  の場合==
+昇順を保つため、 $k+1$  は必ず右に動かす必要がある。この場合の挿入位置も出来るだけ左、つまり  $y$  のすぐ右でよい。
+$$
+  \left\{ \begin{array}{ll}
+    DP[k+1][y]   &= DP[k][y]+A & (y=even) \\
+    DP[k+1][y+1] &= DP[k][y]+A & (y=odd)
+  \end{array} \right.
+$$
+  ■DPの遷移と、各状態が示す暫定数列の一例
+  [サンプル5]
+40 50
+3 4 7 6 1 2 9 8
+                                i      1     2     3     4     5       6       7       8       9
+                                x   0 )1( 2 )3( 4 )5( 6 )7( 8 )9( 10 )11( 12 )13( 14 )15( 16 )17( 18
+                            初期p      5     3     4     7     6       1       2       9       8
+  "1" は、初期位置 z=11 に存在         |     |     |     |     |       1       |       |       |
+  ・y=0
+    ・動かさない DP[1][11] =  0                                        1
+    ・動かす     DP[1][ 0] = 50     1
+  "2" は、初期位置 z=13 に存在         |     |     |     |     |       |       2       |       |
+  ・y= 0 の場合 (cost=50)
+    ・動かさない DP[2][13] =  50    1                                          2
+    ・動かす     DP[2][ 0] = 100   1 2
+  ・y=11 の場合 (cost=0)
+    ・動かさない DP[2][13] =   0                                       1       2
+    ・動かす     DP[2][12] =  50                                       1   2
+  "3" は、初期位置 z=3 に存在          |     3     |     |     |       |       |       |       |
+  ・y= 0 の場合 (cost=100)
+    ・動かさない DP[3][ 3] = 100   1 2       3
+    ・動かす     DP[3][ 0] = 150   123
+  ・y=12 の場合 (cost=50)
+    ・必ず動かす DP[3][12] =  90                                       1  2 3
+  ・y=13 の場合 (cost=0)
+    ・必ず動かす DP[3][14] =  40                                       1       2   3
+こんな感じで、直前の数字の位置のみを状態として、DPを遷移できる。
+さて、ここまでの考察で、区間は「indexちょうど」と「その間」で分けたが、今回のように小さい方から確定させていけるDPの場合、半開区間で持ってもよい。区間数が半分になり、定数倍の高速化になる。
+  i      1     2     3     4     5     6     7     8     9
+  x   0 )[  1 )[  2 )[  3 )[  4 )[  5 )[  6 )[  7 )[  8 )[  9
+ $k$  の位置が  $y$  なら、 $y$  の実態が整数座標でも小数座標でも、 $k+1$  が挿入できる最も左の位置は  $y$  である。
+大きい方から見る場合は開区間と閉区間を逆にする。大小両方から見る必要があるような場合は、やはりindexちょうどとその間は区別する必要がある。
+====別解法====
+  * [[https://twitter.com/ngtakana/status/1109627547136909313/photo/1|ながたかな（長田歌菜）さんのツイート: "Dはこんな感じで解きました！（伝われ） 細かい説明を全部すっ飛ばしてしまうと、この上の最短経路長（この場合220）が答えです。このグラフは直積順序のハッセ図で作っていて、ラベルはその間の数を適宜左か右に出すためのコストです。うーん、伝わるかなぁ……… https://t.co/eLuyszZVwO"]]
+グラフを作って最短経路で解く。
+通過する頂点は、位置を変化させない数字。通過しない頂点の位置を変化させる。
+通過する頂点の位置を変化させないために、その間で前や後ろに持っていく必要のある数字の移動コストが、辺のコストになる。
+<sxh python>
+from bisect import bisect
+n, a, b = map(int, input().split())
+ppp = map(int, input().split())
+qqq = [0] * n
+for i, p in enumerate(ppp, start=1):
+    qqq[p - 1] = i
+dp = [(0, 0)]
+for i in qqq:
+    s = bisect(dp, (i,))
+    ndp = [(j, cost + b) for j, cost in dp[:s]]
+    stay_cost = dp[s - 1][1]
+    ndp.append((i, stay_cost))
+    remain = iter(dp[s:])
+    for j, cost in remain:
+        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])
+</sxh>
+===== E - Modulo Pairing =====
+[[https://beta.atcoder.jp/contests/agc032/tasks/agc032_e|E - Modulo Pairing]]
+==== 問題 ====
+  * 正整数  $M$  がある
+  *  $2N$  個の整数  $a_1,a_2,...,a_{2N}$  があり、全て  $0 \le a_i \lt M$
+  * これを2つずつ組み合わせて  $N$  個のペアを作る
+  * ペアの数字をそれぞれ  $x,y$  として、「 $(x+y) \mod{M}$  の、 $N$  個のペアの中での最大値」を $X$ とする
+  *  $X$  が最小となるようにペアを作ったときの  $X$  の値を求めよ
+  *  $1 \le N \le 10^5$
+  *  $1 \le M \le 10^9$
+==== 解法 ====
+解説pdfを読んだら理解と実装は比較的簡単だが……発想の飛躍が……
+===いろいろ試す===
+最大値をなるべく低く抑えるということは、ペアの合計を均等にした方が良さそうなので、大きいのと小さいのを組み合わせる方向性が思いつく。
+  M=10
+  ,---------,
+  |   ,-,   |
+2 3 4 5 9
+    `-----'
+仮に、 $\mod{M}$  の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。（解説pdfの、青色同士の組み替え参照）
+でもこの問題だと  $X=9$  になり、 $M=10$  なのであまり有効そうではない。 $\mod{M}$  を有効活用したい。
+  ,-----,
+  | ,-, | ,-,
+2 3 4 5 9
+つ大きい数字同士でペアを作ってから、残ったもので大小組み合わせると、 $X=5$  となり、サンプルの出力例と一致する。
+適切なペアはこんな感じになるようだ。
+ただ  $N$  が少なすぎて、どういう風に一般化すればいいか、まだ決めづらい。
+ところで、各数字は  $0 \le a_i \lt M$  なので、2つ足しても  $2M$  を超えることはない。「和が  $M$  を超えるペア」のスコアは必ず「2数の和 $-M$ 」である。つまり、「和が  $M$  を超えるペア」同士の間では、2数の和がそのまま大小比較に使える。
+なので「和が  $M$  未満のペアに使われる数字」「 $M$  以上のペアに使われる数字」に分類した際、その中での適切なペアの作り方は、やはり大きいのと小さいのを組み合わせる方針である。
+  ※a～hはソート済み
+          ,--------------,
+          |     ,--,     |
+  M未満   a     c  d     f
+  M以上      b        e     g  h
+             |        `-----'  |
+             `-----------------'
+ここから、分類を組み替えることで、より  $X$  を小さく出来ないか考える。
+こんなペア（左）があった時、こうする（右）と、
+          ,-----,             ,--,
+  M未満   a     c       →    a  b
+  M以上      b     d    →          c  d
+             `-----'                `--'
+  ペア    a + c               a + b
+          b + d - M           c + d - M
+  *  $a+c$  で  $M$  未満なのだから、 $a+b$  は  $M$  未満
+  *  $b+d$  で  $M$  以上なのだから、 $c+d$  は  $M$  以上
+よって、組み替えた後も  $M$ 未満/以上という分類は成立している。
+また、 $a+c \ge a+b$ 、 $b+d \ge c+d$  が成り立つので、最終的な  $X$  の値も  $X_左 \ge X_右$  となり、常に改善される。
+他のケースも、考えていくと同じ事が言える。
+          ,--------,          ,--,
+  M未満   a        d    →    a  b
+  M以上      b  c       →          c  d
+             `--'                   `--'
+          a + d         >=    a + b
+          a + d         >     c + d - M  (=  d + (c - M)  =  d + 負)
+             ,--,             ,--,
+  M未満      b  c       →    a  b
+  M以上   a        d    →          c  d
+          `--------'                `--'
+          b + c         >=    a + b
+          b + c         >     c + d - M  (=  c + 負)
+なので、これを繰り返すと、和が  $M$  未満グループを左、 $M$  以上グループを右に寄せてしまってよいことがわかる。
+          ,--------,
+          |  ,--,  |
+  M未満   a  b  c  d
+  M以上               e  f  g  h
+                      |  `--'  |
+                      `--------'
+残る問題は、
+  * この分類が正しいのか（実際に $b+c$ はちゃんと $M$ 未満か？）
+  * 正しい分類が複数ある場合、どれが最小なのか
+番目の問題から考える。
+変化させられるのは、 $M$  未満と以上のペアの個数である。個数を決めればペアは決まる。仮に  $M$  未満の個数を1減らしてみる。
+          ,--,
+  M未満   a  b
+  M以上         c  d  e  f  g  h
+                |  |  `--'  |  |
+                |  `--------'  |
+                `--------------'
+変化前と変化後で、変化後の全てのペアのスコアが、変化前のいずれかのスコア以下、ということが言えれば、 $X$  は変化後の方が小さいと言える。そしてそれは実際に言える。
+  変化前          変化後
+  a + d      >=   a + b
+  e + h - M  >=   c + h - M
+  f + g - M  >=   d + g - M
+  f + g - M  >=   e + f - M
+よって、分類が正しく成立してるなら、 $M$  未満の個数はなるべく少ない方がよいと言える。
+（厳密にやるなら、項数  $N$  や変化前後の分類の個数について一般化する必要があるが）
+分類が成立するという前提のもと、 $M$  未満の個数が最も少ない境界を、2分探索で求める。
+<sxh python>
+def check(k):
+    ret = 0
+    b = 2 * k - 1
+    for j in range(k):
+        t = aaa[j] + aaa[b - j]
+        if t >= m:
+            return -1
+        ret = max(ret, t)
+    b = 2 * k
+    c = 2 * n - 1
+    for j in range(n - k):
+        t = aaa[b + j] + aaa[c - j]
+        if t < m:
+            return -2
+        ret = max(ret, t - m)
+    return ret
+n, m = map(int, input().split())
+aaa = sorted(map(int, input().split()))
+l, r = 0, n
+ans = -1
+while l < r:
+    mid = (l + r) // 2
+    res = check(mid)
+    if res == -1:
+        r = mid
+    elif res == -2:
+        l = mid + 1
+    else:
+        ans = res
+        r = mid
+if ans == -1:
+    ans = check(n)
+print(ans)
+</sxh>