No.2302 Carry X Times
桁DPだという情報を得てAC。
桁DPだと分かった上で見ると桁DPの問題にしか思えないし、桁DPとしてはかなり書きやすい部類の問題で、すんなり書くことができた。
これを思い付けなかったのはまずい。
No.2303 Frog on Grid
解説AC。
縦・横それぞれについて、x回のジャンプで行く場合の数を計算し、それを組み合わせるという計算量H*Wの解法は分かったが、高速化が思いつかなかった。
FFTはちょっと考えたが、二項係数をかけるので無理だろうと諦めてしまったが、それぞれの配列を予め割る数で割っておけば良いのね。
FFTを使う問題での前処理としては難しくないものだと思う。こういう処理に慣れないと。
No.2304 Distinct Elements
解説AC。
slope trickの練習問題として解けるのだが、slope trick自体（DPテーブルが凸になっているという性質を利用する）も忘れていた。さらに、maspyさんの解説ツイートの、
・dp[x] = min_{y<=x}dp[y] + |x-a|
という式にも納得ができず、長いこと悩んでしまった。
いや、この式自体は分かっていたのかもしれないけど、この操作を累積minした後、|x-a|を加えるという操作で表せるということが納得できなかったのかもしれないけど……。
どちらにしても、slope trickを理解できていれば自然なものなので、ここで悩むのはおかしい。
0 件のコメント:
コメントを投稿