C、通したかったな。
AB2完。Cは終了後にAC。
A - p-binary
最初のとっかかりが分かりにくかったが、個数を固定して作れるか考えると を
個の
の和で表現できるか？という話になる。これは ARC164-A とほぼ同じ設定で、簡単に解ける。
B - Power Products
素因数分解した上で、各素因数の指数を すればもう一方の相方(の素因数の指数)が分かる。後はその相方をオーバーフロー回避のため途中で打ち切りつつ具体的に求めれば良い。 AGC003-D とほぼ同じ考え方。 Div1-B にしては簡単？
C - Rock Is Push
マス目ごとに何かを管理する の DP だとは考えたが、岩の状態が同じマス目にいて、かつその後の進行方向を固定しても(その後に通りうる部分でさえ)一意に定まらないのでどうすればいいか分からなかった。
解説を開くとそのマス目で方向転換すればいいというのがあり、確かにこれなら岩の状態が一意に定まるなあとなった。マス目 DP において今いるマスを方向転換のキーとして持っておく考え方、覚えておきたい。
