差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/04/21] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/04/21] – [解法] ikatakos | ||
|---|---|---|---|
| 行 406: | 行 406: | ||
| 解説pdfを読んだら理解と実装は比較的簡単だが、考察の時点で結構地道なパターン分けが必要。 | 解説pdfを読んだら理解と実装は比較的簡単だが、考察の時点で結構地道なパターン分けが必要。 | ||
| - | |||
| - | ===いろいろ試す=== | ||
| 最大値をなるべく低く抑えるということは、ペアの合計を均等にした方が良さそうなので、大きいのと小さいのを組み合わせる方向性が思いつく。 | 最大値をなるべく低く抑えるということは、ペアの合計を均等にした方が良さそうなので、大きいのと小さいのを組み合わせる方向性が思いつく。 | ||
| 行 418: | 行 416: | ||
| 仮に、modM の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。 | 仮に、modM の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。 | ||
| - | < | + | < |
| これを確認する。a≤b≤c≤d として、ペアの組み方は3通りある。 | これを確認する。a≤b≤c≤d として、ペアの組み方は3通りある。 | ||
| 行 426: | 行 424: | ||
| `--' | `--' | ||
| - | ある2通りのペアの組み方 $A,Bがあって、醜さの最大値の比較でZ_A \le Z_B$ と言うためには、 | + | ある2通りのペアの組み方 $P,Qがあって、醜さの最大値の比較でZ_P \le Z_Q$ と言うためには、 |
| - | 「$Aの全てのペアについて、それぞれ、より醜さが大きいペアがB$ に存在する」ということが言えればよい。 | + | 「$Pの全てのペアについて、それぞれ、より醜さが大きいペアがQ$ に存在する」ということが言えればよい。 |
| すると、C のペアは、 | すると、C のペアは、 | ||
| 行 441: | 行 439: | ||
| ただ、先ほどの例だと Z=9 になる。M=10 なので、答えとなり得る値の中で最大であり、そのまま適用するのはあまり有効そうではない。modM を有効活用したい。 | ただ、先ほどの例だと Z=9 になる。M=10 なので、答えとなり得る値の中で最大であり、そのまま適用するのはあまり有効そうではない。modM を有効活用したい。 | ||
| - | |||
| - | ,-----, | ||
| - | | ,-, | ,-, | ||
| - | 0 2 3 4 5 9 | ||
| - | |||
| - | 1つ大きい数字同士でペアを作ってから、残ったもので大小組み合わせると、X=5 となり、サンプルの出力例と一致する。 | ||
| - | 適切なペアはこんな感じになるようだ。 | ||
| - | ただ N が少なすぎて、どういう風に一般化すればいいか、まだ決めづらい。 | ||
| ところで、各数字は 0≤ai<M なので、2つ足しても 2M を超えることはない。「和が M を超えるペア」のスコアは必ず「2数の和−M」である。つまり、「和が M を超えるペア」同士の間では、2数の和がそのまま大小比較に使える。 | ところで、各数字は 0≤ai<M なので、2つ足しても 2M を超えることはない。「和が M を超えるペア」のスコアは必ず「2数の和−M」である。つまり、「和が M を超えるペア」同士の間では、2数の和がそのまま大小比較に使える。 | ||
| 行 473: | 行 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 が成り立つので、最終的な Z の値も Z左≥Z右 となり、常に改善される。 | + | また、$(左)a+c \ge (右)a+b、(左)b+d \ge (右)c+dが成り立つので、最終的なZの値もZ_左 \ge Z_右$ となり、常に改善される。 |
| 他のケースも、考えていくと同じ事が言える。 | 他のケースも、考えていくと同じ事が言える。 | ||
