AtCoder Regular Contest 179 B,D問題メモ

AtCoder Regular Contest 179

B - Between B and B

問題文

$1$ 以上 $M$ 以下の整数からなる長さ $M$ の数列 $(X_1,X_2,\dots ,X_M)$ が与えられます.
$1$ 以上 $M$ 以下の整数からなる長さ $N$ の数列 $A=(A_1,A_2,\dots ,A_N)$ であって, 以下の条件を満たすものの個数を $998244353$ で割ったあまりを求めてください.
- $B=1,2,\dots ,M$ について, $A$ の中で異なる位置にある $2$ つの $B$ の間(両端を含む)には $X_B$ が存在する.

制約

$1\leq M\leq 10$
$1 \leq N \leq 10^4$
$1 \leq X_i \leq M$

解法

たとえば $X_1=5$ のとき、一度 “1” を置いたら、“5” を置くまで、次に “1” をおくことはできない。

$M$ の値が小さいのが取っかかり。

$DP[i,S]=(A_1,A_2,...,A_i)$ まで確定させて、 $A_{i+1}$ には集合 $S$ にある数字を置ける状態の数

たとえば、 $S=\{1,2,5,7\}$ とすると、 $DP[i-1, S]$ の状態からは、 $A_{i}$ には4種類の数字を置ける。

         i-1  i
... 1  3  6   ?     ← 1 or 2 or 5 or 7 を置ける

$Y_i$ を、「 $X_j=i$ であるような $j$ の集合」とし、前計算しておく。（意味合い的には、 $i$ を置いたら次以降に置いて大丈夫になる数字）

$A_i$ に $k$ を置くとすると、 $DP[i, S \backslash \{k\} \cup Y_k] += DP[i-1,S]$ というように遷移できる。

$2^M$ 通りにつき、“1”が立ってるbitからそれぞれ遷移できて、それを $N$ 回繰り返すので、計算量は $O(NM2^M)$

Python3

D - Portable Gate

問題文

頂点 $1,2,\dots ,N$ の $N$ 頂点からなる木が与えられます. $i$ 番目の辺は頂点 $u_i,v_i$ を双方向に結んでいます.
すべての頂点ははじめ白に塗られています.
駒と不思議なゲートを $1$ 個ずつ用いて次の手順ですべての頂点を黒に塗ります.
- まず好きな頂点を選び, 駒とゲートをその頂点に置きます.
- その後, すべての頂点が黒に塗られるまで次の操作を何度も行います.
  - 次のうち $1$ つを選んで実行する.
    - 駒が置かれている頂点を黒に塗る.
    - 駒が置かれている頂点に隣接した頂点をひとつ選び, その頂点に駒を移動させる, コストが $1$ かかる.
    - ゲートが置かれている頂点に駒を移動させる.
    - 駒が置かれている頂点にゲートを移動させる.
コストがかかるのは $2$ 番目の操作のみであることに注意してください.
かかるコストの合計の最小値を求めてください.

制約

$2 \leq N \leq 2\times 10^5$
$1 \leq u_i,v_i \leq N$

解法

要は、ゲームなんかであるファストトラベル的なイメージ。
既に訪れたことのある頂点を同時に1つまで登録でき、いつでもそこにノーコストで戻れる。
登録の上書きもできるが、そうすると以前登録されていた頂点は失われてしまう。

開始頂点が決まっている場合

開始頂点を根とした木DPで解ける。

探索は根から葉へ進む。基本的に、木の頂点を全て巡る移動といえばオイラーツアーのようになる。

ゲートは既に訪れた頂点を登録できるので、オイラーツアーのコストの内、「ある頂点にゲートを設置しておき、その子の部分木を全て探索し終わったら、戻るのに必要なコスト」を節約するという使い方となる。

    ：
    ●←ゲート
    /\
  ●  ○        ゲートの位置まで戻るコスト3を、
  /\            ゲートを設置することで節約できる
 ●●
   ｜
   ●←駒

  (u)
  / \
(v) (w)

$u$ にゲートを置き、 $v$ 以下の探索が終わったら戻るのに使おうと思うと、 $v$ 以下の探索の過程ではゲートを1回も使うことはできない。

ただ、 $v$ では使わなくても、兄弟である $w$ 以下では使うことができる。 $w$ から $v$ に移動するとき（または探索順は逆でもいいが）、 $u$ を経由するので、その時に再設置できる。兄弟間は独立に、「親にゲートを設置して戻るのに使う」のか、「自分以下の部分木内で使う」のかを選べる。
（または、 $u$ より上位の頂点 $x$ にゲートを設置する場合は $v,w$ のいずれでも使うことはできないが、その場合のコストは、 $x$ でDPを計算する際にまとめて算出できる）

以下の木DPをする。

$\mathrm{DP}[v] = (p_v,q_v,r_v,s_v)$
- $p_v$ ： $v$ を出発して部分木を全て巡り $v$ に戻ってくるのに、ゲートを使用した場合の最適コスト
- $q_v$ ： $v$ の部分木の頂点数
- $r_v$ ： $v$ を深さ0として、 $v$ の部分木で最も深い頂点の深さ
- $s_v$ ： $v$ を出発して部分木を全て巡り「 $v$ に戻ってこなくても良い」場合の最適コストの、 $p_v$ との差分

問題の設定では、全てを黒で塗りおえたら、開始頂点に戻らずそこで終えてよい。
木DPでは、基本的には親に帰らないといけないので $v$ まで戻るコストを考慮するが、最後だけは、「全て塗りおえてから、根に戻るコスト」を省略できる。
$s_v$ は、それを考慮するものとなる。

頂点 $\mathrm{DP}[u]$ を求めたい場合、まず子ごとに寄与を計算する。
子 $v$ が $\mathrm{DP}[u]$ に寄与する分をそれぞれ、 $p'_{uv},q'_{uv},r'_{uv},s'_{uv}$ とする。

$p'_{uv}$ の求め方
- $v$ 以下でゲートを使う場合： $u→v,v→u$ の部分は直接の移動が必要になる
  - $p_v+2$
- $u$ にゲートを設置して、 $v$ の探索後戻るのに使う場合：
  - $v$ 以下はオイラーツアーなので、頂点数 $q_v \times 2$ の直接移動が必要になる
  - そのうち、最も深い頂点から帰る（そうなるように探索順を決める）ようにすると、 $r_v+1$ だけ省略できる
  - $2q_v-r_v-1$
- $p'_{uv}=\min(p_v+2,2q_v-r_v-1)$
$s'_{uv}$ の求め方
- まずは差分ではなく、最後の頂点を塗りおえるまでの最適コストを計算し、それを $p'_{uv}$ から引く
- $v$ 以下でゲートを使う場合： $u→v$ のみ新たな直接移動が必要になる（帰りは省略できる）
  - $p_v-s_v+1$
- $u$ にゲートを設置して、 $v$ の探索後戻るのに使う場合：上記と変わらない
  - $2q_v-r_v-1$
- $s'_{uv}=p'_{uv}-\min(p_v-s_v+1,2q_v-r_v-1)$

これらを兄弟間で統合したものが、DP[u]となる。

$p'_{uv}$ は、兄弟間で直接合算
$q'_{uv}$ は、兄弟間で直接合算
$r'_{uv}$ は、兄弟間でMAXを取る
$s'_{uv}$ は、兄弟間でMAXを取る

最終的に、根を $k$ として、 $p_k-s_k$ が、開始頂点を $k$ とした場合の答えとなる。

全方位木DP

ここまででも結構な考察だが、実際は開始する頂点を自由に選べる。

根についての木DPの結果を全ての頂点について求めたいと言えば、全方位木DP。

ある程度、ライブラリで実装を抽象化していれば、根を固定した場合の処理を定義するだけで、自動的に全方位木DPも可能となる。

全方位木DP

全て一から実装するのは少し大変かも。

Python3

        
          
          
              
              from dataclasses import dataclass
from typing import List, Callable, TypeVar
 
T = TypeVar('T')
U = TypeVar('U')
 
 
@dataclass
class RerootingEdge:
    src: int
    tgt: int
    value: U
 
 
class Rerooting:
    """
    抽象化 全方位木DP
    ・r = 1,2,...,N について、頂点 r を根とした木DPの結果（DP[r]）を求める。
    ・merge 演算に逆演算が成り立たない場合に対応
    ・頂点に対して値が決められている場合、辺に対して値が決められている場合（あるいは両方）のいずれにも対応
 
    【使い方】
    ① __init__()に示された関数を定義する
    ② add_edge()にてN-1本の辺を与える。u→v と v→u で2回呼んで双方向で与える。
    ③ solve()
 
    【apply, merge 関数で処理すべき内容】
       (u)      ans[v] には、"v 自身の値は未反映の" v 以下の部分木に対するDP結果が入る。（その方が定義する関数の数を減らせるため）
      ／|＼      （※ たとえば「ans[i] = i 以下の部分木の頂点数」とした場合、ans[v] には v 自身は加算されていない）
    (v)(w)(x)   ans[u] を求める際に呼ばれる apply(ans[v]) 内で、v についての情報を加算する。
                apply では↑と同時に、辺をv→uとたどる際に何らかの処理が行われる場合はそれも反映する。頂点 u の値の反映は行わない。
                merge は、[ unit, apply(ans[v]), apply(ans[w]), apply(ans[x]) ] を左から2つずつ累積的に合成していく処理を行う。
                全てマージされた結果が、ans[u] となる。
    """
 
    def __init__(self,
                 n: int,
                 leaf_factory: Callable[[], T],  # 1回目のDFSで葉に適用する値
                 unit_factory: Callable[[], T],  # 単位元
                 merge: Callable[[T, T], T],  # 演算
                 apply: Callable[[T, RerootingEdge], T],  # [子の値, 親→子への辺] から、親に伝える情報を計算
                 ) -> None:
        self.n: int = n
        self.links: List[List[RerootingEdge]] = [[] for _ in range(n)]
        self.leaf = leaf_factory
        self.unit = unit_factory
        self.merge = merge
        self.apply = apply
 
    def add_edge(self, s, t, value) -> None:
        self.links[s].append(RerootingEdge(src=s, tgt=t, value=value))
 
    def solve(self) -> List[T]:
        links = self.links
        status = [0] * self.n
 
        leaf = self.leaf
        unit = self.unit
        merge = self.merge
        apply = self.apply
 
        # 1回目のDFSで、自身の子のapply済み結果の左からの累積和
        acc_left: List[List[T]] = [[unit()] for _ in range(self.n)]
        # 1回目のDFSで、自身の子のapply済み結果の右からの累積和
        acc_right: List[List[T]] = [[unit()] for _ in range(self.n)]
 
        # 最終結果（1回目のDFSでは自身のsubtreeのみの結果が入る）
        ans: List[T] = [unit() for _ in range(self.n)]
        # 親に向かう辺
        parents: List[RerootingEdge | None] = [None for _ in range(self.n)]
        # 2回目のDFSで、親から伝播される値（apply済）
        from_parent: List[T] = [unit() for _ in range(self.n)]
 
        q = [0]
        while q:
            v = q[-1]
            if status[v] == 0:
                status[v] = 1
 
                # 親頂点をリンクリストから除く
                children_links = []
                for e in links[v]:
                    if status[e.tgt] == 0:
                        children_links.append(e)
                    else:
                        parents[v] = e
                links[v] = children_links
 
                for e in links[v]:
                    q.append(e.tgt)
            else:
                q.pop()
 
                if len(links[v]) == 0:
                    ans[v] = leaf()
 
                else:
                    acl = acc_left[v]
 
                    for e in links[v]:
                        acl.append(apply(ans[e.tgt], e))
 
                    acr = acc_right[v]
                    for i in range(len(acl) - 1, 0, -1):
                        acr.append(merge(acl[i], acr[-1]))
                    acr.reverse()
 
                    for i in range(1, len(acl)):
                        acl[i] = merge(acl[i - 1], acl[i])
 
                    ans[v] = acl[-1]
 
                status[v] = 2
 
        q = [0]
        while q:
            v = q.pop()
            fp = from_parent[v]
            ans[v] = merge(ans[v], fp)
 
            acl = acc_left[v]
            acr = acc_right[v]
            for li, e in enumerate(links[v]):
                pe = parents[e.tgt]
                tgt_data = merge(fp, merge(acl[li], acr[li + 1]))
                from_parent[e.tgt] = apply(tgt_data, pe)
                q.append(e.tgt)
 
        return ans
 
 
n = int(input())
 
# 1: その部分木内でゲートを使った場合の最小コスト
# 2: 部分木の頂点数（v そのものの頂点の +1 は未反映）
# 3: 部分木の最大深さ（v そのものの深さの +1 は未反映）
# 4: 最後に訪れる枝として選ぶときの、1 から省略できるコスト差分
leaf_factory = lambda: (0, 0, 0, 0)
unit_factory = lambda: (0, 0, 0, 0)
 
 
def merge(a, b):
    a1, a2, a3, a4 = a
    b1, b2, b3, b4 = b
    return (a1 + b1, a2 + b2, max(a3, b3), max(a4, b4))
 
 
def apply(p, e):
    p1, p2, p3, p4 = p
    p2 += 1
    p3 += 1
    best_cost = min(p1 + 2, p2 * 2 - p3)
    last_cost = min(p1 - p4 + 1, p2 * 2 - p3)
    return (best_cost, p2, p3, best_cost - last_cost)
 
 
rrt = Rerooting(n, leaf_factory, unit_factory, merge, apply)
 
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    rrt.add_edge(u, v, 0)
    rrt.add_edge(v, u, 0)
 
result = rrt.solve()
 
ans = 1 << 60
for p1, _, _, p4 in result:
    ans = min(ans, p1 - p4)
 
print(ans)

            

        
      