AtCoder Regular Contest 182

　ABの二完だが、レートは上がった。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 182 ABの後ずっとDを考えていたが分からなかった。
A 左右を見て、それより前に使うものでV_iより大きいものがあってはダメ。それより後で使うものでV_iより小さいものがあってはダメ。
B 二分木
D 難しい場合、端の方は同じ方向に回しそう、から考察が進まなかった。

— titia (@titia_til) August 11, 2024

C - Sum of Number of Divisors of Product

　解説AC。

　積の和典型の練習をしようと思って解こうとしたが難しく、解説を読んでもしばらく理解できず非常に苦労した。

　公式解説のように積の和典型を適用すると、タワーと積み木の問題と同等になることは分かる。しかし、それがbit DPで表せることが分からなかった。（ChatGPTに聞いたりしつつ悩んだ）

・どこかで積み木を選ぶのだから、積み木を置いたそのときに選べば良い

　と考えると理解できた。

　たとえば、「6」の積み木を置くとき、それは、2と3の位置に積み木を一個ずつ選ぶことを意味する。

　そして、それまでに2の位置や3の位置の積み木を選んでなかったとしたら、このときに選べば良い。

　その、既に選んだかどうかでbit DPをしている。

　また、最初に積み木が一個ずつ置いてあり、それを選んでも良いので、bit DPの初期値は全て1になる。

　こういう考え方でDPを書いたものが、この提出。これを行列累乗で高速化するとACできる。