yukicoder 1330 Multiply or Divide
$ dp_i := $ i回操作をするときの$ xの値の最大値 としてDP.
まず, 問題の構造を考察する. すると, $ A_iを素因数分解したとき, $ Pの部分は取り除かれることがわかる.
ただし最後の操作のみは例外で, 次の操作まで進まないのでこの場合は元の$ A_iのままである.
これらを踏まえ貪欲に考える. あらかじめ元の$ A_iの最大値をもっておき, $ A_iを$ Pで割れるだけ割り, 割った回数ごとの配列の最大値を更新しておく.
その後$ dp_iの値を次に掛ける値の割った回数を全探索し, 前計算しておいた回数を用いて計算する.
答えは$ i * (元のA_iの最大値) > Mとなるような最小の$ iに1を足したものとなる. そのような$ iが存在しなければ-1となる.
ちなみに, DPではなく同じ$ A_iのみ用いる貪欲法による嘘解法が本番中通った(自分もやってしまった).