AtCoder Regular Contest 142 D問題メモ

AtCoder Regular Contest 142

コーナーケース発見力がよわよわだった。速解き回でこれは致命的。

D - Deterministic Placing

• $N$ 頂点の木が与えられる
• いくつかの頂点にコマを置く
  • 1つの頂点におけるコマ数は0個か1個。ただし全頂点0個というのはなし
• 「コマを、今いる頂点に隣接する頂点の中から好きに選んで移動させる」のを全てのコマで同時に行う操作を考える
• 操作のうち、以下の2条件を満たすものを「よい操作」と呼ぶ
  • 操作中に、辺上でコマが衝突しない
  • 操作後に、1頂点に2つ以上のコマがない
• ここで、初期のコマの置き方は $2^N-1$ 通りあるが、そのうち以下の2条件を満たす置き方が何通りあるか、$\mod{998244353}$ で求めよ
  • 「よい操作」を無限回行うことができる
  • 初期状態から、よい操作を繰り返し行った後の各操作後の状態（どの頂点にコマがあるか）は一意に決まる
• $2 \le N \le 2 \times 10^5$

初期状態から「よい操作」を1回行った後、各コマをさっきと逆方向に動かせば、それも「よい操作」で、初期状態に必ず戻る。
これが一意に決まるのだから、操作は、初期状態と（一意に決まる）1回操作後の状態を交互に繰り返すしかないことがわかる。

木DPで解けそうな見た目をしているので、その方向で考える。
頂点1を根とした根付き木として、各頂点に対して、

• 奇数回・偶数回目の操作後にコマはある/ない
• ある場合、それは次に子に動く/親に動く
• ない場合、次に子からコマが来る/親からコマが来る

などで場合分けして、その時々の、部分木内のコマの置き方のパターン数をDPすればよさそうだが、とにかく遷移がややこしい。

結構な試行錯誤を経て、以下の場合分けでよいとなる。

• 用語定義
  • t0: 初期状態または偶数回の操作後の状態
  • t1: 奇数回の操作後の状態
  • 親黒: その頂点にコマが置かれていて、コマは親との間を行き来する
  • 子黒: その頂点にコマが置かれていて、コマは子との間を行き来する
  • 親白: その頂点にコマが置かれていない。次に親からコマが来る
  • 子白: その頂点にコマが置かれていない。次に子からコマが来る

(t0, t1) でどの状態か？

• ①a: (親黒, 子黒)
• ①b: (親黒, 親白)
• ②a: (子黒, 親黒)
• ②b: (親白, 親黒)
• ③ : (子黒, 子黒)
• ④ : (子黒, 子白)
• ⑤ : (子白, 子黒)

○:白  ●:黒  ◎:どちらでもよい・不定

  ①a          ①b          ③                 ④
     t0  t1       t0  t1       t0      t1        t0  t1
親   ◎  ●       ◎  ●
     ↑  ↓       ↑  ↓
     ●  ●       ●  ○       ●      ●        ●  ○
     ↑  ↓                   ↙↖    ↗↘       ↓  ↑
子   ●  ◎                  ◎  ●  ●  ◎      ◎  ●

②a,②bは①a,①bのt0とt1を交換したもの、⑤は④のt0とt1を交換したものとなる。

奇数偶数両方の操作後ともコマがない場合というのは、よい操作が一意に決まらないので除外して考えてよい。

それぞれの遷移を考える。特に、複数の子をマージする場合に、一意に決まらなくなってしまう場合を注意する。

• ①a
  • 子の中に ①a or ①b が1つ必要、ただし2つ以上あると衝突するため不可
  • 他の子の中で、②a,②b があると明らかに衝突するため不可
  • 他の子の中で、t1が白の頂点（④）が1つでもあると、t0からの操作が一意に決まらなくなるため不可
  • 他の子の中で、t0が白の頂点（⑤）が1つでもあると、t1からの操作が一意に決まらなくなるため不可
  • よって、「1つのみ ①a or ①b を含み、他の子は③のみ」
• ①b
  • 子の中で ①a,①b,②a,②b があると衝突する/状態が合わないため不可
  • 子の中で、t0が黒の頂点（③④）が1つでもあると、その頂点にとってのt0の操作が一意に決まらなくなるため不可
  • よって、「子は⑤のみ」
• ②a
  • ①aと同様に考えて、「1つのみ ②a or ②b を含み、他の子は③のみ」
• ②b
  • ①bと同様に考えて、「子は④のみ」
• ③
  • 子の中に (①a or ①b) が1つと、(②a or ②b) が1つ必要
  • 他の子の中で、t1が白の頂点（④）が1つでもあると、t0からの操作が一意に決まらなくなるため不可
  • 他の子の中で、t0が白の頂点（⑤）が1つでもあると、t1からの操作が一意に決まらなくなるため不可
  • よって、「(①a or ①b) 1つ、(②a or ②b) 1つ含み、他の子は③のみ」
• ④
  • 子の中に ②a or ②b が1つ必要
  • 他の子の中で、t0が黒の頂点（③④）が1つでもあると、その頂点にとってのt0の操作が一意に決まらなくなるため不可
  • よって、「1つのみ ②a or ②b を含み、他の子は⑤のみ」
• ⑤
  • ④と同様に考えて、「1つのみ ①a or ①b を含み、他の子は④のみ」

で、上記を考えるとき、①aと①b、②aと②b の結果はくっついていても計算に問題は無いので、計算上はまとめてよい。

子をマージするときは、DPの要領で、基本は各子の③,④,⑤のパターン数を掛け合わせつつ、 「既に①を1回選んだ/まだ選んでない」などで場合分けして、1回のみ①を含むパターン数などを求めればよい。

Python3

n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)

MOD = 998244353

# result[v] = [v1,v2,v3,v4,v5]
# v1: 奇数回目に親に移動する、部分木内のパターン数
# v2: 偶数回目に親に移動
# v3: 親には移動しないが、奇数・偶数のいずれの手順後にも駒が置かれている（異なる2つの子とのやりとり）
# v4: 初期または偶数回操作後のみ駒が置かれている
# v5: 奇数回操作後のみ駒が置かれている
result = [None for _ in range(n)]

status = [0] * n
q = [0]
while q:
    u = q[-1]
    if status[u] == 0:
        status[u] = 1
        for v in links[u]:
            q.append(v)
            links[v].remove(u)
    else:
        q.pop()
        dp3_00, dp3_01, dp3_10, dp3_11, dp4_0, dp4_1, dp5_0, dp5_1 = 1, 0, 0, 0, 1, 0, 1, 0

        for v in links[u]:
            a1, a2, a3, a4, a5 = result[v]
            ndp3_00 = dp3_00 * a3 % MOD
            ndp3_01 = (dp3_00 * a1 + dp3_01 * a3) % MOD
            ndp3_10 = (dp3_00 * a2 + dp3_10 * a3) % MOD
            ndp3_11 = (dp3_01 * a2 + dp3_10 * a1 + dp3_11 * a3) % MOD
            ndp4_0 = dp4_0 * a4 % MOD
            ndp4_1 = (dp4_0 * a1 + dp4_1 * a4) % MOD
            ndp5_0 = dp5_0 * a5 % MOD
            ndp5_1 = (dp5_0 * a2 + dp5_1 * a5) % MOD
            dp3_00, dp3_01, dp3_10, dp3_11, dp4_0, dp4_1, dp5_0, dp5_1 = \
                ndp3_00, ndp3_01, ndp3_10, ndp3_11, ndp4_0, ndp4_1, ndp5_0, ndp5_1

        result[u] = [(dp3_01 + dp5_0) % MOD, (dp3_10 + dp4_0) % MOD, dp3_11, dp5_1, dp4_1]

res0 = result[0]
ans = (res0[2] + res0[3] + res0[4]) % MOD
print(ans)