練習で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 になります。

というわけで常に正しくグラフを構成できるようです。

提出：

公式の解説動画：