自分の構築方法が公式解説やユーザ解説に載っていなかったので。
問題
- $M$個の対戦場があり、それぞれに$2$つずつ相異なる数字を重複のないように割り振る
- $N$人にはあらかじめ$1$～$N$の番号が割り振られており、各ラウンドにおいて自分の番号と対戦場に割り振られた番号が一致すればそこへ行き、相手と対戦をする
- 各ラウンドの終了後に、それぞれに割り当てられた番号を$+1$する。但し$N+1$は$1$とする。(1-indexedで考える$\mathrm{mod} N$ のようなもの)
- この工程を$N$ラウンド繰り返したとき、どの$2$人も$2$回以上同じ組み合わせで対戦しないような$M$個の対戦場への数値の割り振り方を構築せよ
制約
- $1 \leq M$
- $2M+1 \leq N \leq 200000$
解説
前提として、$N$を固定したときにできるだけ$M$を大きくした方が全体の対戦数が増え同じ組み合わせでマッチするリスクが高まりそう。そこで、できるだけ$M$が大きい場合でも条件を満たす割り当て方法を検討し、それがより条件の緩い$M$が小さい場合でも適用できるかを考える順番でいく。
まずは愚直に割り当てるとどうなるかを考えてみる。
例えば$N=7, M=3$について、3個の対戦場への割り当てを
- 1-2
- 3-4
- 5-6
とするとどうなるだろう。
便宜上7人をABCDEFGとアルファベットで表記するとすると、最初はA=1,B=2,...,G=7だから、1ラウンド目は(A,B),(C,D),(E,F)の3組が対戦することになる。3ラウンド目まで飛ばすと各自の番号が+2ずつされているので、(F,G),(A,B),(C,D)が対戦することになるが、これは1ラウンド目と(A,B),(C,D)が重複してしまっている。
このような重複がなぜ起こるかというと、単純なことで割り当てる数字のペアの差が、複数の対戦場の間で等しくなっているため。全部で$N$ラウンドあるということは、ある人がすべての番号付けを経験するわけだから、もしペアの差が等しくなるような対戦場が複数あれば、一度どちらかでマッチした後に番号の+1を繰り返すと、必ずもう片方でもマッチすることになる。
つまり、複数の対戦場でペアの数字が等しくなる場合は避けなければならない。
では、入力例2のように、
- 1-7
- 2-6
- 3-5
と、 片方は1からインクリメント、マッチングする相手をNからデクリメントする のはどうだろう。これだと2数の差は上から順に$N-2, N-4, ...$ と2ずつ減っていくので、重複することはない。もちろん 5-3のようなペアが出てくるまでラウンドを繰り返せば重複が起こるが、問題の制約で $2M+1 \leq N$があるので、左側の数が一番大きくなる$M$のときでも、右側の$N-M$について制約を変形すると $M+1 \leq N-M$が成り立つから常に右側の数は左側の数より大きく、上記のような心配はない。
実際、実はこの方法で$N$が奇数の時は正解になる。
しかし、 $N$が偶数の場合に失敗する ことがある。例えば $N=6, M=2$を考えてみる。
- 1-6
- 2-5
と割り当てる場合を考えると、1ラウンド目では(A,F),(B,E)となる。 これが4ラウンド目になると+3されているので(D,C),(E,B)となる。よく見ると(B,E)が被ってしまっている。こうなる理由は単純で、左側から右側を見たときの差3と右側から1をはさんで左側を見たときの差3が一致してしまっているから。今の例でいうと$2-5$を採用するのは実質的に$5-8$も同時採用してしまっていることになっており、これだと差が同じものが2回出てきてはいけないというルールに反してしまう。
そもそもこの問題は、差が$N/2$になるような2数が出てくる場合に起こることで、実は$N=4m+2$のような場合にのみ起こる。というのは$N$が偶数のときにこれまで説明したようなペアの作り方をすると2数の差が必ず奇数になるため。$N=4m$のような形の場合は$N/2$も偶数になるのでこの事例を考慮する必要がない。また、$N=4m+2$のときとりうる最大の$M$は$M=2m$のときで、2数の差は大きい方から$4m+1,4m-1, 4m-3,4m-5,...$と続き、最終的に$M=2m$個のペアをとると最後の差は$3$となる。この中に$2m+1$が含まれている場合、それを飛ばして$2m$のペアを代わりに採用して同様の操作を続けても最後の差は$2$までしか小さくならないため、全ての差が重複しないようにできる。
上述の$N=6,M=2$の事例の場合は、2-5の代わりに差が2の2-4や3-5を採用すれば回避できる。
実はこれでも$N=4m$の場合に失敗する場合がある。
例えば$N=8, M=3$を考えると、同様の操作で差が$7,5,3$のペアを構築できるが、実は差が5のペアと差が3のペアは裏返しの関係になっている。具体的には$左側+5=右側$のとき、$右側+3=左側+N$の関係が成り立っているので、一度差が5のペアでマッチした後+3すると、入れ替わりで再度マッチしてしまう。$N=4m$の場合はこのパターンを回避する必要がある。この場合も差の最小値は3であるため、どこかで既に作ったペアの差と一致するような事例に遭遇した場合、そこからペアの差をさらに1だけ小さくして操作を継続すれば、それ以降のペアで同様の事例が起こらないし、最小でも2なので条件を満たすことになる。
最後にここまでの議論を踏まえて、$M$が小さい場合にも適用できるかを考えるが、この構築方法は既に作ったペアの差とこれから作るペアの差が被らないようにするもので、$M$の値にかかわらず適用できる。したがって、この方法で構築すれば$M$が小さい場合にも対応できる。
解答
(1,N), (2,N-1),(3,N-2),...のように、(1,N)から始めて、左側の数を1増やし右側の数を1減らしながら割り当てを$M$組作る。
但し$N$が偶数の場合は構築中に以下のような状況になった場合、左側の数字だけを1増やしてからペアを作って、操作を続行する。
- 2数の差が$N/2$と一致したとき
- 既に作成したペアの2数の差のいずれかと、今作ろうとしているペアの2数の差の和が$N$に等しくなるとき
AC例
2数の差が$N/2$に等しくなる場合については、最初からN/2を既に存在するペアの差の候補として管理しておけばよく、本コードでもそのようにすることで$N$が偶数のときの場合分けを、後者のみで済むようにしている。
https://atcoder.jp/contests/abc165/submissions/51932116