ABの二完だが、レートは上がった。
コンテスト後のツイート
AtCoder Regular Contest 182 ABの後ずっとDを考えていたが分からなかった。
— titia (@titia_til) August 11, 2024
A 左右を見て、それより前に使うものでV_iより大きいものがあってはダメ。それより後で使うものでV_iより小さいものがあってはダメ。
B 二分木
D 難しい場合、端の方は同じ方向に回しそう、から考察が進まなかった。
C - Sum of Number of Divisors of Product
解説AC。
積の和典型の練習をしようと思って解こうとしたが難しく、解説を読んでもしばらく理解できず非常に苦労した。
公式解説のように積の和典型を適用すると、タワーと積み木の問題と同等になることは分かる。しかし、それがbit DPで表せることが分からなかった。（ChatGPTに聞いたりしつつ悩んだ）
・どこかで積み木を選ぶのだから、積み木を置いたそのときに選べば良い
と考えると理解できた。
たとえば、「6」の積み木を置くとき、それは、2と3の位置に積み木を一個ずつ選ぶことを意味する。
そして、それまでに2の位置や3の位置の積み木を選んでなかったとしたら、このときに選べば良い。
その、既に選んだかどうかでbit DPをしている。
また、最初に積み木が一個ずつ置いてあり、それを選んでも良いので、bit DPの初期値は全て1になる。
こういう考え方でDPを書いたものが、この提出。これを行列累乗で高速化するとACできる。