ARC094 E Tozan and Gezan

問題文

https://beta.atcoder.jp/contests/arc094/tasks/arc094_c

 

はじめからAとBが等しいときは0が答えとなるので,そうでないときをかんがえる.

このとき,とざん君がA[i]>B[i]となるようなiを1つ選び,i番目以外の要素から1減らすことにすると,i番目以外の要素が全て0になるまでこの操作を続けられることがわかる(お互いに1減らすことしかできないのでげざん君がどう操作してもA[i]>B[i]のままだから).

このあと,とざん君はA[i]から1減らし続けるしかなく,やがてA[i]=B[i]となって終了する.

結局,高橋くんが食べる飴は(A[i]の合計)-(A[i]>B[i]を満たすiについてのB[i]のmin)個になる.

これが最適であることの証明はここにある.

知識は不要で,それぞれの立場での良さげな戦略をかんがえてみるとわかるという問題だった.

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
ll A[200000];
ll B[200000];
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    bool same = 1;
    ll sum = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) same = 0;
        sum += A[i];
    }
    if (same) {
        cout << 0 << endl;
        return 0;
    }
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] > B[i]) {
            ans = max(ans, sum - A[i] + (A[i] - B[i]));
        }
    }
    cout << ans << endl;
}