ABC 165 E - Rotation Matching
問題
$n$ 人の参加者と $ m $ 個の対戦場があり、各対戦場に $2$ つずつ、$1$ から $n$ の番号のうちの $2 m $ 個を割り当てる。参加者は自分の番号のある対戦場で対戦し、その後自分の番号に $1$ 足す。このとき $n+1$ は $1$ とする。この操作を $n$ 回繰り返すとき 、同じ組合せの対戦が起きないような対戦場への番号の割り当てを求めよ。（$2 m + 1 \leq n \leq 2 \times 10 ^ 5 $）
解説
$i$ 番の対戦場に割り当てた数字のペアを $(A _ i , B _ i )$ とし、 $$ C _ i = \mathrm{min} \{ | A _ i - B _ i | , n - | A _ i - B _ i | \} $$ とすると、以下の $2$ 条件をみたしていれば、同じ組合せの対戦は起きない。
- 各 $i$ について、$2 \times C _ i \neq n$
- 各 $i \neq j $ について、$C _ i \neq C _ j$
なぜなら、$1$ つめの条件により対戦場内では同じ組合せの対戦が起こらず、「$a,b$ に $1$ ずつ足し、$n + 1$ になれば $1$ にする」という操作で $\mathrm{min} \{ | a - b | , n - | a - b | \} $ の値は変わらないため、$2$ つめの条件により異なる対戦場で同じ対戦が起こることはないからである。
$2$ つの条件をみたす番号の割り当ては以下のように構成できる。
$a=n,\ b=1$ から開始し、$a$ を $1$ ずつ減らし、$b$ を $1$ ずつ増やしていく。 途中で上記の条件のいずれかをみたさない
なら、さらに $a$ を $1$ 減らす。
例えば、$n = 6, \ m = 2$ のとき、$1$ つめの対戦場には $(6,1)$ を割り当て、次のペアは $(5,2)$ であるが、 $$ \mathrm{min} \{ | 5 - 2 | , 6 - | 5 - 2 | \} = 3 $$ より、$1$ つめの条件を満たさないので、$2$ つめの対戦場には $(4,2)$ を割り当てる。
$n = 8, \ m = 3$ のとき、$1$ つめの対戦場には $(8,1)$ を割り当て、$2$ つめの対戦場には $(7,2)$ を割り当てる。次のペアは $(6,3)$ となるが、 $$ \begin{aligned} \mathrm{min} \{ | 7 - 2 | , 8 - | 7 - 2 | \} &= 3 \\ \mathrm{min} \{ | 6 - 3 | , 8 - | 6 - 3 | \} &= 3 \end{aligned} $$ より、$2$ つめの条件を満たさないので、$3$ つめの対戦場には $(5,3)$ を割り当てる。
実装
$$ \mathrm{dist}(a,b) = \mathrm{min} \{ | a - b | , n - | a - b | \} $$ とおいて、すでに出た $\mathrm{dist}(a,b)$ の値を集合 $S$ に入れて管理した。
n, m = map(int, input().split()) def dist(a, b): return min(abs(a - b), n - abs(a - b)) a, b = n, 1 S = set() for i in range(m): if 2 * dist(a, b) == n or dist(a, b) in S: a -= 1 print(a, b) S.add(dist(a, b)) a -= 1 b += 1
