差分
このページの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:// | [[https:// | ||
* [[https:// | * [[https:// | ||
+ | |||
+ | コンテスト前のすいみんはだいじ。 | ||
===== A - Limited Insertion ===== | ===== A - Limited Insertion ===== | ||
行 12: | 行 14: | ||
* 数列 $b_1, | * 数列 $b_1, | ||
- | * 空の配列 $a$ に以下の操作を $N$ 回繰り返して $b$ と同じにできるか判定し、可能なら操作手順を示せ | + | * 空の数列 $a$ に以下の操作を $N$ 回繰り返して数列 |
* $i$ 番目の操作では、$1 \le j \le i$ なる $j$ を1つ選び、$a$ の $j$ 番目に整数 $j$ を挿入する | * $i$ 番目の操作では、$1 \le j \le i$ なる $j$ を1つ選び、$a$ の $j$ 番目に整数 $j$ を挿入する | ||
* $1 \le N \le 100$ | * $1 \le N \le 100$ | ||
行 26: | 行 28: | ||
最後に挿入した数字は、$a_i=i$ となっているはずである。 | 最後に挿入した数字は、$a_i=i$ となっているはずである。 | ||
- | そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作しないと困ったことになる。 | + | そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作したことにしないと矛盾が発生する。 |
i | i | ||
- | a | + | a |
| | ||
i=3を最後に操作したことにすると、1つ前の状態は | i=3を最後に操作したことにすると、1つ前の状態は | ||
行 85: | 行 87: | ||
==== 解法 ==== | ==== 解法 ==== | ||
- | なんかこういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。 | + | 自身の頂点の和を調整するために、ある辺を無くすと、その相手の和にも影響してしまうため、考え出すとこんがらがる。 |
+ | |||
+ | こういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。 | ||
1 2 3 | 1 2 3 | ||
行 97: | 行 101: | ||
ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。 | ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。 | ||
- | 自身に対する辺のみが無いので、頂点 $v$ に隣接する頂点の和は $S-v$ となる。 | + | 自身に対する辺のみが無いので、このままでは頂点 $v$ に隣接する頂点の和は $S-v$ となる。 |
ここで、ペアへの辺を1本だけ無くすと、$S-T$ となり、これは全ての頂点で同じとなる。 | ここで、ペアへの辺を1本だけ無くすと、$S-T$ となり、これは全ての頂点で同じとなる。 | ||
行 103: | 行 107: | ||
==$N$ が奇数の場合== | ==$N$ が奇数の場合== | ||
- | $T=N$ (頂点 $N$ だけぼっち)となるので、上記と同様に構築すると、完全グラフの時点で頂点 $N$ は $S-v=S-T$ となり、他の頂点と等しくなっている。 | + | $T=N$ とする。頂点 $N$ だけぼっちとなる。上記と同様に構築すると、完全グラフの時点で頂点 $N$ に隣接する頂点の和は $S-T$ となり、他の頂点と等しくなっている。 |
<sxh python> | <sxh python> | ||
行 222: | 行 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 | ||
+ | , | ||
+ | p 1 5 3 4 7 6 2 9 8 | ||
+ | ↓ , | ||
+ | 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 | ||
+ | , | ||
+ | p 1 | ||
+ | , | ||
+ | p 1 2 5 3 4 7 6 9 8 | ||
+ | | ||
+ | p 1 2 3 4 5 | ||
+ | ... | ||
+ | |||
+ | ので、元のindexに加えて区間にも通し番号を付ける。これを $x$ とする。 | ||
+ | |||
+ | i 1 | ||
+ | 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 | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | |||
+ | $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+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+1][y+1] &= DP[k][y]+A & (y=odd) | ||
+ | \end{array} \right. | ||
+ | $$ | ||
+ | |||
+ | ■DPの遷移と、各状態が示す暫定数列の一例 | ||
+ | [サンプル5] | ||
+ | 9 40 50 | ||
+ | 5 3 4 7 6 1 2 9 8 | ||
+ | i 1 | ||
+ | x 0 )1( 2 )3( 4 )5( 6 )7( 8 )9( 10 )11( 12 )13( 14 )15( 16 )17( 18 | ||
+ | 初期p | ||
+ | " | ||
+ | ・y=0 | ||
+ | ・動かさない DP[1][11] = 0 1 | ||
+ | ・動かす | ||
+ | | ||
+ | " | ||
+ | ・y= 0 の場合 (cost=50) | ||
+ | ・動かさない DP[2][13] = 50 1 2 | ||
+ | ・動かす | ||
+ | ・y=11 の場合 (cost=0) | ||
+ | ・動かさない DP[2][13] = | ||
+ | ・動かす | ||
+ | | ||
+ | " | ||
+ | ・y= 0 の場合 (cost=100) | ||
+ | ・動かさない DP[3][ 3] = 100 1 2 3 | ||
+ | ・動かす | ||
+ | ・y=12 の場合 (cost=50) | ||
+ | ・必ず動かす DP[3][12] = 90 | ||
+ | ・y=13 の場合 (cost=0) | ||
+ | ・必ず動かす DP[3][14] = 40 | ||
+ | |||
+ | こんな感じで、直前の数字の位置のみを状態として、DPを遷移できる。 | ||
+ | |||
+ | さて、ここまでの考察で、区間は「indexちょうど」と「その間」で分けたが、今回のように小さい方から確定させていけるDPの場合、半開区間で持ってもよい。区間数が半分になり、定数倍の高速化になる。 | ||
+ | |||
+ | i 1 | ||
+ | x 0 )[ 1 )[ 2 )[ 3 )[ 4 )[ 5 )[ 6 )[ 7 )[ 8 )[ 9 | ||
+ | |||
+ | $k$ の位置が $y$ なら、$y$ の実態が整数座標でも小数座標でも、$k+1$ が挿入できる最も左の位置は $y$ である。 | ||
+ | |||
+ | 大きい方から見る場合は開区間と閉区間を逆にする。大小両方から見る必要があるような場合は、やはりindexちょうどとその間は区別する必要がある。 | ||
+ | |||
+ | ====別解法==== | ||
+ | |||
+ | * [[https:// | ||
+ | |||
+ | グラフを作って最短経路で解く。 | ||
+ | |||
+ | 通過する頂点は、位置を変化させない数字。通過しない頂点の位置を変化させる。 | ||
+ | |||
+ | 通過する頂点の位置を変化させないために、その間で前や後ろに持っていく必要のある数字の移動コストが、辺のコストになる。 | ||
+ | |||
+ | <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, | ||
+ | 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, | ||
+ | remain = iter(dp[s: | ||
+ | for j, cost in remain: | ||
+ | if stay_cost > cost + a: | ||
+ | ndp.append((j, | ||
+ | break | ||
+ | ndp.extend((j, | ||
+ | dp = ndp | ||
+ | print(dp[-1][1]) | ||
+ | </ | ||
+ | |||
+ | |||
+ | ===== E - Modulo Pairing ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * 正整数 $M$ がある | ||
+ | * $2N$ 個の整数 $a_1, | ||
+ | * これを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 | ||
+ | ,---------, | ||
+ | | , | ||
+ | 0 2 3 4 5 9 | ||
+ | `-----' | ||
+ | |||
+ | 仮に、$\mod{M}$ の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。(解説pdfの、青色同士の組み替え参照) | ||
+ | |||
+ | でもこの問題だと $X=9$ になり、$M=10$ なのであまり有効そうではない。$\mod{M}$ を有効活用したい。 | ||
+ | |||
+ | ,-----, | ||
+ | | ,-, | ,-, | ||
+ | 0 2 3 4 5 9 | ||
+ | |||
+ | 1つ大きい数字同士でペアを作ってから、残ったもので大小組み合わせると、$X=5$ となり、サンプルの出力例と一致する。 | ||
+ | 適切なペアはこんな感じになるようだ。 | ||
+ | ただ $N$ が少なすぎて、どういう風に一般化すればいいか、まだ決めづらい。 | ||
+ | |||
+ | ところで、各数字は $0 \le a_i \lt M$ なので、2つ足しても $2M$ を超えることはない。「和が $M$ を超えるペア」のスコアは必ず「2数の和$-M$」である。つまり、「和が $M$ を超えるペア」同士の間では、2数の和がそのまま大小比較に使える。 | ||
+ | |||
+ | なので「和が $M$ 未満のペアに使われる数字」「$M$ 以上のペアに使われる数字」に分類した際、その中での適切なペアの作り方は、やはり大きいのと小さいのを組み合わせる方針である。 | ||
+ | |||
+ | ※a~hはソート済み | ||
+ | , | ||
+ | | , | ||
+ | M未満 | ||
+ | M以上 | ||
+ | | ||
+ | | ||
+ | |||
+ | ここから、分類を組み替えることで、より $X$ を小さく出来ないか考える。 | ||
+ | |||
+ | こんなペア(左)があった時、こうする(右)と、 | ||
+ | |||
+ | , | ||
+ | M未満 | ||
+ | M以上 | ||
+ | | ||
+ | ペア | ||
+ | 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未満 | ||
+ | M以上 | ||
+ | | ||
+ | a + d > | ||
+ | a + d > | ||
+ | | ||
+ | , | ||
+ | M未満 | ||
+ | M以上 | ||
+ | `--------' | ||
+ | b + c > | ||
+ | b + c > | ||
+ | |||
+ | なので、これを繰り返すと、和が $M$ 未満グループを左、$M$ 以上グループを右に寄せてしまってよいことがわかる。 | ||
+ | |||
+ | ,--------, | ||
+ | | ,--, | | ||
+ | M未満 | ||
+ | M以上 | ||
+ | | `--' | ||
+ | `--------' | ||
+ | |||
+ | 残る問題は、 | ||
+ | |||
+ | * この分類が正しいのか(実際に$b+c$はちゃんと$M$未満か?) | ||
+ | * 正しい分類が複数ある場合、どれが最小なのか | ||
+ | |||
+ | 2番目の問題から考える。 | ||
+ | |||
+ | 変化させられるのは、$M$ 未満と以上のペアの個数である。個数を決めればペアは決まる。仮に $M$ 未満の個数を1減らしてみる。 | ||
+ | |||
+ | ,--, | ||
+ | M未満 | ||
+ | M以上 | ||
+ | | | `--' | ||
+ | | `--------' | ||
+ | `--------------' | ||
+ | | ||
+ | 変化前と変化後で、変化後の全てのペアのスコアが、変化前のいずれかのスコア以下、ということが言えれば、$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, | ||
+ | |||
+ | 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) | ||
+ | </ |