AtCoder Regular Contest 152 D問題メモ

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

programming_algorithm/contest_history/atcoder/2022/1120_arc152.txt · 最終更新: 2022/11/22 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0