Rotation Matching [AtCoder Beginner Contest 165 E]

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);
    }
}