[ABC236] E - Average and Median
[Q] https://atcoder.jp/contests/abc236/tasks/abc236_e
0. 精度が10^-3までなので、Aを10000倍しちゃう。
1. 平均値をにぶたん。
2. DPなんだけど、
平均値=midを仮定したら、(A-mid)とみなして、maxだけ取得するDP。これが味噌。
DP[index] = その時点での最高スコアとして管理。
最終的にDP[N-1] >= 0 なら成立。
そうすれば、DPの要素に取得個数をもたなくて済む。
3. 中央値もにぶたん。
4. 取得個数が過半数なら、medianを満たす。
N=7
A[]=3 1 4 1 5 9 2
0. A[]を10000倍。
A[] = 30000 10000 40000 10000 50000 90000 20000
1. 平均値を求める
状態が2つ。自身をとる場合と取らない場合があるので、DP0とDP1を用意。
DP0[i] // A[i]をとらない場合。
DP1[i] // A[i]をとる場合。
DP0は、直前に取っている場合のみ採用されるので、DP0[i] = DP1[i-1]
DP1は、直前にかかわらず採用するのでDP1[i] = max(DP0[i-1] + A[i], DP1[i-1] + A[i])
mid = 52500 のとき、
DP0[] = 0 -22500 -42500 -35000 -77500 -37500 0
DP1[] = -22500 -42500 -35000 -77500 -37500 0 -32500
score = max(DP0[N-1], DP1[N-1]) = 0 // 0以上なので成立
avg = mid/10000 = 5.2500000000
3. 中央値を求める
こっちのほうが簡単。採用する条件は2つ。
・mid以上なら採用
・mid以下だけど、直前に取っていないなら採用
mid = 40000 のとき、
3 1 4 1 5 9 2
~ ~ ~ ~
3,4,5,9 (*10000)が採用されて、
median = 40000/10000 = 4実装
ll N;
ll A[100010];
ld solve_avg() {
/*
にぶたん。mid = 解答平均値。
A[] - midで、maxだけ取得するDP。
最終値が0以上なら成立
*/
ll high = 1e13 + 100;
ll low = -1;
ll DP0[N]{}; // とらない
ll DP1[N]{}; // とる
while (high - low > 1) {
rep(i, N) {
DP0[i] = -oo;
DP1[i] = -oo;
}
ll mid = (high + low) / 2;
rep(i, N) { // 自分から、2個前と1個前からもらう感じ
ll a = A[i] - mid;
if (i == 0) {
chmax(DP1[i], a);
chmax(DP0[i], 0);
} else {
chmax(DP1[i], DP0[i - 1] + a);
chmax(DP1[i], DP1[i - 1] + a);
chmax(DP0[i], DP1[i - 1]);
}
}
ll mx = max(DP1[N - 1], DP0[N - 1]);
if (mx >= 0) { // lowは満たす。
low = mid;
} else
high = mid;
}
return (ld)low / 10000;
}
ll solve_med() {
/*
にぶたん
メジアン以上の個数が、過半数を超えていればいい
*/
ll high = 1e13 + 100;
ll low = -1;
bool used[N]{};
while (high - low > 1) {
rep(i, N) used[i] = false;
ll cnt0 = 0;
ll cnt1 = 0;
ll mid = (high + low) / 2;
rep(i, N) {
if (A[i] >= mid) {
used[i] = true;
++cnt1;
} else if (i > 0 && used[i - 1] == false) {
used[i] = true;
++cnt0;
}
}
if (cnt1 > cnt0)
low = mid; // 成立
else
high = mid;
}
return low / 10000;
}
int main() {
cincout();
cin >> N;
rep(i, N) {
cin >> A[i];
A[i] *= 10000; // 誤差補正
}
ld avg = solve_avg();
ll med = solve_med();
cout << avg << endl << med << endl;
}