AtCoder Regular Contest 152 D問題メモ

AtCoder Regular Contest 152

D - Halftree

• 番号 $0,...,N-1$ の $N$ 頂点のグラフがあり、はじめ、辺は無い
• 好きなだけ辺を追加することができる
• 最後に1回だけ、与えられる整数 $K$ を用いて以下の操作が行われる
  • あなたが追加した各辺につき、両端の頂点が $u,v$ なら、$(u+K \mod{N},v+K \mod{N})$ にも辺を追加する
  • 元々辺が存在していても追加されるため、その場合は多重辺となる
• 操作後のグラフが木となるような、あなたが追加するべき辺の組の一例を示せ
• 不可能な場合は-1を出力せよ
• $2 \le N \le 2 \times 10^5$
• $1 \le K \le N-1$

いろいろな考え方があるとは思うが、自分の考えをメモ。

まず、木なら辺は $N-1$ 本あるため、これが偶数、つまり $N$ が奇数でないと不可能。
以下 $N$ は奇数とする。
追加する辺は $\dfrac{N-1}{2}$ 本である。

いきなり答えの一例を示すと、以下のようになる。

$N$ 個の数字を $K$ ごとに改行して並べる（続く数字はループするようにする）と、 操作で追加される辺は「ちょうど1マス分下に移動した辺」となる。

N=35 K=10    ━:あなたが追加した辺  ─:操作で追加された辺
00━01━02━03━04━05━06━07━08━09
┃
10─11─12─13─14─15─16─17─18─19
│                        ／      ／
20━21━22━23━24━25  26  27  28  29
                          ／      ／
30─31─32─33─34─00  01  02  03  04

05  06  07  08  09  10  11  12  13  ...

N=45 K=10
00━01━02━03━04━05━06━07━08━09
┃
10─11─12─13─14─15─16─17─18─19
│
20━21━22━23━24━25━26━27━28━29
┃
30─31─32─33─34─35─36─37─38─39
│    ／      ／
40  41  42  43  44  00  01  02  03  04
      ／      ／
05  06  07  08  09  10  11  12  13  ...

1行目を全て横に結ぶと、2行目が全て結ばれる。同様に3,5,7,…行目を結ぶと4,6,8,…行目が結ばれる。
また、1列目を縦に1個おきに結ぶと、各行がつながる。

閉路ができない限界まで、「横に繋げる」「左端を繋げる」の2種類の方法により辺を追加してみる。

全体（$N-1$ の属する行）が、奇数行か偶数行かにより、処理が多少異なる。

1列目を縦につなぐ辺は最終行までつなげられるが、最終行の残りは横に繋げられなくなる。

上の $N=45$ の例では、00～39は全てつながり、1列目の40も縦につながるが、 その後の $41～44$ は横に結ぶと 06-07 などが多重辺となってしまうため、同様の方法ではこれ以上追加できない。

1列目を縦につなぐ辺は、閉路ができない範囲では最終行の1つ上で止まる。

一方、最終行は1つ上の行を横につなげることで、操作によって追加される辺で '00' とつながることができる。
ただし、そのため最終行の1つ上の行は横の辺を途中で止めなければならず、いくつかの数字が残される。

上の $N=35$ の例では、$26～29$ が残される。

奇数行、偶数行のいずれでも、いくつかの数字が残される可能性があるが、残されるのは

• 1行のみ（2行にまたがることはない）
• それぞれ単独の数字（中途半端につながった欠片が残ることはない）
• $N$ が奇数であることを踏まえると、残るのはかならず偶数個

であることがわかった。

これらは、2個セットにして前の数字を右上とつなぐと、後の数字は左下とつながる。

これで残った数字もカバーできる。

Python3

n, k = map(int, input().split())

if n % 2 == 0:
    print(-1)
    exit()

m = n // 2
buf = []
check = [True] * n

for i in range(0, n, 2 * k):
    if i + 2 * k < n:
        buf.append((i, i + k))
        check[i] = False
        check[i + k] = False
        check[i + 2 * k] = False

i = 0
while len(buf) < m:
    if i + k >= n:
        break
    if (i + 1) % k != 0:
        buf.append((i, i + 1))
        check[i] = False
        check[i + 1] = False
        check[i + k] = False
        check[(i + k + 1) % n] = False
        i += 1
    else:
        i += k + 1

for i in range(n):
    if check[i]:
        buf.append((i, (i - k + 1) % n))
        check[i] = False
        check[i + 1] = False

print(m)
for u, v in buf:
    print(u, v)