ABC-B 81-116
を解きました。
Bを解くついでにCの考察だけしてみていたが、改めて見返すと結構間違えている。
scoresのパイチャートを真緑にするために、明日は残っている1-41を片付ける。
ABC-B 50-80
今日は色々と忙しかったのでB問題をちまちま。
新たに学んだことは特にないが、自明な問題を瞬殺する訓練にはなる気がする。
ARC-A 1-57
昨日のABCでCの早解きができなかった & Dで初歩的な考察ミスでWAにハマり時間切れになってしまったのを受けて、ABC-Dの前にARC-Aの旧基準を片付けてしまうことにする。最近のABC-Bぐらいの難易度だろうか。
このところ重い問題が多くて精神を削られていたのと、AtCoder problems上での(見た目の)進捗が悪いので、息抜きがてらARC 1-57まで一気に埋めた。
新しく知った知識 & 忘れていたこと
・スペース区切りのstring入力は while(cin >> s){ … }
・std::mapはキーの順にソートされて格納。
・stoi, to_stringでint, stringの相互変換。
・next_permutationが便利。int型配列とかでもok。
何かこう、自分の中でエンジンがかかるまではWAやREを連発しがち。
コンテスト前や難しい問題に掛かる前に簡単な問題をいくつか解くのが良いかも。
ポンポンACが取れると精神ゲージが回復していく。
ABC 118 & ABC-D 53-56
3回目のコンテスト参加。
33分 3完で 833th。
パフォーマンス 1121
rating 815 → 872 (+57)
無念。
やはり全完できないとABCではパフォーマンスは全然出ない。
D問題は方針は立っていたのだがどうしてもWAになってしまうケースが残ってしまった。20分かけても原因を特定できずにタイムアップ。
C問題は解説を読むと最大公約数でユークリッドの互除法使う問題だったらしい。
自分はといえば、Aiの最小値で他全てのmodを計算 -> 0になったものを除いて再び残りの最小値でmodを計算 …としてAの要素数が1になったところでその値をprintというコードを書いた。最大公約数であることに気付ければ本来一瞬で解ける問題だった。
D問題は9, 8, … 1の順で、使用可能でかつ最終的な桁数が変わらないような数字をdfsで入れていくという方針で書いた。3が使えるとき2を使う理由がないとかそういうのをいれて高速化するとTLEしない。
ただ、どうしても4つWAが取れないで終わってしまった。
コンテスト中20分かけても原因がわからなかった。
想定解はDPだったようだ。
WAの原因は桁数を固定してしまったところ。
最適桁数の値がそもそも存在しない可能性が取り入れられていなかった。
以下のように、dfsの実行を桁数の値を徐々に減らしながら行えばよかった -> AC
while(!flagout){
dfs(0);
maxdig--;
}
コンテスト中はただコードを眺めて原因を特定しようとしてしまった。
やはりD問題が解けるかどうかはdp力が左右するようだ。
以下、今日やったABC-D解答メモ。
ABC53
カードを食うな。
3枚以上あるカードは確定で操作。
n -> n-2になる。
結果、全てのカードが2枚以下になるまで続けることができる。
11 22 3 4 55のようになったら、
112 -> 1 2 3 4 55
1 55 -> 2 3 4 5
にできる。
2枚以上のカードの組の数は一回の操作でm-> m-2になる。mが0以下になるまで繰り返せばok
よってやるべきは、カードの枚数を数えることと、3枚以上を処理したあとの2枚の組の数の偶奇の判定。
15分ぐらいでAC。
ABC54
N=40なあたり半分全列挙で解けそう。
たとえば、N/2とN-N/2で組み合わせを列挙して、Aの重量/Bの重量でソートしておく。
前半組の各々に対してパートナーをlog(2^{N/2})で見つけられればOK。
前半組の重量比が Ma/Mbより大きい場合、それと組み合わせられるのは後半でMa/Mbより小さいもの。
ただ、重量比では二分探索ができない。
前半をa, b, 後半をc, dとしたとき
(a/b - Ma/Mb) + (c/d - Ma/Mb) = 0が条件。
-> a/Ma - b/Mbでソートする。
これなら二分探索で探せる。
-> subtask05以降が全滅(WA)
原因がわからん。
-> 想定解はDPで、O(N^2 A B)の解法。
dp[i][ca][cb] := i 番目までの薬品の組み合わせで、物質 A が ca グラム、物質 B が cb グラムとなる溶液の最小コスト
半分全列挙による解があることも触れられているが詳細は書いてない。
dpの方が解きやすかったはず。制約に引っ張られすぎた。
この人は半分全列挙で解いている。mapを使うのが良いっぽい。
mapで書き直してAC。おそらく探索部分に問題があった。
-(a/Ma - b/Mb)を探すというコードだと、doubleの差の誤差で思うような動作をしないというのが原因か。
a *Mb - b*Maなら良いのかというと、今度はうまくソートできなくなる。
前半、後半をあわせた総重量を j としたときに、ある与えられた後半組のパートナーが
(Ma * j - after.A, Mb *j - after.B)になるということを使うことで、mapで探せる。
自分の解答はパートナーの決め方についての考察が甘かった。
半分全列挙のパートナーを探すときは、単調性などに依存せず該当する値をダイレクトに探せるmapの方が向いている。
ABC-Dで半分全列挙が要求される問題はそうそうでないだろうという気付きも必要だったかもしれない。
教訓: 半分全列挙にはmap。慣れてない手法を使う前に他の選択肢を検討する。可能な限り浮動小数点計算は回避する。
ABC55
s[i] = ‘o’の場合、t[i-1]とt[i+1]は等しい。
s[i] = ‘x’の場合、t[i-1]とt[i+1]は異なる。
WとSにt[i]を分類すれば良い問題。
Union findみたいな感じで解けそう。
予めunionを２つ用意しておけばいい。W, Sを割り当てておいてok
iの小さい方から見ていくとき、i+1を見た時点でi-1のunionは決定している。一周回って矛盾がなければok
無矛盾に調べていくのが意外と面倒。
0, 1を決め打ちして調べる？
途中まで狼と羊でx, oの振る舞いが違うことに気づいてなかった。
解けたけど時間かかりすぎ。
どうせ0, 1を決め打ちして調べるならunionfindなんぞ持ち出す必要もなく、矛盾しないか確かめるだけで良かった。
ABC56
カード i を含むある部分集合の総和をXとしたときに、
X > K ならば X - ai > K
が成立するなら i は必要。
aiが非常に大きいとき、明らかに条件は満たされない。
aiは小さくなければならない。どのくらい？
X > K ならば X - ai > K
とはつまり、Xにはaiをのぞけるだけの余裕があるということ。
K = 1のとき、条件を満たすものは存在しない。
K = 2のとき、ai = 1が一つだけある時それが条件をみたす。
K = 3の時、ai = 1, 2 が一つで他全て 3以上ならok
もしくは、ai = 1が２つでほか全て3以上ならok
ここから、条件をみたせるのは
-
K未満の数字
-
他のK未満の数字との組み合わせが全てK未満
-
K以上の数字が少なくとも１つ存在
が全て満たされるとき？
もっと複雑。例えば
K = 9
{1, 5, 5}
で1は条件を満たす。
K以上の数字は一つにまとめてしまって良い。
与えられた数列は
{a1, a2, .., an, K以上}
という形。ここでa1, …, anはK未満で昇順とする。
※「aiを除くことで条件が満たされなくなるのは、
部分集合の総和がK -ai以上 K 未満のものが存在する時。」
K = 2のとき、a1 = 1, a2 = 1でアウト。
K = 3のとき、a1 = 1, a2 = 2でアウト。
a1 = 1, a2 = 1は、K-a1 = 2なので問題ない。
というわけで、※でok。このときaiは必要。
i を含まない部分集合の和であって、K未満のものの最大値をリストアップしたい。
部分和を処理する方法がわからない。
dp[i][K]としたときに更新できるか? -> 無理。
除くカードについて独立にやればいい。
あるカードを除いたあとの状態について、
dp[i][j] : i枚目まで使ったときjにできるか
とする。これでO(N^2 K)になる。
あとは単調性を使って高速化。
-> REする。
二分探索を行わないO(N^2K)のコードでもRE, WAしている。
N =1のケア & K以上の数値の処理。
->なんとか部分点までは終了。あとはこれを二分探索に。
二分探索のやり方で混乱した。
不必要と必要の境界が欲しいので、おおまかには
middleが必要ならright = middle
middleが不要ならleft = middle
だが、最初に必要になる箇所をもとめるには？lower_boundのようなことをする。
オチとしては
middleが必要なとき right = middle
middleが不要なとき left = middle +1
とするのが正しい。
教訓: ある値を作れるか否かの管理にはDPがよい。
どうやったら自力で解けていたか。
問題が※の形で言えること、dpっぽいというところまではできていた。
除く数字について独立に解くという方針は、O(N^2 K)になりそうという時点で考察を切ってしまっていた。
やはり、aiの値について、不要、必要に単調性があるという点に気づけていなかったのが問題。
D問題だと現状では半分ぐらいしか解けない。時間内だと1/3ぐらいか。
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
Educational DP contest P-S
いつの間にか土曜にBeginnerコンテストが追加されていた。
目標はパフォーマンス1500, rate1000載せ。ここまで順調なのでそろそろ失敗しそう。
ABCの3完は確保したい。
今日は3問 + 途中で終了。
EDPコンテストも後半になって１問１問が重くなってきた。
コンテストの設計として、序盤は200点ぐらい、終盤は800点ぐらいの感覚らしい。
J-Sushiあたりから明らかに難易度が上がっている。
Q問題のようにセグ木を要求するものや、Rのように繰り返し自乗法を要求するものなど、DP + αが必要な問題が出てきている。
S問題はまだ終わっていない。方針は立っているのだが、実装で混乱したまま。
桁dpはまだ練習量不足が否めない。
以下、解答メモ。
P - Independent Set
treeなので、特定のノードをルートとして考えて良い。
dfs順で見たときにあるノードを黒に塗ると、その先のノードは全て白で確定する。
あるノードを白に塗った場合は、その先は任意。
木が一直線であれば
dp[i][0] : i番目が黒のときのi番目までの塗り方
dp[i][1] : i番目が白のときの…
dp[i+1][0] = dp[i][1]
dp[i+1][1] = dp[i][0] + dp[i][1]
で良い。branchをどう処理するか。
葉から決めていったほうがいい。
dp[i][0, 1]を、iを根とする部分木の塗り方の総数とすれば、
dp[root][0] + dp[root][1]で解が得られる。
メモ化再帰によってこれを葉から決めていく。
漸化式は
dp[i][0] = Π dp[ children ][1]
dp[i][1] = Π( dp[ children ][0] + dp[ children ][1])
各部分木の塗り方の積で計算
探索済みフラグの処理が面倒。上位ノードが白の場合と黒の場合で２回探索が入る。
-> 部分木の探索を終えた段階で再びunusedにすれば良い。木なので不都合は生じない。
-> WA & TLE。WAは計算途中のint溢れ。TLEは、上でunusedにしてしまっているので当然だった、
結局探索済みの管理をどうするか。
木なので、自分の親に遷移しないという条件だけで十分。再帰関数に、部分木の根とその親をもたせる。-> AC
Q - Flowers
LISに似ているが、評価値が部分列の長さではない。
int 溢れに注意。
制約からして、どの花を残すかを考えるのは不可能。
i 本目までで作られる部分列でSUM(ai)最大のものが分かっているとき、
i+1本目が来たときにあり得るケースとしては、
・単純に部分列の右端に追加
・部分列の一部を削りh_{i+1}を入れる。
の2パターンがある。
LISの時を思い出すと、長さnの部分列のうちで最も右端の値の小さいものを配列に記録するするという方針。
この配列は必ず単調増加になるので、二分探索によってO(L log L)で更新できるという話だった。
dp[i][0] =index of rightmost, length i
dp[i][1] = sum of a, length i
としてみたらどうか？
新しいエントリーに対して取りうる操作は、単純に右に追加する or 一番右の要素を置き換える。
このままでは、各 i に対してlengthのループが回るのでO(N^2)。これを二分探索とかで減らしたい。
dpの更新が発生するのは、
a_i+1 - dp[k][0].a >= 0 かつ dp[k][0].h>= h_i+1のとき。
-> 各 i で最適にしようとすると、新しい i に対してO(N)の更新が必要になる。
-> わからん。
花の高さについてdpすると良いらしい。
「h <=N でh1…hNが全て異なる」という制約をもっと真剣に捉えるべきだった。
最も右端がh_iであるような部分列の最高値をdp[h_i]とすると、
dp[h_i] = a_i + max( dp[h_j] where h_j < h_i and j < i)
が成立する。これをiの小さい順に更新していけば良い。
maxを求める部分はセグメント木を使ったRMQで O(log N)にできる。
RMQ要求する問題はAtCoderでは初めて出会ったかも。
LISっぽいところに気づくのは良かったが、そもそもLISの解法を間違って覚えていた。
正しくは、dp[h] = 部分列の最大要素がhのときの最大部分列長
LISっぽい -> dp[h]かな？ -> でもa_iだから単調じゃなくて二分探索できない -> じゃあ気合でRMQ
という思考の流れができれば解ける問題。
セグメント木はスニペット化してあるのでそれを使ってAC。
R- Walk
Kの制約がバカでかい (K<=10^18)。
Nが小さい。O(N 2^(N/2))が回るぐらい。
とりあえず、始点についてのループは必須。
Kについてdpすることができない。
dpするにしても、まず全探索だとどうなるか考える。
Kが大きいときはひたすらループを回して稼ぐことになる。
ループを使わない場合の最大パス長はNなので、 K>=Nであればループの検出が重要になる。
Kそのままでは管理できない。仮にK = 2^nとしてみる。
dp[i][j][n]: 始点 i, 終点 j でパスの長さ 2^nの組み合わせとすると
dp[i][j][n+1]は、2^nのパスと2^nのパスの連結なので、
dp[i][j][n+1] = Σk dp[i][k][n] * dp[k][j][n]
という漸化式が書けそう。 ここまでは10^7ぐらいのループで回る。
上記が求まっていれば、Kのビット表示から計算できるはず。
たとえば、 K = 5 = 4 + 1は dp[0]とdp[2]から。
この場合、長さKで始点i, 終点jのパスの総数は、
Σ_k dp[i][k][0]*dp[k][j][2]
で与えられる。しかし、このままだと計算しきれない。
dp[i][k][n]を、i, kを足に持つ行列 M[n] と見ると、求める値は
M[n1] M[n2] … M[kn]
の全要素の和で(N^3)^kなので回らない。
-> いや、O(k N^3)だろ何言ってんだ。
そんなこんなで、時間はかかったが一発AC。行列積のコードをミスっていて気が滅入ったが。
bit DPを正しく着想できたところは非常に良かった。
解いてから冷静に見直してみると、入力行列をK乗して全要素の和を取ればパスの総数になるということ。
上で書いたDPはこれを繰り返し自乗法で処理することに相当している。
dpの漸化式を立てた段階で行列積の形であることをもっと意識すれば、後半でグダることはなかったはず。
これで18問。最初の頃に比べて明らかにコード長が長くなってきたが、
dpは方針さえ正しければバグでWAを出したりは起こりづらい印象がある。
(バグっている場合はたいてい入力例すら通らないので)
5時間で26問はDP力もそうだが精神力が試されてる気がする。
EDPコンテストは、序盤200点相当、終盤800点相当の設定らしい。今は600点相当ぐらいだろうか。
TDPコンテストの難易度が不安である。
少し休憩して今日はあと1問やろう。
S- Digit Sum
露骨な桁DP
Dの倍数という部分がややこしい。
桁和の取りうる範囲は、1-900000
桁和の値を保持しながらのDPは不可能。
まず、桁和がDそのものであるものを求める問題を考えてみる。
桁和がDジャストの場合の問題が解けていれば、2^20 > 900000なので、高々その20倍の計算時間で解ける。
dp[i][j][d]を、i桁目まで見た上でK以下のフラグがjのときに桁和の値がdであるような組の総数
とする。
jは、上位桁が全てKと同じときにfalse,それ以外ではtrueとなる。
桁和をなんにせよ確定させないといけないので、後ろから埋めていくDPになる。
Dを超えるものについて切りたい。dをmod Dで考えれば一度に計算できる？
Kの桁数をN。Kのi桁目までの桁和 mod DをS[N], i桁目の値をk[i]とする。
dp[N][true][S[N]] = (S[N] == 0 mod D) //// others 0
dp[N][false][x] = SUM_{i=0…9} (1 if x+i == 0 mod D) /// 最終桁で調整できる。Dは10以下もあるので、この時点で複数の可能性もある。
dp[N-1][true][S[N-1]] = dp[N][true][S[N]] + dp[N][false][S[N-1] … S[N-1] + 9] // others 0
dp[N-1][false][x] = dp[N][false][x … x + 9]
dp[i][true][S[i]] = dp[i+1][true][S[i+1]] + dp[i+1][false][S[i] … S[i]+9]
dp[i][false][S[i]] =dp[i+1][false][x … x+9]
これで、O(2*D*10000 * 10)になるはず。O(10^7)なので回りそう。
-> 全然合わない…。0の処理がよくわからない。
明日に持ち越し。
Educational DP contest K-O
DP問題の考え方 (DP = DAG上の探索 として)
メモ化再帰では、トポロジカル順を意識する必要がない。
ループもメモ化再帰もどちらも、時間計算量O(E+V)、空間計算量(V)で同じ。
また、どちらか一方でなければ解けない問題というのはほぼ無い。
ループの利点としては、漸化式の評価が重いときに適切なデータ構造を使って高速化できる場合があることらしい
あと、メモ化だと再帰が深すぎると走らない(K問題が例)
今日は5問。少し慣れてきた。
bit DPのような基本的なテクニックをサクッと書けるようにしたい。
ゲーム問題がいくつかあるが、色々と記事を読んでいるとgrundy数やらの用語が出てくる。どこかで自分なりにまとめて練習を積みたいところ。
以下、解答メモ。
K - Stones
ゲーム木上のdp問題。
Aの元は何度でも使うことができる。
石の個数は増えない -> DAG
終状態では、石の残数がa1未満になっている。
最適に行動するという仮定をどう考えるべきか。
K = 1,…, a1-1では secondの勝ち。
K = a1, …, a1+a2-1ではfirstの勝ち
1ターンで勝負がつかない場合の行動は？
残りの石が k 個の時に firstの手番だったとする。
firstには、石を k-a1, …, k-anにする選択がある。
これらのうちで、その後のゲーム展開で必勝のものがあればそれを選択すればよい。
最適行動かつ引き分けなしというゲーム設定なので、kの更新時点でk-a1…k-anのすべてに勝敗が割り当てられている。
dp[k]: 残りk個のとき次に操作する人が勝つか否か、で考えてみる。
自明なケースの初期化は
dp[1…a1-1] = false
dp[a1…a1+a2-1] = true
...
dp[a1…a1+aN-1] = true
非自明なものは、
dp[ k ] = (if any dp[k-ai] = true)? true: false
可能な選択全てで負ける場合にfalseとする
更新順が自明な場合はループで書いたほうが良さそう。
上の議論は、ゲーム問題におけるWL Algorithmというものにほかならないっぽい。
L - Deque
大きい順に取っていくだけだと、
10 100 1 9のようなケースで相手に100を取られてしまう。
残った数列の先頭要素と末尾のインデックスを l, rとしたとき、
dp[l][r] = X - Yとなるようにしたい。
手番をどう管理するか。 r- l + 1 %2 == N%2なら先手
先手番
dp[l][r] = max( dp[l+1][r] + a[l], dp[l][r-1] + a[r])
後手番
dp[l][r] = min( dp[l+1][r] - a[l], dp[l][r-1] - a[r])
更新順は、[l, r]が狭い順。[l, l +d]としてdのループ -> lのループ
M - Candies
K個の区別できないボールを … に似ているが、一人に配れる飴の個数に上限がある。
寿司問題に似ている気がする。aiごとに分類する？
子供を区別する必要があるのと、k = 1, …, Kについて上限k個の子供が何人いるかを管理するのは難しい。
実験
K = 1の時、ai != 0の子供の数 x だけ配る方法が存在する。
K = 2の時、
K=1で配った結果としてキャパが0になった子供が存在する場合は x(x-1)
そうでない場合は x^2
子供についてdpしたほうが良さそう。
dp[i][k]: i人目までの子供にk個配る配り方
とすると、
dp[i+1][k] = Σ dp[i][k-x] ここでx = 0,…, a_{i+1}
が成立する。ただ、計算量が間に合うか不安。右辺は一般にO(K)必要。
保有可能量に関して子供をソートしておくことにする。
i = 1でのkの上限は a1で、i = 2の計算にはdp[1][0]…dp[1][a1]が必要。
i = 2でのkの上限はa1 + a2で、 i =3の計算には dp[2][0]…dp[2][a1+a2]が必要。
dp[i][y]が寄与する右辺を一度に扱えればよい。
dp[i][y]は、dp[i+1][y] …, dp[i+1][y + a_{i+1}]に寄与する。
dp[i][y]の累積和を計算しておけば、dp[i+1][ z ] はO(1)で更新できる。
dp[i+1][z] = cumSum(z+a_{i+1}) - cumSum(z-1)
cumSumがあればdp[i]の値は必要ないので、dp[x]をN回更新してdp[K]を求めれば良い。
累積和を使う以外に、漸化式を変形し、dp[i][y]をdp[i][w<y]を使って更新することでO(1)にすることもできるらしい
無理筋かどうかを判断するには回数こなすしかないのだろうか。
N - Slimes
AOJで見た行列連鎖積問題に似た雰囲気を感じる
終状態は大きさ a1 +... + aNのものが一つだけ。
最適手順での最初の1ステップが ak とak+1の間だったとすると、
[a1, …, ak-1], [ak + ak+1], [ak+2…aN]という問題に分割される。
dp[l][r]を [al…ar]を最適に結合させるときのコストとするならば解はdp[1][N]であり、
結合させる位置kに関して
= min_k dp[1][k-1] + dp[k+2][N] + sum(a1…aN)
dp[l][r] = min_k dp[l][k-1] + dp[k+2][N] + sum(al…ar)
sum(..)はaの累積和を計算しておけばO(1)
更新順が非自明なので、これをメモ化再帰によって解く。
-> 上の漸化式だと、入力例１のように一つずつ潰していくケースが入らない。
“最後”に潰すボンド k について場合分けして考える。
このとき、操作前の時点で
[1…k]、[k+1…N]がそれぞれ一つのまとまりになっている。kを潰すことで
[1…N]となり、それには sum(1…N)のコストがかかる。
どのkが最適か？
1…kの中での潰し方とk+1…Nの潰し方は互いに独立にコストを最小化できる。
よって、最終状態から逆に辿っていくことを考えると、
dp[l][r] = dp[l][k] + dp[k+1][r] + sum(al…ar)でよい。
解答に時間がかかりすぎてしまった。
再帰的な併合は、スライムの重量変化を扱いきれない。
O - Matching
i 人目まででマッチングが成立しているときにi+1人目が追加されるとどうなるか。
(Mのi+1とFのi+1がマッチ): (1..i 人目までの任意のマッチングパターン)
(Mのi+1とFのj, MのkとFのi+1がマッチ): (a_{i+1,j} == 1かつa_{k,i+1}を満たす j, kの組から作られるマッチングパターン)
後者をどう計算するかがキモ。
j, kの候補ごとに結果が異なる。 Fの1…j-1, j+1… i とMの1…k-1, k+1…iのマッチング総数 f(i,j,k)が必要。
制約が小さい(N <= 21)ことに着目。
各 i で、全ての可能な選択 N_C_i のそれぞれにマッチング総数を求めておけば、
i+1で上の計算をする場合にはそれを参照するだけでいい。
N_C_iで処理するの面倒そう。O(N 2^N)で通る？
-> 男女両方考慮すると2^2Nになるので無理。
combinationで真面目にやれば大丈夫? k, jは1…iの中で1つづつ選ぶだけ。
dp[i][j][k]を、i人目のマッチングであって Fのj番目、Mのi番目を使わない組み合わせの数
とする。dp[i][0][0]に全員使った場合の値を入れる。
dp[i+1][0][0] = if(a_{i+1.i+1} == 1, dp[i][0][0]) + SUM(dp[i][j][k] where a_{i+1,j} == a_{k,i+1} == 1);
dp[i+1][j][k]をどう埋めるかが問題。
dp[i][j][k]は、dp[i][0][0]のうちでマッチングがj - jかつk-k or j-k かつk-jのものの数に等しい。
-> 不可能ではなさそうだが実装が複雑すぎる。精神が折れた。
想定解はbit DP
dp[i][mask]: i番目のMまで見たときに、既に使用したFを表すビットマスク
これでO(N 2^N)になる。
i個のビットが立っている状態からの遷移だけ見れば良いので、キューで管理する。
制約から2^Nという予想 -> bit DPでは？という思考ができるように。
