差分
このページの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 | ||
|---|---|---|---|
| 行 424: | 行 424: | ||
| `--' | `--' | ||
| - | ある2通りのペアの組み方 $A,B$ があって、醜さの最大値の比較で $Z_A \le Z_B$ と言うためには、 | + | ある2通りのペアの組み方 $P,Q$ があって、醜さの最大値の比較で $Z_P \le Z_Q$ と言うためには、 |
| - | 「$A$ の全てのペアについて、それぞれ、より醜さが大きいペアが $B$ に存在する」ということが言えればよい。 | + | 「$P$ の全てのペアについて、それぞれ、より醜さが大きいペアが $Q$ に存在する」ということが言えればよい。 |
| すると、$C$ のペアは、 | すると、$C$ のペアは、 | ||
| 行 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数の和がそのまま大小比較に使える。 | ||
