競プロ参戦記 第17回「Tr/ee」 ARC 103 [E]
練習で700点問題を解きました。
構成問題によくある「図を見ればすぐわかる」タイプなので、解説より考察がメインです。
E - Tr/ee
問題概要:長さ N のビット列 S が与えられる。次の条件を満たすN頂点のツリーが存在するか判定し、存在するなら一例を示せ。
S[k] = 1 ⇔ ツリーの辺を1つ削除して頂点数 k の連結成分を得られる
*---*-/-*---*
|
*
↓
*---* *---*
|
*
解説:ツリーから辺を1つ削除すると、頂点数 k, (N-k) の2つの連結成分に分かれます。もとのツリーはこの2つの連結成分の間に「橋」を架けたものです。2つの連結成分はそれぞれ、橋の両端点を「根」とすれば部分ツリーとみなせます。
そのため、条件「ツリーの辺を1つ削除して頂点数 k の連結成分を得られる」は「ツリーが頂点数 k の真部分ツリーを持つ」と同値です。
ツリーが存在する条件を考えると、S に一定の制約がみつかります。ツリーが頂点数 k の部分ツリーを持つなら N-k の部分ツリーも持つので、S[k] = S[N-k] の必要があります。N ≥ 2 なのでツリーは必ず頂点数 1 の部分ツリーを持つため、S[1] = S[N - 1] = 1 です。逆に部分ツリーの頂点数がNということはありえないので、S[N] = 0 の必要があります。
逆にそれ以外のケースではツリーは構成できます。後述の構成手順があるからです。
その前に少し具体例をみておきます。
S=1110 (N=4, k=1,2,3) なら、頂点数1~3の部分ツリーを持つ4頂点ツリーを構成せよということなので、次のツリーが正解です。(* が頂点で -- が辺)
1 2 1
* --- * --- * --- *
ツリーが条件を満たしているかはDPで判定できます。辺に w = (その辺が隣接する部分ツリーの頂点数) をメモしてきます。まず、リーフノードに接続している辺は w=1 です。ある頂点 v に接続している辺 w の値は、その頂点に接続している他の辺の w の総和 + 1 です。
S=10101010 (N=7, k=1,3,4,6) はもう少し複雑で、次のようなツリーがあります。
1 3 3 1
* --- * --- * --- * --- *
\ \
1 \ \ 1
* *
あまり構成手順にピンと来ないので、逆にツリーから S を構成して様子をみるのではどうでしょう。極端な例を考えます。次の2つのツリーが構成されるにはどんな S が必要ですか。
道グラフ:どの頂点数でも部分ツリーがある
1 2 3 2 1
* --- * --- * --- * --- * --- *
星グラフ:部分ツリーの頂点数はすべて1 (大きいほうは5)
*
1 1| 1
* --- * --- *
/ \
1/ \1
* *
道は S=111110 (N=6, k=1,2,3,4,5)、星は S=100010 (N=6, k=1,5) です。
このあたりから「S が多いと分岐が増える」と予想できて、次の構成手順を思いつきました。
1. 1点のグラフを用意して、その点にフォーカスする。
2. 1 ≤ i ≤ N-1 について繰り返す:
3. S[i] = 1 なら、フォーカスしている点に接続する新しい点を追加して、それにフォーカスを移す。
4. S[i] = 0 なら、フォーカスしている点に接続する新しい点を追加する。
S[i] = 1 の場合は、新しく追加した辺を切ったときの部分ツリーの頂点数が i になります。
一方、S[i] = 0 の場合、前述の条件から S[j] = 1 となる次の j があるので、追加した辺を切ったときの部分ツリーの頂点数は j になります。
というわけで常に正しくグラフを構成できるようです。
提出:
公式の解説動画:
この記事が気に入ったらサポートをしてみませんか?