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

programming_algorithm/contest_history/atcoder/2022/0619_arc142.txt · 最終更新: 2022/06/23 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0