問題のリンク
ABC222-Dの解説を読んでも中々理解できなかったのですが、実は階段DP(これみたいな問題)の類題であると考えるとスムーズに理解ができました。
まず、問題文を言い換えます。
高橋君は階段を作ることにした。しかし以下の2つのルールを守って作らなければならない。
- i段目の階段の高さをhiとすると、ai <= hi <= bi
- 階段は各段について広義単調増加になっていなければならない
この時、階段の作り方は何通りあるか?(入力、制約等は元の問題と一緒)
ここで、以下のようにDPを定義します。
dp[i][j] ... 1段目からi段目までで題意を満たすような階段が出来ていて、i段目の高さがjであるような階段は何通りあるか?dpの初期値はdp[0][0]のみ1、それ以外0です。dp[0][0]=1の意味を頑張って言語化すると、「階段が0段の時高さはもちろん0なので1通りある」みたいな感じです。
入力例1をこの考え方に適用して図式化したものが上の画像です。最終段(2段目)の総計の5が答えになります。
この図をよく見ると、まずk段目のdpは、k-1段目のみが影響している事がわかります。
また、dp[2][2]とdp[2][3]が同じ場所から値をとってきて同じ2になっていることから、どうやらdpに影響するのは1個前の階段の今の高さよりも低いDPの総計であることが分かります。
よって、漸化式は以下のようになることが分かると思います。
もう少し複雑な入力について考えてみます。
(入力)
N = 4, a = {1, 1, 2, 1}, a = {2, 3, 4, 5}
4段目の高さ0のdp(dp[4][0])の値が0になっているところからも、この考え方で元の問題の条件である広義単調増加を満たしていることがわかります。
以上です。実装方法については累積和、もしくはそれっぽいものを利用しないとTLEになってしまいます。
(提出したコード)