差分
このページの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: | ||
仮に、$\mod{M}$ の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。 | 仮に、$\mod{M}$ の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。 | ||
- | < | + | < |
これを確認する。$a \le b \le c \le d$ として、ペアの組み方は3通りある。 | これを確認する。$a \le b \le c \le 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$ のペアは、 | ||
行 440: | 行 438: | ||
</ | </ | ||
- | ただ、先ほどの例だと $Z=9$ になる。$M=10$ なので、答えとなり得る値の中で最大であり、そのまま適用するのはあまり有効そうではない。$\mod{M}$ を有効活用したい。 | + | ただ、modを含めて考えると、先ほどの例だと $Z=9$ になる。$M=10$ なので、答えとなり得る値の中で最大であり、そのまま適用するのはあまり有効そうではない。 |
- | + | ||
- | ,-----, | + | |
- | | ,-, | ,-, | + | |
- | 0 2 3 4 5 9 | + | |
- | + | ||
- | 1つ大きい数字同士でペアを作ってから、残ったもので大小組み合わせると、$X=5$ となり、サンプルの出力例と一致する。 | + | |
- | 適切なペアはこんな感じになるようだ。 | + | |
- | ただ $N$ が少なすぎて、どういう風に一般化すればいいか、まだ決めづらい。 | + | |
ところで、各数字は $0 \le a_i \lt M$ なので、2つ足しても $2M$ を超えることはない。「和が $M$ を超えるペア」のスコアは必ず「2数の和$-M$」である。つまり、「和が $M$ を超えるペア」同士の間では、2数の和がそのまま大小比較に使える。 | ところで、各数字は $0 \le a_i \lt 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 \ge a+b$、$b+d \ge c+d$ が成り立つので、最終的な $Z$ の値も $Z_左 \ge Z_右$ となり、常に改善される。 | + | また、$(左)a+c \ge (右)a+b$、$(左)b+d \ge (右)c+d$ が成り立つので、最終的な $Z$ の値も $Z_左 \ge Z_右$ となり、常に改善される。 |
他のケースも、考えていくと同じ事が言える。 | 他のケースも、考えていくと同じ事が言える。 | ||
行 535: | 行 525: | ||
$a_1, | $a_1, | ||
- | * 成立、$M$ 未満グループが不成立(和が $M$ 以上のペアが出来てしまう)なら左半分から境界を探索 | + | * 成立、または |
* $M$ 以上グループが不成立(和が $M$ 未満のペアが出来てしまう)なら右半分から境界を探索 | * $M$ 以上グループが不成立(和が $M$ 未満のペアが出来てしまう)なら右半分から境界を探索 | ||
行 543: | 行 533: | ||
... a ... b ... | ... c ... d ... | ... a ... b ... | ... c ... d ... | ||
| | ||
- | ソート順: | + | ソート順: |
- | 成立条件: | + | |
<sxh python> | <sxh python> |