差分
このページの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 | ||
|---|---|---|---|
| 行 395: | 行 395: | ||
| * 正整数 M がある | * 正整数 M がある | ||
| - | * 2N 個の整数 a1,a2,...,a2N があり、全て 0≤ai<M | + | * 2N 個の、0≤ai<M の整数 a1,a2,...,a2N がある |
| - | * これを2つずつ組み合わせて N 個のペアを作る | + | * これを2つずつ組み合わせて N 個のペアを作る |
| - | * ペアの数字をそれぞれ x,y として、「(x+y)modM | + | * ペアの「醜さ」を、ペアの数字をそれぞれ x,y として、(x+y)modM |
| - | * $X$ が最小となるようにペアを作ったときの X の値を求めよ | + | * N 個のペアの中での醜さの最大値を $Z$ とする |
| + | * $Z$ が最小となるようにペアを作ったときの値を求めよ | ||
| * 1≤N≤105 | * 1≤N≤105 | ||
| * 1≤M≤109 | * 1≤M≤109 | ||
| 行 404: | 行 405: | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| - | 解説pdfを読んだら理解と実装は比較的簡単だが……発想の飛躍が…… | + | 解説pdfを読んだら理解と実装は比較的簡単だが、考察の時点で結構地道なパターン分けが必要。 |
| - | + | ||
| - | ===いろいろ試す=== | + | |
| 最大値をなるべく低く抑えるということは、ペアの合計を均等にした方が良さそうなので、大きいのと小さいのを組み合わせる方向性が思いつく。 | 最大値をなるべく低く抑えるということは、ペアの合計を均等にした方が良さそうなので、大きいのと小さいのを組み合わせる方向性が思いつく。 | ||
| - | | + | , |
| - | | + | |
| | , | | , | ||
| 0 2 3 4 5 9 | 0 2 3 4 5 9 | ||
| `-----' | `-----' | ||
| - | 仮に、modM の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。（解説pdfの、青色同士の組み替え参照） | + | 仮に、modM の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。 |
| - | でもこの問題だと | + | <WRAP round box> |
| + | これを確認する。$a \le b \le c \le d$ として、ペアの組み方は3通りある。 | ||
| - | ,-----, | + | |
| - | | + | |
| - | | + | |
| + | `--' | ||
| - | 1つ大きい数字同士でペアを作ってから、残ったもので大小組み合わせると、$X=5$ となり、サンプルの出力例と一致する。 | + | ある2通りのペアの組み方 P,Q があって、醜さの最大値の比較で ZP≤ZQ と言うためには、 |
| - | 適切なペアはこんな感じになるようだ。 | + | 「P の全てのペアについて、それぞれ、より醜さが大きいペアが Q に存在する」ということが言えればよい。 |
| - | ただ | + | |
| + | すると、$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つ順に適用していくことで、最終的に「小さい方と大きい方から順に組み合わせていく」方針が最適となることが分かる。 | ||
| + | |||
| + | </ | ||
| + | |||
| + | ただ、modを含めて考えると、先ほどの例だと Z=9 になる。M=10 なので、答えとなり得る値の中で最大であり、そのまま適用するのはあまり有効そうではない。 | ||
| ところで、各数字は 0≤ai<M なので、2つ足しても 2M を超えることはない。「和が M を超えるペア」のスコアは必ず「2数の和−M」である。つまり、「和が M を超えるペア」同士の間では、2数の和がそのまま大小比較に使える。 | ところで、各数字は 0≤ai<M なので、2つ足しても 2M を超えることはない。「和が M を超えるペア」のスコアは必ず「2数の和−M」である。つまり、「和が M を超えるペア」同士の間では、2数の和がそのまま大小比較に使える。 | ||
| - | なので「和が M 未満のペアに使われる数字」「M 以上のペアに使われる数字」に分類した際、その中での適切なペアの作り方は、やはり大きいのと小さいのを組み合わせる方針である。 | + | なので「和が M 未満のペアに使われる数字」「M 以上のペアに使われる数字」に分類した際、各分類の中での適切なペアの作り方は、やはり大きい方と小さい方から順に組み合わせる方針が適用できる。 |
| - | ※a～hはソート済み | + | ※a～hは昇順にソート済み |
| , | , | ||
| | , | | , | ||
| 行 440: | 行 452: | ||
| | | ||
| - | ここから、分類を組み替えることで、より $X$ を小さく出来ないか考える。 | + | ここから、分類を組み替えることで、より $Z$ を小さく出来ないか考える。 |
| こんなペア（左）があった時、こうする（右）と、 | こんなペア（左）があった時、こうする（右）と、 | ||
| 行 451: | 行 463: | ||
| b + d - M c + d - M | b + d - M c + d - M | ||
| - | * a+c で M 未満なのだから、a+b は M 未満 | + | * (左) a+c で M 未満 |
| - | * b+d で M 以上なのだから、c+d は M 以上 | + | * (左) b+d で M 以上 |
| よって、組み替えた後も M未満/ | よって、組み替えた後も M未満/ | ||
| - | また、a+c≥a+b、b+d≥c+d が成り立つので、最終的な $Xの値もX_左 \ge X_右$ となり、常に改善される。 | + | また、$(左)a+c \ge (右)a+b、(左)b+d \ge (右)c+dが成り立つので、最終的なZの値もZ_左 \ge Z_右$ となり、常に改善される。 |
| 他のケースも、考えていくと同じ事が言える。 | 他のケースも、考えていくと同じ事が言える。 | ||
| 行 485: | 行 497: | ||
| 残る問題は、 | 残る問題は、 | ||
| - | * この分類が正しいのか（実際にb+cはちゃんとM未満か？） | + | * この分類が正しいのか（たとえばb+cは実際にM未満か？） |
| * 正しい分類が複数ある場合、どれが最小なのか | * 正しい分類が複数ある場合、どれが最小なのか | ||
| - | 2番目の問題から考える。 | + | 2番目の問題から考える。仮に M 未満の個数を1減らしてみる。 |
| - | + | ||
| - | 変化させられるのは、M 未満と以上のペアの個数である。個数を決めればペアは決まる。仮に M 未満の個数を1減らしてみる。 | + | |
| ,--, | ,--, | ||
| 行 499: | 行 509: | ||
| `--------------' | `--------------' | ||
| | | ||
| - | 変化前と変化後で、変化後の全てのペアのスコアが、変化前のいずれかのスコア以下、ということが言えれば、X は変化後の方が小さいと言える。そしてそれは実際に言える。 | + | modM の条件を取り除いたときの考察と同様に、変化前と変化後で、変化後の全てのペアのスコアが、変化前のいずれかのスコア以下、ということが言いたい。 |
| + | そしてそれは実際に言える。 | ||
| 変化前 | 変化前 | ||
| 行 508: | 行 519: | ||
| よって、分類が正しく成立してるなら、M 未満の個数はなるべく少ない方がよいと言える。 | よって、分類が正しく成立してるなら、M 未満の個数はなるべく少ない方がよいと言える。 | ||
| - | （厳密にやるなら、項数 N や変化前後の分類の個数について一般化する必要があるが） | + | （厳密に証明するなら、項数 N や変化前後の分類の個数について一般化する必要があるが） |
| - | 分類が成立するという前提のもと、M 未満の個数が最も少ない境界を、2分探索で求める。 | + | 分類が成立していて、M 未満の個数が最も少ない境界を、2分探索で求める。 |
| + | |||
| + | a1,a2,... をソート後、真ん中に境界を仮定して、分類の成立を調べる。 | ||
| + | |||
| + | * 成立、M 未満グループが不成立（和が M 以上のペアが出来てしまう）なら左半分から境界を探索 | ||
| + | * M 以上グループが不成立（和が M 未満のペアが出来てしまう）なら右半分から境界を探索 | ||
| + | |||
| + | 両方のグループが同時に不成立となることは無い。仮に M 未満グループから a,b、M 以上グループから c,d が不成立だったとすると、矛盾する。 | ||
| + | |||
| + | 小← | ||
| + | ... a ... b ... | ... c ... d ... | ||
| + | |||
| + | ソート順: | ||
| + | 成立条件: | ||
| <sxh python> | <sxh python> | ||
