AtCoder Regular Contest 027 - D ぴょんぴょんトレーニング
解説とは違う方法なので
問題
N個の石があって，i番目の石はi+1..i+H\[i\]にジャンプ出来る．
次のD個のクエリに答えたい：s番目の石からt番目の石へ移動する方法の数を答えよ．
キーワード
- 行列演算表現を用いた動的計画法
- 行列が乗ったセグメントツリー
TLE解法1
Submission #3092464 - AtCoder Regular Contest 027
愚直にクエリごとに時間O(t-s+1)の動的計画法をする．
普通に問いても良いけれども，問題の特性を用いた書き方をすることにした．
H[i] <= 10 の制約から，dpに必要な配列サイズは sizeof(integer)*10 で済む*1．
↓ これの改良1と同じ事をしています．
ll N, D; ll H[300010]; void applyDP(vector<ll>& dp, int p) { ll zero = dp[0]; repeat(i, 11) { if (i >= H[p]) zero = 0; dp[i] = (zero + dp[i + 1]) % MD; } } void preprocess() { } ll solve(ll s, ll t) { --s; --t; vector<ll> dp(12); dp[0] = 1; iterate(i, s, t) { applyDP(dp, i); } return dp[0] % MD; } int main() { scanner >> N; scanner.in(H, H + N); scanner >> D; preprocess(); repeat(i, D) { ll s, t; scanner >> s >> t; printer << solve(s, t) << '\n'; } return 0; }
TLE解法2
Submission #3092570 - AtCoder Regular Contest 027
このタイプのDP遷移は，行列で書き直すことが出来る．
この行列をpからp+1に遷移するためのDP遷移行列(p,p+1)*2と呼ぶことにする．
void applyDP(valarray<llmod>& dp, int p) { ll zero = dp[0]; Matrix<llmod> mat(10, 10, valarray<llmod>{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }); repeat(i, H[p]) mat(i, 0) = 1; dp = multiply(mat, dp); }
考察
観察すると，DP遷移行列(p,p+2) = DP遷移行列(p+1,p+2)*DP遷移行列(p,p+1) が分かる．演算順序に注意．
もし，DP遷移行列(s,t) を高速に求めることが出来れば，初期化されたDP配列に DP遷移行列(s,t) を掛け，
sからtに遷移した後のDP配列を得て，そのDP配列から解が求まる．
行列(s,t) = 行列(t-1,t)*行列(t-2,t-1)*...*行列(s,s+1) のクエリに答えられるデータ構造と言えば，セグメントツリーである．
MLE
実装したのがこちら．（コードが長くなってしまったので載せませんが，）MLEしてしまう．
Submission #3092809 - AtCoder Regular Contest 027
行列のサイズは sizeof(ll)*10*10, セグメントツリーのために2の冪でNの2倍以上必要なので 1048576*sizof(行列)．800mbぐらい．
MLE回避
セグメントツリーの葉に近い部分をメモリに載せることは辞めて，毎回計算することにする．
また，事前計算でセグ木を埋める形にしていたのを，未計算ならば計算して保存するキャッシュのような実装にした．
Submission #3092906 - AtCoder Regular Contest 027
AC．最速からは程遠い．
