ARC138 - C : Rotate and Play Game

問題

atcoder.jp

解法

大きい方からN/2個がどんな並びでも取れそうと思い、その証明を得た。
やってること自体は本解説と同じな気がするが、こっちの方が断然わかりやすいはず。

次の図が全てである。

値を取らない場合 x方向+1, 取る場合 y方向+1

値を取る場合は y方向に1歩進み、取らない場合はx方向に1歩進む。 x = p に初めて到達した時に y の値が p より大きいと、「大きい方からN/2個取る」のに失敗する。

cyclic shift をするのは、このグラフでいうスタート地点を変更することに対応するので、
青点のように、y = x から最も離れた点 (すなわち、y - x が最も大きい点) から始めれば、
x = p に初めて到達した時の y の値は p 以下となる。

つまり、大きい方から N/2 個取ることに成功する。

int main(){
    int n; cin >> n;
    V<ll> a(n);
    rep(i,n) cin >> a[i];
    V<int> use(n);
    priority_queue<pair<int, int>, V<pair<int, int>>, greater<>> que;
    rep(i,n/2) que.emplace(a[i], i);
    for(int i = n/2; i < n; i++){
        if(que.top().fi < a[i]){
            que.pop();
            que.emplace(a[i], i);
        }
    }
    ll sum = 0;
    while(sz(que)){
        sum += que.top().fi;
        use[que.top().se] = 1;
        que.pop();
    }
    int idx = -1, dif = 0, cur = 0;
    for(int i = 0; i < n; i++){
        if(use[i]) cur++;
        else cur--;
        if(chmax(dif, cur)) idx = i;
    }
    cout << idx << " " << sum << endl;
}