Educational DP contest S-U & ABC-D 51-52
EDPコンテストの終盤がグロすぎる(非常に勉強にはなる)ので、精神の安定を図るためにやはりD問題埋めを同時並行ですすめていくことにする。
EDPまあ数日で終わるやろと思っていたが無理&無理だった。
今日のEDPコンは、昨日やり残していた桁DPのS問題を終わらせたの + 新規で合計3問。
桁DP、DP×累積和、bit DPによる集合の管理&bit演算による部分集合の高速列挙など、EDPコンテストの終盤は応用的なDPや、DPと別の典型テクニックの組み合わせが要求される。
U問題は巡回セールスマンをちゃんとDPで解いたことがあれば思いつけたのだろうか。
精神回復を求めて数日ぶりにABC-Dをやったらだいぶ救われた。
特にABC-52の癒やしっぷりたるや。
以下、解答メモ。
S- Digit Sum (前日の続き)
昨日の考察は漸化式が間違ってた。
そもそもスタートは
dp[N][true][S[N]] = 1
dp[N][false][x%D] += 1 (if x < k[N])
であるべき。
結局以下のコードを書いたが、テストケース21だけがWAしている。計算時間、メモリ消費ともに小さいのでコーナーケース？
intmain() {
cin>> K;
cin>> D;
// Kの桁分解。
for(autoi = 1; i<K.size(); i++){
dig.push_back(K[i] - '0');
}
cumsum.push_back(dig[0]%D);
for(autoi = 1; i<K.size(); i++){
reverse(all(cumsum));
llN = (ll)K.size();
memo[N-1][1][dig[N-1]%D] = 1;
for(autoi = 0; i<dig[N-1];i++){
memo[N-1][0][i%D] += 1;
memo[N-1][0][i%D] %=MOD;
}
for(auton = N-2;n>=0;n--){
memo[n][1][cumsum[n]%D] = 1;
for(autoi =0; i<D; i++){
for(autoj = 0; j<dig[n];j++){
memo[n][0][(i+j)%D] += memo[n+1][1][i];
memo[n][0][(i+j)%D] %=MOD;
}
for(autoj = 0; j<10;j++){
memo[n][0][(i+j)%D] += memo[n+1][0][i];
memo[n][0][(i+j)%D] %=MOD;
}
}
}
cout<< (memo[0][1][0] + memo[0][0][0] - 1) %MOD<< endl;
return0;
}
オチとしては、(memo[0][1][0] + memo[0][0][0] - 1) < 0 をケアできていなかった。
llans = (memo[0][1][0] + memo[0][0][0] - 1);
if(ans <0) ans += MOD;
cout<< ans %MOD<< endl;
にしてAC。
教訓: 桁DPは上から処理する & MODの扱いに注意。
T- Permutation
dp[i][0]: i 番目が ‘<’のときの、サイズ i の数列で条件を満たすものの数。
dp[i][1]: i 番目が ‘>’のときの、サイズ i の数列で条件を満たすものの数。
という感じにしたくなるが、使われずに残っている数字を管理する必要がある。
O(3000^2)は回るので、
dp[i][j][0]: i 番目がs[i] == ‘<‘ でp_iより大きい未使用の数字が j 個あるときのサイズ i の配列の総数。
dp[i][j][1]: i 番目がs[i] == ‘>‘ でp_iより大きい未使用の数字が j 個あるときのサイズ i の配列の総数。
にしてみる。
dp[i][j][0]の場合、 p_i < p_{i+1}なので、p_{i+1}の候補が j 個あることになる。
ただし、dpを更新するのに、使用済みの数字が何かが効いてしまうのでは？
sは固定なので、<, > について管理する必要はない。
i 番目で、p_iより大きい未使用数字がj個のとき、i + 1番目はどう決まるか
・ s[i] == ‘<‘ のとき
p_{i+1}は j 個のうちのいずれか。k番目とするとdp[i+1][j-k] += dp[i][j]
・ s[i] == ‘>‘ のとき
p_{i+1}は...
p_iより小さい未使用数字も管理しないと解けない。とりあえず計算時間のことは無視。
・ s[i] == ‘>‘ のとき
p_{i+1}は、p_iより小さい未使用数字n個のうちのいずれか。その小さい方からk番目とすれば dp[i+1][j+n-k][k-1] += dp[i][j][k]
細かい添字は違うかもしれないが、とりあえず dp[i][j][n]で持てれば解けそう。
しかし、このままではi, j, n, kについてループでO(N^4)。
もっと単純？
i + j + n = Nが常に成立する。
つまり、 j, nについての和は実質O(N)しか回らないようにできるかも。
・s[i] == <
rep(k, j) dp[i+1][j-k][n+k-1] += dp[i][j][n]
・s[i] == >
rep(k, n) dp[i+1][j + (n-k)][k-1] += dp[i][j][n]
n = N - i - j
初期化は、最初の数字ごとに分けてやれば良いだけ。
p[1] = 1なら dp[1][0][N-1] = 1;
p[2] = 1ならdp[1][1][N-2] = 1;
…
dpテーブルをそのまま持とうとするとメモリが足りないので i の添字を落としたいが。
テーブルを毎回コピーするとN^3でアウト。
i + j + n = Nが常に成立するということは、 同じN*Nのテーブルを使っても、同じ成分が後々参照されることはないので問題ない。
ここまでやってもまだi, j, k でO(N^3)。k依存性を右辺で処理してRAQにできればO(N^2 log N)。
dp[i+1][j][n] = ?
s[i+1] == ‘<‘ のとき、
rep(j,N-(i+1)){
n = N - i - 1 - j;
rep(k,j){
dp[i+1][j][n] += dp[i][j-k][n+k+1]
}
}
s[i+1] == ‘>‘ のとき、
rep(j,N-(i+1)){
n = N - i - 1 - j;
rep(k,n){
dp[i+1][j][n] += dp[i][j+k+1][n-k]
}
}
dp[i][j+1][n], dp[i][j+1+1][n-1], …, dp[i][j+1+k][n-k], … dp[i][j+1+n][0] が log Nで計算できるようにしたい。
異なるjの値に応じて和を取る範囲が変わる。
ある i についての計算が終わった段階で, nに関して累積和を計算しておけばよい。累積和の計算はO(N)なのでこれでいける!
given な j に応じて、 テーブルの0 ,..., N-i-1-j 成分の総和 = cumsum[n] を加えれば良い。
‘<‘ のときは [0][n+j+1] …, [j][n+1]なので、 cumsum[n+j+1] - cumsum[n]
一文字ずつ、左側にあるoperatorを処理していくほうが良い。
s[i-1] == ‘<‘ のとき、i 文字目でn, j のものは？
i-1 文字目で 未使用の数字が残っているもの。下限 j + 1
i - 1文字目で未使用の数字は j+1個以上、 N - (i-1)個以下。
rep(j,N-i-1)){
n = N-1 - i - j;
rep(k, n-1 ){
dp[i][j][n] += dp[i-1][j+1+k][n-k]
}
}
= cumsum[n]
s[i-1] == ‘>‘ のとき、i 文字目でn, j のものは？
i-1 文字目で 未使用の数字が残っているもの。下限 n + 1
i - 1文字目で未使用の数字は n+1個以上、 N - (i-1)個以下。
rep(n,N-1-i)){
j = N-1 - i - n;
rep(k, j ){
dp[i][j][n] += dp[i-1][j - k ][n+1+k]
}
}
= cumsum[n+j+1] - cumsum[n];
酷く疲れたがなんとか一発でAC通せた。
dpテーブルの作り方、累積和による計算量の削減にたどり着けたのは良いが、そこからの実装 & デバッグに時間かかりすぎ。
トライ&エラーでデバッグしがちなのを辞めるのと、単純な実装力の強化。相変わらず、考察より実装のほうに時間がかかってしまう。
他の人の解答を見ると基本的に同じ発想だが、i + j + n = Nを使ってdpテーブルをもっと単純にしている。
dp[i][j] : i まで決めたときに、最後に置いた数字が未使用の数字の中で j 番目に小さいときの場合の数
自分の解法だとこれがdp[N-i-j][j] に当たる。
制約条件で実行変数を減らせるならそちらのほうがループ中の遷移が分かりやすいのでデバッグしやすい。
また、制約条件を処理しようとするとループの範囲とかを間違えやすくなる。
教訓: 解法を思いついても、より実装がシンプルなdpテーブルの作り方は無いかよく考える。
これでEDPコンテスト20問。
dpであるということが分かっているだけでだいぶとっつきやすいが、さすがに今の実力だとこの終盤は時間がかかってしまう(各問2hぐらいかかってる)。
体力的にも一日2-3問が限界。
U- Grouping
相性が全て正なら一つのグループにまとめてしまえばよいが…
N<=16と小さいので、巡回セールスマン問題のように状態を2^Nで管理するのかもしれない。
グループピングの状態を簡潔に表せないか？16^16は無理かつ無駄が多い。
何はともあれ、とりあえず全探索を考える。
一人目は任意のグループ g1
二人目は一人目と同じ or 違うでg2 = g1 or not = (g1, g2), (g1=g2)
三人目はg3 = g1 or g2 or other = (g1=g2, g3) (g1=g2=g3), (g1, g2=g3), (g1=g3,g2), (g1, g2, g3)
四人目は 5 + 3*2 + 3*1 + 1 = 15
5: 15 + 4*5 + 6*2 + 4*1 + 1 = 52
6: 5_C_0 *52 + 5_C_1*15 + 5_C_2 * 5 + 5_C_2 * 2 + 5_C_1*1 + 1 = 203
1, 2, 5, 15, 52, 203, ...
パターンは見えた、とりあえずOEISに突っ込んでみる
-> Bell or exponential numbers: number of ways to partition a set of n labeled elements.
ドンピシャ -> 全探索では10480142147 ~ 10^10 通りあるっぽい。
DPとして扱おうとする上でややこしいのは、部分問題で最適であっても全体で最適にならないところ。
i 人目までの最適なグループ分けは、i+1人目では全くダメというケースが有りうる。
1と同じグループか否かを各ノードについて考えて列挙するのは2^(N-1)で可能。
そもそも、全パターンをO(1)で調べられたとしてもO(10^10)で無理なのでは？枝刈りする？
たとえば、i 人目まで見たときに、それ以降のグループ分けで達成可能な最大値 Max[i]= SUM(a_jk + a_kj > 0, i<j)を用意しておいて、
ただ、しきい値を使った枝刈りは一般には上手くいかない。今の場合、得点の小さいものから探索されるようになっていると効果が出ない。
思いつかん。
-> bit DPでO(3^N)で解ける典型問題らしい。3?
コード自体はこっちを参考に
constintMAXN=16;
intn;
inta[MAXN][MAXN];
llsum[1<<MAXN];
lldp[1<<MAXN];
llsolve() {
FOR(mask,1,1<<n) { sum[mask]=0; REP(i,n) if(mask&(1<<i)) FOR(j,i+1,n) if(mask&(1<<j)) sum[mask]+=a[i][j]; }
FOR(mask,1,1<<n) {
dp[mask]=sum[mask];
intothers=(1<<n)-mask-1;
for(inti=(others+1)&mask;i<mask;i=(i+others+1)&mask) {
dp[mask]=max(dp[mask],dp[i]+dp[mask^i]);
}
}
returndp[(1<<n)-1];
}
上で、sum[mask]はmaskのウサギを全て一つのグループに入れた場合のそのグループの得点で、グループ分けを最適化したときの最高得点であるdp[mask]をそれで初期化する。
others = ~mask は、maskで考慮していないウサギの集合を表すマスク
トリッキーな int i のループでは、int iでmaskの部分集合を列挙して、それを分離させる方が得かどうかを見ている。今の場合 mask^i < mask なので更新順に問題はない。
なぜこれで部分集合が列挙できるのか
まず、(others + 1)&maskは、maskで最も右端にある1のビットを返す。
この i に対して (i + others + 1)&maskを行うと、maskで二番目に右にある1のビットが返る。
この i に対して (i + others + 1)&maskを行うと、maskの最も右端にある２つの1のビットが返る。
２進数の繰り上がりを上手いこと制御することでこれが続いていく。
教訓:
探索対象の状態が多く全探索が原理的に不可能であれば、部分問題の最適化と全体の最適化が矛盾しない分割を考える。
巡回セールスマン問題しかり、集合の管理はビットマスクで。ビット演算により部分集合の列挙を高速に行うテクニックがある。
典型問題は数をこなすしかない。
EDP後半がグロすぎて精神が持たないのでABC-Dで休憩。
ABC51
ワーシャルフロイドする。
最短経路に含まれているものを除いていく。
-> WAが取れない。
・辺をINF初期化するのを忘れていた
・d[i][i] = 0とするのを忘れていた。
せっかくライブラリを用意しても使い方を間違えていてはどうしようもない。
ABC52
めっちゃDP。
街 i -> i+1の移動はテレポート or ひたすら歩くのどちらか。
dp[i+1] = min (dp[i] + B , dp[i] + (X[i+1]-X[i])*A)
EDPコンテストで800点クラスにボコボコにされたあとではチョロい。
全ての500点台がこんなぐらいであって欲しい。
}
reverse(all(dig
