終了五分前に7ペナの末、FをACして全完。全完できたとはいえ、ちょっと喜べない出来。
D - Base n
二分探索の上限の設定と、Xが一桁の場合をミスって1ペナ。
後者については、1WA出した後、Xが一桁なら答えが無数にあるのでは？ と思って問題文を見直したら、「Xをn進法表記の数とみなして得られる値」が何種類あるか問われていることに気付きました。
パッと理解するのは難しい文章だと思うので、1ペナで切り抜けられたのならまあ良いか。
F - Potion
部分和っぽい問題なので、一目DPを考えたくなります。ただ、素材の個数が絡んでくるから上手くDPできなそう……？ と分からなくなり、使わない個数は少なくてもなぜか上手くいったりするのかな？ とか考えてしまった。
実際はDPでOK。
素材の個数のせいで分かりにくいなら、素材の個数を決め打って、それぞれの場合についてDPすれば良いです。計算量が増えそうでちょっと不安だけど、$O(N^4)$としてはかなり軽くなるので、PyPyでも通ります。
落ち着いて見れば自然な解法なんだけど、長いこと迷走してしまった。
0 件のコメント:
コメントを投稿