[AGC057] B - 2A + x
[Q] https://atcoder.jp/contests/agc057/tasks/agc057_b
0. 統合する。（しなくてもいい）
5 10 20 は、5は10とかぶるし、10は20とかぶるから、5と10は消去していい。
これは問題を少し単純にするだけの処理。
最大値の20を動かした消去判定を、してはいけない。
値が大きくなればなるほど、max-minは大きくなってしまう。
1. 各値について、2つの変動値をメモする。
10 30 50 70だとして。現時点での最大値70をtargetとする。
(a) *2+Xして、70以下の最大値をメモ。
(b) *2して、70以上の最小値をメモ。
2. (b)の値でN通りシミュレートする。
一番いいスコアが解答。
Q. (b) 2倍するだけの値が、どうしてmax値とみなしたときの最小とわかるの？
途中で*2+Xをはさんだ結果、よりtargetの70に近い70以上の値になることはないの？
A. なさそう。
もし近づくとしたら、それは0の統合処理に吸収されるべき。
実装
ll N, X;
ll A[100010];
int main(){
cincout();
cin >> N >> X;
rep(i, N) cin >> A[i];
set<ll> S;
rep(i, N){
S.insert(A[i]);
}
// まず重複している数字を統合する。5 10 20 があった場合、5 10 は 20 に吸収。
// これは省略してもいい。
for(auto s: S){
ll low = s*2;
ll high = s*2+X;
auto it = S.lower_bound(low);
while (it != S.end()){
if (*it <= high){
// low ~ highの間に遷移できるなら吸収。
S.erase(S.find(s));
break;
}
low *= 2;
high = high*2 + X;
it = S.lower_bound(low);
}
}
vector<pll> V; // high, low
V.reserve((ll)S.size());
for(auto s: S){
V.emplace_back(s, s);
}
ll vsz = V.size();
// targetをこえないhigh(毎回*2+Xする場合)と, targetを超えるlow(毎回2倍するだけ)をメモする。
ll target = V[vsz-1].first;
rep(i, vsz-1){ // こえないhigh, こえるlowに変更
auto &[high, low] = V[i];
while (low * 2 < target){
low *= 2;
high = high * 2 + X; // targetをこえないぎりぎりのhigh
}
low *= 2; // targetをこえる最小のlow
}
// low(target)をN通り置換する全探索。
sort(all(V));
// highだけでみると、最もtargetに寄った値に変換されているはず。
// V[].first = a, b, c, target(, a*2, b*2...)
~~~~~~~~~~~~~~~
ll ans = oo;
rep(i, vsz){ // max値(low)を全探
auto[high, low] = V[i];
chmin(ans, target - high);
chmax(target, low); // targetを変更。今検証した値が、既存のtargetを超える最小値に設定。
}
if (ans < X) ans = 0; // Xにゆとりがあれば絶対0にできる
cout << ans << endl;
}