https://atcoder.jp/contests/abc165/tasks/abc165_e
解説
https://atcoder.jp/contests/abc165/submissions/12644257
頑張ってスマートな方針を考える。
最も厳しいパターンで方針を考えるのが良いだろう。
今回であれば、対戦相手が少ないほど、再戦の可能性が上がりそうなので、N=2M+1のパターンで考えるといい。
これで頑張って考えて、以下の方針をひねり出す。
「M個の対戦場はそれぞれ違う距離の対戦相手と戦うようにする」
例えば、M=3, N=7であれば、以下のように頑張る。
A vs Bの戦いと考える。
- 1つ目の対戦場は、B-A=1となるようにする
- 2つ目の対戦場は、B-A=2となるようにする
- 3つ目の対戦場は、B-A=3となるようにする
こうしておくと、対戦番号がシフトしても対戦相手との差は変わらないので、異なる対戦場で同じパターンが現れることはない。
あとは、最初の番号がすべて異なるように配置してやれば、各対戦場で+1されても、
その対戦場の差でのパターンはN通りあり、順番にそれが当たるので、問題ない。
問題は、どのように初期配置を決めるかである。
簡潔に表現すると、以下の図のようにする。
このように奇数と偶数で分けて、重ねていくと、場所をかなり節約でき、組を作ることができる。
あとは、これをうまく実装する。
int N, M; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; if (M == 1) { printf("1 2\n"); return; } int i1 = 1; int i2 = M + 2; rrep(diff, M, 1) { printf("%d %d\n", i1, i1 + diff); i1++; swap(i1, i2); } }