https://atcoder.jp/contests/past202107-open/tasks/past202107_o
前提知識
解説
https://atcoder.jp/contests/past202107-open/submissions/24477460
最初の考察方針というのはだいぶパフォーマンスに影響すると思う。
今回の問題も制約が普通で、色々方針が見えそうではある。
DPが正しい方針であるが、それをなんで見出したかといわれるととても困ってしまう。
前置きはいいとして、解説に入ろう。
性質①
まずは重要な性質を取り出しておく。
それは入力に対して適切な変換を施すことで、Bを狭義単調増加にすることができるという部分である。
仮にB[i]≧B[i+1]になっている部分があったとすると、i日目を通過できているということはB[i]円以上の
コンピュータを持っているということであり、i+1日目は必ず通過できることになる。
よって、i+1日目は考慮する必要が無く、ただ所持金が増えるだけの日として、それ以降のBが狭義単調増加している日に
マージしてしまおう。
A B
===
2 4
1 3
6 8
となっていたら2日目は何もしなくてもお金が入ってくるので3日目とまとめてしまっていいので、
A B
===
2 4
7 8
のように変換できる。
この部分がまず分かっていないとこれ以降を理解することは難しい。
（理解はできても実装で困るかも）
自分の実装では前処理として、pre関数にてBが狭義単調増加になるように入力を変換している。
入力によっては最後に何もしなくても所持金が増える場合があるので、その分をpostとして別途分けている。
これ以降は、Bは狭義単調増加していると前提をして説明を進める。
性質②
行動として「好きな金額を支払ってコンピュータを購入できる」という部分が自由度が高い。
自由度が高いと選択肢が増えて取り扱いにくいので、少し考えてみる。
コンピュータを購入する意味は仕事を終えるためなので、仕事をこなすのに必要な金額以上のコンピュータを買う必要性はない。
加えて、自分が今持っているコンピュータより安いコンピュータを買う必要性もない。
よって、もう一つ重要な性質として、とある状況で購入するコンピュータの金額は、今持っているコンピュータより高額で、
配列Bのいずれかの金額に絞ってよいということになる。
これで少なくとも遷移はO(N)におさめることができるようになる。
DPテーブル
問題のDPテーブルは以下のようになる。
dp[i] := i日目の夜の仕事を終えた（その夜に必要なコンピュータを購入済み）ときの所持金の最大値
遷移は結構複雑。
dp[i]からdp[j]への遷移について考えてみよう。
dp[i]の状態ではi日目の夜に必要なコンピュータを持っているので、次の日はこのままでは仕事ができない。
だが、遷移先はdp[j]であるので、i+1日目の昼に買うコンピュータはj日目に必要なものになる。
よって、遷移できる条件はj日目のコンピュータの金額 ≦ dp[i] + (i+1日目の朝もらえるお金)となる。
もし、この時に買うことができるならば、j日目まではコンピュータを買わずに済むため、購入後の所持金は
dp[i] + (i+1～j日目の朝もらえるお金) - (j日目のコンピュータの金額)
となる。
高速化のために累積和を使って朝もらえる金額をうまく変換しておこう。
dp[i] + （～j日目の朝もらえるお金) - （～i日目の朝もらえるお金) - (j日目のコンピュータの金額)
これがdp[j]の候補となる。
ここまで理解できていると嬉しいが、これを貰うDPで実装したものが
提出 #24476595 - 第七回 アルゴリズム実技検定
になる。dpだけ1-indexedで、それ以外が0-indexedでなんのことか分からないかもしれないが、参考程度に見てみてほしい。
まずはここまでくればO(N2)が達成できる。
ここまでわかってくればいい所まで来ている。
DP高速化
今回高速化したい部分というのは、
- j日目のコンピュータの金額 ≦ dp[i] + (i+1日目の朝もらえるお金) という条件をiが満たす中で
- dp[i] + （～j日目の朝もらえるお金) - （～i日目の朝もらえるお金) - (j日目のコンピュータの金額)の最大値
2番目の部分では貰うDPだとjについては固定なので、dp[i] - （～i日目の朝もらえるお金)の最大値が欲しいということになる。
これにはいくつか解決法がある。
自分はpriority_queue, multisetで実装をしたが、色々やり方がありそうではある。
priority_queue, multiset
自分の実装では以下のような関数を用意して実装した。
- add(i)：dp[i]についてデータ構造に追加
- cut(limit):満たすべき条件を考慮して、現在のデータ構造から候補を削る
- getOpt(): 条件を満たす中での
dp[i] - （～i日目の朝もらえるお金)の最大値
今回この手法が使えるのは、「j日目のコンピュータの金額」が狭義単調増加しているからである。
priority_queueを使って条件に使用されるdp[i] + (i+1日目の朝もらえるお金)を保持しておき、日付が増えるにつれて、
「j日目のコンピュータの金額」が増えていくので、priority_queueの先頭（最小）を見ながら条件を満たさないものを
あぶりだして候補から消していく。
候補についてはmultisetで別途管理して、priority_queueから除外されたらmultisetからも消すようにする。
multisetでは最大値を持ってきたいdp[i] + (i+1日目の朝もらえるお金)を入れておき、消せるし、最大値も取れるしという
状況にしておく。
int N; ll A[201010]; int B[201010];
ll dp[201010];
ll post = 0;
ll tot[201010];
void pre() {
int NN = 1;
int ma = B[0]; ll tot = 0;
rep(i, 1, N) {
tot += A[i];
if (ma < B[i]) {
A[NN] = tot;
B[NN] = B[i];
NN++;
ma = B[i];
tot = 0;
}
}
post = tot;
N = NN;
}
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
min_priority_queue<pair<ll, ll>> contains;
multiset<ll> candicates;
void add(int idx) {
contains.push({ dp[idx] + A[idx], dp[idx] + A[idx] - tot[idx] });
candicates.insert(dp[idx] + A[idx] - tot[idx]);
}
void cut(ll limit) {
while (!contains.empty()) {
auto to = contains.top();
if (to.first < limit) {
contains.pop();
candicates.erase(candicates.find(to.second));
}
else return;
}
}
ll getOpt() {
auto ite = candicates.rbegin();
if (ite == candicates.rend()) return -infl;
return *ite;
}
void _main() {
cin >> N;
rep(i, 0, N) cin >> A[i] >> B[i];
pre();
tot[0] = A[0];
rep(i, 1, N) tot[i] = tot[i - 1] + A[i];
tot[N] = tot[N - 1] + post;
rep(i, 0, N + 1) dp[i] = -infl;
dp[0] = 0;
add(0);
rep(j, 1, N + 1) {
cut(B[j - 1]);
ll opt = getOpt();
if (-infl < opt) {
dp[j] = opt + tot[j - 1] - B[j - 1];
add(j);
}
}
ll ans = -1;
if (-infl < dp[N]) ans = dp[N] + post;
cout << ans << endl;
}
