これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って...

問題概要

長さ $N$ の数列 $a_{1}, \dots, a_{N}$ が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。

数列の任意の区間を選んで、その区間内の値をすべてその区間内の値の平均値で置き換える

制約

$1 \le N \le 10^{6}$

考えたこと

まず、操作する区間は disjoint であるとしてよい。大前提として、最適解は単調増加になっていると思ってよくて (そうでないなら明らかに辞書順を改善できる)、重なっている状態で最適解が得られているなら重なりをほどいて解が悪化することはありえない。よってこの時点で、 $O(N^{2})$ にはなる (毎回、残りの部分について、左から Greedy に最小となる区間を切り出していく)。

ここから高速化。

stack

元々区間に対する操作と stack は相性がいい。今回の問題は特に、ちょっとぷよぷよに似てる。

2 つの要素 a, b があって、a > b な関係だったら、パーンと 1 つの要素にしちゃった方がいい

みたいなことを延々と繰り返すイメージ。なんかぷよぷよっぽい。こういうぷよぷよっぽい挙動は stack を用いて線形時間でシミュレートできるのだ。本質的には「カッコ列を判定する stack の使い方」と一緒。

#include <bits/stdc++.h>
using namespace std;

using pll = pair<long long, long long>; // sum, num
int main() {
    int N;
    scanf("%d", &N);
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) scanf("%lld", &a[i]);

    vector<pll> st;
    for (int i = 0; i < N; ++i) {
        long long sum = a[i], num = 1;
        while (!st.empty() &&
               st.back().first * num >= sum * st.back().second) {
            sum += st.back().first;
            num += st.back().second;
            st.pop_back();
        }
        st.emplace_back(sum, num);
    }
    for (int i = 0; i < st.size(); ++i) {
        double res = (double)st[i].first / st[i].second;
        for (int j = 0; j < st[i].second; ++j) printf("%.10f\n", res);
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #618 (Div. 1) C. Water Balance (R2100)

問題概要

制約

考えたこと

stack