今日解いた競プロの問題。

競プロ典型90問-073: ☆5で唯一解けず放置していたが、あらためてやってなんとか自力AC。木DPの練習ということのようだったが練習にしては厳しすぎないか？

適当に根を決めて根付き木とする。各ノードについてDPで以下の3つの値を算出する。

• そのノードの連結成分にaしか含まれず、また全ての子ノードについてその連結成分がa,b双方を含むような切り方のパターン数
• そのノードの連結成分にbしか含まれず、また全ての子ノードについてその連結成分がa,b双方を含むような切り方のパターン数
• そのノードの連結成分にa,b双方が含まれ、また全ての子ノードについてその連結成分がa,b双方を含むような切り方のパターン数

それぞれ$dp[i]_a, dp[i]_b, dp[i]_{ab}$とする。

$c_i=$aのときこうなる。

• $dp[i]_a$の条件を満たすのは、ab双方を含むような子ノードを切り離しなおかつaのみを含むような子ノードのみを連結させた場合なので$d[i]_a=\prod (dp[k]_{ab}+dp[k]_a)$
• $dp[i]_b$の条件は満たされないので$dp[i]_b=0$
• $dp[i]_{ab}$の条件を満たすのは…
  • ab双方を含むような子ノードを連結させる
  • ab双方を含むような子ノードを切り離す
  • bのみを含むような子ノードを連結させる
  • aのみを含むような子ノードを連結させる
  • bのみを含むような子ノード又はab双方を含むような子ノードを最低1つ連結させる
    場合なので
    $dp[i]_{ab}=\prod (2dp[k]_{ab}+dp[k]_a+dp[k]_b)-\prod (dp[k]_{ab}+dp[k]_b)$

$c_i=$bの場合も同様に考えられる。

これ、もともと考え方に慣れているかもしくは実際に手を動かさないと$\prod$が出てくる理由が分からないんじゃないかと思う。解説は読んだが、自力でこれを解けない人間があの解説を読んで納得できるとは思えない。

---

チェンソーマン3巻を読んだのに感想書いてなかったので書いておく。

デンジくん、頭の良さが全く隠しきれていない。痛がってるのに気づく観察力とあの作戦に思い至る発想力があるし。あと永久機関が完成したらノーベル賞ものっていう認識、普通にそれなりの教養じゃね？？？というツッコミを入れたくなる。

なんか急に銃持ったのが出てきたのはびびった。マキマは、まあ、なんかネットで漏れ聞こえる前評判から考えるとあれで死んでるとは思えないが、姫野がこんな早く退場するとは思わなかった。

---

出し損ねた課題レポートを遅れながらも出せた。良かった。

しかしまだまだ次のレポートが待っている。厳しい。