戻すDPわからない
はてなでの数式の扱い良くわからなくて意味わからないことになっている
戻すDPわからない
随分前から名前を見てたものの学ぼうとしてなかった
コドフォに出たことでTLでめっちゃ見えたので流石にやろうと思ったら理解に苦しんだので自分のためだけにブログを書く
実際には深く理解してないので意味のわからないことしか書けないけど
yukicoderのこれを見て理解できる人は すごいと思う.これが理解できるような人になりたい人生だった.
概要
DPで数え上げをするときに特定の要素を特別扱いしたくなることがある
そのとき,要素の順番を変えてもDPの結果が同じになるような場合ではその要素がなかったときの結果が求められる
これは例えばdp[i][j] := i番目まで見てi-1番目がj個残ってるとき
みたいな定義になるとダメ,多分(自信がない)
この場合でも当然,N
個目を取り除いた場合が知りたければN-1
個目までしか
処理しなければ求められるけど,戻すDPが適用できる場合はそれが何個目の要素のときでもできるよというのが本質
戻すDPが適用できる条件は次の2つ
1. 要素の順番が数え上げに関係しない
2. DPの漸化式を式変形することでdp[i] = dp[i+1] * ... + ...
みたいな雰囲気ができる
このとき,2.ができるためには情報が消えてはいけないので遷移に場合分けがあったらダメ
3問戻すDPを使う問題を解いたのでそのときの気持ちと解法を下に書く
注文の多い高橋商店
とりあえず簡単すぎると言われている方が解けないことには話にならないので解く.
僕ぐらいになるとここで詰まってしまうから悲しい
単純に考えるとDPの遷移は として一行目のようになっている
このままだと計算量大爆発(ぐらい)なため,累積和を使うことで削減できるがめんどくさい
ここでで計算したものが二行目のようになっていることを考えると引いて式変形することで三行目のような遷移になり単純になる
このとき,漸化式は左辺にが来るようなもらう形になってるとなんか戻しやすい気がする.そんな関係ないかも
よって普通にDPができたので,これを戻せれば勝ち
ちなみに添字が0未満になるところは0として考える.これは場合分けになるから戻せなくなるのでは?みたいな気持ちになるけど0未満になる場合はありえなくて実際0通りなので問題ない.
僕はget(dp, i, j)
みたいな感じで呼んだらどっちか0未満なら0を返すみたいなのを用意した
戻した結果としてとなるdp2を求める
ここで漸化式を式変形して左辺にが来るようにするととなる.
なので,i番目を戻したい(除いた場合を考えたい)ときに行う遷移はとなり,右辺でを参照するときの添字を考えてが小さい方から回すことになる.
が求まったので,クエリの種類目をちょうど個使う時というのは種類目を使わないで個選ぶのと同じであることから答えはとなる.
コードは下のやつなんですが,この問題だけModIntを使っていない
int main(void){ for (auto& x : dp) for (auto& y : x) y = 0; for (auto& x : dp2) for (auto& y : x) y = 0; cin >> N >> M >> Q; a.resize(N); for (auto& x : a) cin >> x; dp[0][0] = 1; REP(i, N){ REP(j, M+1){ dp[i+1][j] = (get(dp, i+1, j-1) - get(dp, i, j-a[i]-1) + get(dp, i, j))%mod; } } REP(i, N){ REP(j, M+1){ dp2[i][j] = (get(dp, N, j) - get(dp, N, j-1) + get(dp2, i, j-a[i]-1))%mod; dp2[i][j] = (dp2[i][j] % mod + mod) %mod; } } while(Q--){ int64 k, x; scanf("%lld %lld", &k, &x); k--; printf("%lld\n", dp2[k][M-x]); } }
生放送とBGM
これは戻すDPなのかなあとなるけど戻すDPのところで紹介されてたので戻すDPだと思いながら考える(最悪)
特定の曲に注目して考えることになるので考えると,ある曲が再生されるときの通り数を全ての曲に対して求め足し合わせると答えになることがわかる
特定の曲が再生されるかどうかはその曲が再生され始める時間が以下なら良いのでにして,戻した後にを求めれば良さそうとなる
しかしこの問題では全部の順列に対して求める必要があるので,時間がになる組み合わせではなく順列が知りたい.更に特定の曲の後に流れる予定の部分についても順番が区別されるため,この両方を求めるために特定の曲までに何曲流したのかも欲しい.
なのでとしてDPを行う.
これを戻すと という配列が手に入るため,答えは を求めた後に期待値なのでで割ればいい
僕は初心者なのでmodの問題でもないのにどうやってそんな大きい階乗をとれば...と思ってたけどdoubleでやれば大丈夫だった(それはそう)
肝心のDPの遷移と戻し方だが,普通のDPはでできる.
このときに配るDPをやろうとして,更に時間の合計がL以上になる部分はまとめていいだろ〜みたいな気持ちになり とかやると,が実質的に場合分けになっているので戻せなくなる.この場合は戻すときに にどこから足されたかがわからなくなってしまうため
どちらの場合でも,この問題では一回戻すため一回戻せるだけの余裕をもたせる必要がある.
一曲の時間の最大値を とおくと配るDPなら のとり方を にすれば良くて(普通のDPをする際には を までしか回す必要がないので配列を十分にとっておけばminを取らなくてもいい)
もらうDPなら を まで回せばいい
このとき,戻すDPの遷移は でできる
今回も が小さい方から回すことになる
コード,initでfactを初期化している.
さっきのもそうだったけどdpの添字や配列名があってないのは空間計算量削減とかあるので許してください.
int main(void){ init(); cin >> N >> L; L *= 60; S.resize(N); REP(i, N){ int64 m, s; scanf("%d:%d", &m, &s); S[i] = m*60+s; } vector<vector<int64>> dp(N+1, vector<int64>(L+60*60+1, 0)); dp[0][0] = 1; REP(i, N){ vector<vector<int64>> dp2(N+1, vector<int64>(L+60*60+1, 0)); REP(j, N+1){ REP(k, L+60*60+1){ dp2[j][k] = get(dp, j-1, k-S[i]) + get(dp, j, k); } } swap(dp, dp2); } double res = 0; REP(i, N){ vector<vector<int64>> dp2(N+1, vector<int64>(L+60*60+1, 0)); REP(j, N+1){ REP(k, L+60*60+1){ dp2[j][k] = dp[j][k] - get(dp2, j-1, k-S[i]); if (k < L && N-j-1 >= 0) res += dp2[j][k] * fact[j] * fact[N-j-1] / fact[N]; } } } cout << fixed << setprecision(10) << res << endl; }
Destroy the Colony
問題概要
僕が読解に苦しんだのでこれだけ問題概要
偶数長の英文字(大小)からなる文字列が与えられる
これの並び替えのうち,文字列を前後半に分けた時に同じ文字が同じ側にある並び替えは嬉しい(Destroy the Colonyできる)
このとき次のクエリが与えられるので処理しなさい
- とが同じ側になるような並び替えは何通りあるか出力せよ
とが同じなら普通に全部の嬉しい並び替えを答えればいいみたいな感じ
クエリの種類が実質種類しかない(とが逆でも答え一緒なので実際は半分強)ので先に計算しておけば勝ち
明らかに特別扱いしたいものがあるので戻すDPだなとなるが,2つあるので当然2回戻す
答えの求め方が僕の考えたTLEするやつと解説の方法がある.
解説のほうが明らかに明快(僕には難しくて難解だった)なのでそっちを先に書いて,僕の考えたやつは最後に書く(読みたい人は読んでって感じ)
解説解
それぞれの文字種がいくつ現れるかをとする. この時, 個ずつになるように分ける組み合わせがわかれば,そのときの組み合わせを とすると,前半と後半それぞれについて重複順列を求めてかけ合わせたものに をかければいいので下のようになる
以外の部分はどういう分け方でも共通なのであらかじめ計算しておく
じゃあを求めればいいねとなり,これは上の二問よりも簡単では?みたいな気持ちになる
ここでとするととなる.
これを戻す形にするとになる
の範囲としては,2回戻す分必要かつそれぞれの文字種の個数が決まってないのでまで回す必要がある?(ないかも)
文字種で一回戻したときを,文字種で更に戻したときをとすると,でがわかり,全く同じことをしてでが求まる
なら, そうでなければとなる
各についてを求め,それを用いて各についてを求めればいいので,計算量は使用されている文字の種類数をとするととなり,である.
戻すときの処理が全く同じなのでそこを関数化すると簡単にかけるらしい
コード,僕はそれをしていない
MintがModIntで,fというのはFactorialライブラリ,f.comb(a, b)
でを返す.
めっちゃコードが長くて何が起こってるかわからないね
これが1970msぐらい
int main(void){ vector<int64> c(52, 0); cin >> s >> q; n = s.size(); REP(i, s.size()) c[ctoi(s[i])]++; Mint W = f[n/2]*f[n/2]; REP(i, 52) W /= f[c[i]]; vector<Mint> dp(n+1, 0); dp[0] = 1; REP(i, 52){ if (c[i] == 0) continue; vector<Mint> dp2(n+1, 0); REP(j, n+1){ dp2[j] = get(dp, j-c[i]) + get(dp, j); } swap(dp, dp2); } vector<vector<Mint>> ans(52, vector<Mint>(52, 0)); REP(i, 52){ if (c[i] == 0) continue; vector<Mint> t1(n+1, 0); REP(j, n+1){ t1[j] = get(dp, j) - get(t1, j-c[i]); } REP(j, 52){ if (c[j] == 0) continue; if (i == j) { ans[i][j] = t1[n/2]; continue; } vector<Mint> t2(n+1, 0); REP(k, n+1) { t2[k] = get(t1, k) - get(t2, k-c[j]); } ans[i][j] = t2[n/2]; } } while(q--){ int32 x, y; scanf("%d%d", &x, &y); x--; y--; x = ctoi(s[x]); y = ctoi(s[y]); cout << ans[x][y] * W * 2 << endl; } }
僕の解法
DPは万能なので,DPで組み合わせだけ求めてそれに並び替えをかけなくても最初から並び替えた後を求められるじゃ~んみたいな気持ちになっていた
つまり, をした.
ここで,既に個あるところにこれを並び替えず同じ種類のものを個追加したときの並べ方は,ある種類のもの個と別の種類のもの個の並べ方と同じなのでとなる.
とする
前半に種類目を追加するか後半に追加するかの二通りの遷移があるので合わせて となる
これを戻す形にすると下のような形になる.
戻す文字種を先ほどと同じようにとすると,文字種を並び替えて一番後ろからにして,分母のが一回目はであることから,二回目はとなる.
こっちが最初に書いたやつなので答えの部分がすこしごちゃごちゃしてます.
二回戻した後,が求まったら取り除いている分を追加したときの並び替えを答えないといけないので,が答えになります
後は組み合わせが0になってゼロ割してしまわないように気をつけて下のコードのようになります
さっきのが1970msぐらいなので,遷移が定数倍重くなってるこっちは当然TLEします.
お疲れ様でした,多分test9までは通ってるので解法としてはあっているはず
int main(void){ cin.tie(0); ios::sync\_with\_stdio(false); vector<int64> c(52, 0), sum(53, 0); cin >> s >> q; n = s.size(); REP(i, s.size()) c[ctoi(s[i])]++; REP(i, 52) sum[i+1] += sum[i] + c[i]; vector<Mint> dp(n+1, 0); dp[0] = 1; REP(i, 52){ if (c[i] == 0) continue; vector<Mint> dp2(n+1, 0); REP(j, n+1){ dp2[j] = dp[j] * f.comb(sum[i]-j+c[i], c[i]) + get(dp, j-c[i]) * f.comb(j, c[i]); } swap(dp, dp2); } vector<vector<Mint>> res(52, vector<Mint>(52, 0)); vector<Mint> t1(n+1, 0); vector<Mint> t2(n+1, 0); REP(i, 52){ if (c[i] == 0) continue; REP(j, n+1) { if (n-j >= c[i]) { t1[j] = (get(dp, j) - get(t1, j-c[i]) * f.comb(j, c[i])) / f.comb(n-j, c[i]); } } FOR(j, i, 52){ if (c[j] == 0) continue; if (i == j) { res[i][j] = t1[n/2] * f.comb(n/2, c[i]) * 2; continue; } REP(k, n+1){ if (n-c[i]-k >= c[j]) { t2[k] = (get(t1, k) - get(t2, k-c[j]) * f.comb(k, c[j])) / f.comb(n-c[i]-k, c[j]); } } if (c[i]+c[j] <= n/2) res[i][j] = res[j][i] = t2[n/2] * f.comb(n/2-c[i], c[j]) * f.comb(n/2, c[i]) * 2; } } while(q--) { int64 x, y; cin >> x >> y; x--; y--; x = ctoi(s[x]); y = ctoi(s[y]); if (x == y) { cout << res[x][y] << endl; } else if (c[x] + c[y] > n/2) { cout << 0 << endl; } else { cout << res[x][y] << endl; } } }