G - Takahashi's Expectation 2 解説
by 
MMNMM
\(i\) 番目に受け取るプレゼントの価値が \(P _ i\) であるようなプレゼントの列を整数列 \((P _ 1,P _ 2,\ldots,P _ M)\) で表します。 プレゼントの列 \(P\) に対して、高橋くんのテンションが \(T\) である状態から \(P\) を順に受け取ったあとの高橋くんのテンションを \(t _ P(T)\) で表します。
プレゼントの列 \((P _ 1,P _ 2,\ldots,P _ M)\) が良い列であることを、\(1\le i\lt M\) なるすべての整数 \(i\) に対して \(P _ i+A\le P _ {i+1}\) が成り立つことと定めます。 高橋くんが良い列を順に受け取る場合、ある整数 \(i _ {\mathrm C}\) が存在して \(1\le i\lt i _ {\mathrm C}\) に対して \(i\) 番目のプレゼントを受け取ったときはテンションが下がり \(i _ {\mathrm C}\le i\le M\) に対して \(i\) 番目のプレゼントを受け取ったときはテンションが上がります。 このことを用いて、良い列 \(P\) に対する \(t _ P(T)\) の値を \(T\) が与えられるごとに \(O(\log M)\) 時間で求められます。
\(2\) つのプレゼントの列 \(P\) と \(Q\) が等価であることを、任意の \(T\) に対して \(t _ P(T)=t _ Q(T)\) が成り立つことと定めます。 \(\displaystyle\lim _ {T\to+\infty}t _ P(T)-T=-B\times|P|\) なので、等価な列どうしの長さは等しいです。
どのようなプレゼントの列に対しても等価な良い列が存在します。 実際にプレゼントの列に対して等価な良い列を構成するアルゴリズムを示し、これを利用してこの問題を解きます。
長さ \(2\) のプレゼントの列 \((p,q)\) が良い列ではないとします。このとき、列 \((q-A,\max\lbrace q,p-B\rbrace)\) が \((p,q)\) と等価な良い列です。
証明
\((q-A)+A=q\le\max\lbrace q,p-B\rbrace\) よりこれは良い列です。
\(t _ {(p,q)}(T),t _ {(q-A,\max\lbrace q,p-B\rbrace)}(T)\) の値を比較することで等価であることを示します。
\(T\) は \(T\le q-A,q-A\lt T\le p,p\lt T\le q+B,\max\lbrace{p,q+B}\rbrace\lt T\) のいずれかを満たします。
\((p,q)\) が良い列ではないので、\(q-A\lt p\) です。
- \(T\le q-A\) が成り立つとき、どちらの列に対しても高橋くんのテンションは \(2\) 回上がります。よって \(t _ {(p,q)}(T)=t _ {(q-A,\max\lbrace q,p-B\rbrace)}(T)=T+2A\) です。
- \(q-A\lt T\le p\) が成り立つとき、\((p,q)\) では高橋くんのテンションは上がったあと下がり、\((q-A,\max\lbrace q,p-B\rbrace)\) では下がったあと上がります。よって \(t _ {(p,q)}(T)=t _ {(q-A,\max\lbrace q,p-B\rbrace)}(T)=T+A-B\) です。
- \(p\lt T\le q+B\) が成り立つとき、どちらの列に対しても高橋くんのテンションは下がったあと上がります。よって \(t _ {(p,q)}(T)=t _ {(q-A,\max\lbrace q,p-B\rbrace)}(T)=T+A-B\) です。
- \(\max\lbrace{p,q+B}\rbrace\lt T\) が成り立つとき、どちらの列に対しても高橋くんのテンションは \(2\) 回下がります。よって \(t _ {(p,q)}(T)=t _ {(q-A,\max\lbrace q,p-B\rbrace)}(T)=T-2B\) です。
以上より、\((p,q)\) と \((q-A,\max\lbrace q,p-B\rbrace)\) が等価であることが示されました。
良い列 \(P\) の末尾に価値 \(q\) のプレゼントを追加した列 \(P\mathop{+\!\!+}(q)\) と等価な良い列は、\(M\) を \(P\) の長さとして \(i=M,M-1,M-2,\ldots,1\) に対して順に、\(i\) 番目と \(i+1\) 番目からなる部分列が良い列でないなら上の結果から得られる等価な良い列に置き換えることで得られます。
証明
\(2\) つの列 \(P,Q\) の連結 \(P\mathop{+\!\!+}Q\) に対して \(t _ {P\mathop{+\!\!+}Q}(T)=t _ Q(t _ P(T))\) が成り立つので、プレゼントの列の中の連続する部分列を、その部分列と等価な列に置き換えたものも全体として等価です。 このことから得られる列が等価であることがわかるので、操作によって良い列が得られることを示せばよいです。
はじめから連続して \(k\) 回置き換えを行ったとき、列は \((P _ 1,P _ 2,\ldots,P _ {M-k},q-kA,\max\lbrace{q-(k-1)A,P _ {M-k+1}-B}\rbrace,\max\lbrace{q-(k-2)A,P _ {M-k+2}-B}\rbrace,\ldots,\max\lbrace{q,P _ {M}-B}\rbrace)\) になります。
\(1\le i\lt M-k\) に対する \(P _ i+A\le P _ {i+1}\) および \(M-k+1\le i\lt M\) に対する \(\max\lbrace{q-(i-M)A,P _ i-B}\rbrace+A\le\max\lbrace{q-(i-M+1)A,P _ {i+1}-B}\rbrace\) が成り立ちます。
\(k+1\) 回目の置き換えを行わない場合、\(P _ {M-k}+A\le q-kA\) もしくは \(k=M\) が成り立っているためこの時点で列が良い列になっています。 よってこの後は置き換えが行われず、操作が終わったときの列が良い列であることが示されました。
良い列 \(P\) の末尾に良い列 \(Q\) を連結した列 \(P\mathop{+\!\!+}Q\) と等価な良い列は、上記の操作を \(Q\) の先頭から順に行うことで得られます。 これを愚直に行うと \(O(|P||Q|)\) 回操作することになりますが、ソート列のマージと似た要領で先頭の要素から定めていくことで \(O(|P|+|Q|)\) 時間で等価な良い列を得ることができます。
高橋くんが受け取る予定のプレゼントの個数を \(M\) として、\(M\) を相異なる \(2\) べき \(2 ^ {e _ 0}\gt2 ^ {e _ 1}\gt\cdots\gt2 ^ {e _ k}\) の和で表します。 受け取るプレゼントのうち \(\displaystyle\sum _ {0\le i\lt j}2 ^ {e _ i}\) 番目から \(\displaystyle\sum _ {0\le i\le j}2 ^ {e _ j}\) 番目（0-indexed）からなる連続する部分列と等価な良い列を求めておきます。
すると、質問クエリに対しては \(k=O(\log M)\) 個の良い列を順に受け取ったときのテンションの値を求められればよいため \(O\bigl((\log M) ^ 2\bigr)\) 時間で、追加クエリに対しては適切に \(0\) 個以上の列をマージすればよいためならし \(O(\log M)\) 時間で処理ができるようになり、この問題を解くことができました。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
int main() {
using namespace std;
cin.tie(nullptr);
ios::sync_with_stdio(false);
unsigned N;
long A, B;
cin >> N >> A >> B;
vector<long> P(N);
for (auto&& p : P)
cin >> p;
// 良い列の列
vector<vector<long>> seq;
// 十分小さい値
static constexpr long min_sentinel{-800000000000000};
// 2 つの良い列をマージして等価なひとつの良い列を作る
const auto merge{[N, A, B](auto&& lhs, auto&& rhs) -> vector<long> {
const long L(size(lhs)), R(size(rhs));
vector<long> result;
result.emplace_back(min_sentinel); // 番兵
result.reserve(L + R + 1);
for (long l{}, r{}; l < L || r < R; )
// 先頭から値を決める
result.emplace_back(l == L || (r < R && lhs[l] - r * B > rhs[r] - (L - l) * A) ?
rhs[r++] - (L - l) * A :
max(result.back() + A, lhs[l++] - r * B));
result.erase(begin(result)); // 番兵を消す
return result;
}};
// 新しい列を追加する
// 末尾と長さが等しければ、末尾を取り出してマージ
const auto append_seq{[&seq, &merge](const auto& rec, vector<long>&& p) -> void {
if (empty(seq) || size(seq.back()) != size(p))
seq.emplace_back(move(p));
else {
auto lhs{move(seq.back())};
seq.pop_back();
rec(rec, merge(move(lhs), move(p)));
}
}};
for (const auto p : P)
append_seq(append_seq, vector{p});
unsigned Q;
cin >> Q;
for (unsigned i{}; i < Q; ++i) {
unsigned T;
long X;
cin >> T >> X;
if (T == 1)
append_seq(append_seq, vector{X});
else {
for (const auto& s : seq) // 良い列ごとに
// 二分探索をしてテンションの変化を求める
X += A * size(s) - (A + B) * *ranges::partition_point(views::iota(0UL, size(s)), [X, &s, B](const long i){
return X > s[i] + i * B;
});
cout << X << '\n';
}
}
cout << flush;
return 0;
}
投稿日時:
最終更新: