かしのブログ

競技プログラミングとか

AtCoder Beginner Contest 165 E - Rotation Matching

AtCoder

問題

$N$ 人の参加者が、 $M$ 個の卓でそれぞれ2人ずつ対戦する。卓 $i$ では番号 $a_i$ と $b_i$ の人が対戦する。はじめ、 $N$ 人の参加者は1から $N$ の番号が順番についていて、対戦が終わると番号が1増える（ $N+1$ は1になる）。 $N$ ラウンド実施し、同じ2人が対戦するカードが存在しないような卓の番号の振り方を求める。

考察

問題文のただし、与えられる制約のもとでそのような割り当てが必ず存在することが示せます。より、 $2M+2$ 番目以降の席を設けなくても解けるとこがわかるので、 $N = 2M +1$ としても問題が解けるとみなす。

ある卓 $i$ で $b_i = a_i + d$ のとき、他に、 $b_j = a_j + d$ や $b_j = a_j + (N-d)$ なる卓 $j$ は存在してはいけない。

卓 $i$ で $d_i = b_i - a_i = i$ とすると、同じ2人が対戦することがなくなるので、これの実現方法を考える。差が奇数の対戦カードは $\lceil \frac{M}{2} \rceil$ 、偶数の対戦カードは $\lfloor \frac{M}{2} \rfloor$ なので、 $1\sim 2\times \lceil \frac{M}{2} \rceil$ を差が奇数の対戦カードとして、残りを偶数の対戦カードとして差の大きいものから順に決定できる。

$N \gt 2M+1$ 以上でも、この実装は可能。

実装