ARC177-Dメモ
ARC177-D https://atcoder.jp/contests/arc177/tasks/arc177_d について、自分の考え方のメモ。
まず、確率に $${2^N}$$ を掛けて出せ、ということなので、これは場合の数を出せということ。棒ごとに$${2}$$ 通りのケースを持っていて、それが$${N}$$ 個集まれば$${2^N}$$ になって、これが全体なので、確率を求めるのではなく、「その回で全てが倒れる場合の数」を求めればOK。
さて、棒が連鎖して倒れる連結成分ごとに分けたとき、各連結成分は独立なので、連結成分毎に $${i_1}$$ 回目、$${i_2}$$回目、・・・を取ってきたら、その積の個数分の場合の数が $${\max\{i_1,i_2,…\}}$$ 回目で全て倒れる。
ちゃんと書くと：
連結成分の個数を$${K}$$ として、$${k}$$ 番目の連結成分が $${i}$$ 番目に全て倒れる場合の数を $${a_{k,i}}$$ とすると、$${i}$$ 回目に全て倒れる場合の数は、
$$
\prod_{\max\{i_1,…,i_k\}=i} a_{i_1}a_{i_2}…a_{i_k}
$$
となる。これは、愚直に回すと大変なことになるけれど、$${i}$$ より小さいものを連結成分毎にたしておいて、使うときに（$${i}$$ 番目が含まれる連結成分以外の）積を取ればよい。この積は毎回掛けていると時間が足りないのは、累積積を取っておけばいいのだけれど、modint はたまに 0 になることがあるので、セグ木を使ってかけ算することで 0割りを回避する。
で、自分的には難しかったのは一つの連結成分の各 $${i}$$ 回目での全部倒れる場合の数をどう計算するかの方で、これを再帰で求めた。
まず、一つの連結成分を考えたときに、その中で一番若いindexを $${i}$$ とし、またこの連結成分の個数を$${n}$$ とする。すると、この$${n}$$ 個のアイテムが倒れるときに全滅する場合の数がいくらかを求めればよく、その総数は $${2^n}$$ であることから、$${2^n}$$ を分配していく問題になる。そして、最初の$${i}$$ が左右どちらかに倒れることで場合の数を$${1}$$個分だけ消費するので、倒れたあとの部分問題が保有する場合の数は $${2^{n-1}}$$ 個になる。ポイントは、左右どちらに倒れても部分問題が保有する場合の数は $${2^{n-1}}$$ 個で、これは連鎖して倒れてしまったアイテムの分の、果たし得なかった場合の数も背負っていることになる。
計算は次のようにすればよい。
親問題から、割り当て場合の数（$${2^m}$$ とする）をもらう。連結成分の一番最初の操作なら$${m}$$ は連結成分の個数だが、連鎖で倒れた後の場合は部分問題がもつアイテム数より多いこともある。
部分問題の中で一番若いアイテムに注目する。$${i}$$ とする。
$${i}$$ の左側について
$${i}$$ の左にアイテムが存在すれば
$${i}$$ が右に倒れた場合には左側が残り、割り当てられた $${2^m}$$ のうち $${i}$$ が使用した$${1}$$個分を除いた $${2^{m-1}}$$ 個の場合の数を左側の部分問題に引き渡す。
$${i}$$ の左にアイテムがなければ
$${i}$$ が右に倒れた場合には全滅するので、「$${i}$$番目に全滅する場合の数」に $${2^{m-1}}$$ を加算する。
同様のことを、右側についても実施
例：連結成分内のアイテム番号が $${\{6,2,3,5,1,4,7\}}$$ のとき
割り付ける場合の数の総数は $${2^7}$$ 個。
最も若い$${1}$$番目に注目すると、
左に$${\{6,2,3,5\}}$$ があるので、この部分問題に対して$${2^6}$$を割り当てる。
右に$${\{4,7\}}$$ があるので、この部分問題に対して $${2^6}$$を割り当てる。
$${1}$$ 自体は、どちらに倒れても反対側が残るため、$${1}$$ で全滅する場合の数はゼロ。
$${\{6,2,3,5\}}$$ の部分問題も、最若の$${2}$$の両側にアイテムがあるので、
$${\{6\}}$$ に$${2^5}$$を、$${\{3,5\}}$$ に$${2^5}$$を割り当てる。
$${2}$$ で全滅する場合の数はゼロ。
$${2^5}$$ をもらった $${\{3,5\}}$$ では、
左に倒れたとき、$${2^4}$$ 個を $${\{5\}}$$ に割り当て
右に倒れたときは全滅するので、$${3}$$ で全滅する場合の数に$${2^4}$$通りを加算する。
$${\{4,7\}}$$ は$${\{3,5\}}$$ と相似だが、割当数は$${2^6}$$ なので、$${4}$$ で全滅する場合の数に $${2^5}$$ を、$${\{7\}}$$ 部分問題に $${2^5}$$ を渡す。
残りはすべて一本なので、どちらに倒れても全滅する。よって、割り当てられた分の全てがそのアイテムでの全滅数になる。$${\{5\}}$$ は $${2^4}$$が割り当てられており、$${\{6\}}$$と$${\{7\}}$$は $${2^5}$$ が割り当てられている。
結果、$${i=1,2,…,7}$$ についての全滅数は、$${0, 0, 2^4, 2^5, 2^4, 2^5, 2^5}$$ となる。全てたして $${2^7}$$ 通り。
このようにして再帰的に部分問題に場合の数を割り付けていけば、一つの連結成分についての「何回目で全滅する場合の数が何か」がわかる。割当数は再帰ごとに$${1/2}$$ して渡せばいいので、あと必要なのは、「部分問題で最若のインデックスはどれか？」と、「そのインデックスの左右それぞれにアイテムが（何個）残っているか」がわかればよい。これは、Cartesian Tree （参考：https://drken1215.hatenablog.com/entry/2023/10/19/025800 けんちょん氏）を作ればできる。
