差分
このページの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 | ||
---|---|---|---|
行 438: | 行 438: | ||
</ | </ | ||
- | ただ、先ほどの例だと $Z=9$ になる。$M=10$ なので、答えとなり得る値の中で最大であり、そのまま適用するのはあまり有効そうではない。$\mod{M}$ を有効活用したい。 | + | ただ、modを含めて考えると、先ほどの例だと $Z=9$ になる。$M=10$ なので、答えとなり得る値の中で最大であり、そのまま適用するのはあまり有効そうではない。 |
ところで、各数字は $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数の和がそのまま大小比較に使える。 | ||
行 525: | 行 525: | ||
$a_1, | $a_1, | ||
- | * 成立、$M$ 未満グループが不成立(和が $M$ 以上のペアが出来てしまう)なら左半分から境界を探索 | + | * 成立、または |
* $M$ 以上グループが不成立(和が $M$ 未満のペアが出来てしまう)なら右半分から境界を探索 | * $M$ 以上グループが不成立(和が $M$ 未満のペアが出来てしまう)なら右半分から境界を探索 | ||
行 533: | 行 533: | ||
... a ... b ... | ... c ... d ... | ... a ... b ... | ... c ... d ... | ||
| | ||
- | ソート順: | + | ソート順: |
- | 成立条件: | + | |
<sxh python> | <sxh python> |