Codeforces Round #225 (Div. 2) C. Milking cows

解いてる時はなんとなく提出したら正解だった, という感じでした。

問題

codeforces.com

解法

右に向いてるやつを左から順番に取っていき, その後に左に向いてるやつを右から順番に取っていく, というのが最適な milking の一つです(左に向いてるやつを右から順番に取って, その後右に向いてるやつを左から順番に…でも良い)。

なんでこれが最適かは解いてる時ははっきり証明できなかったので, 解説を見ました。

i < j を満たす異なる２つの整数の組 (i, j) を考えます。このとき,

• a[i] = 0, a[j] = 0 のとき… 明らかに j -> i と取るのが最適
• a[i] = 0, a[j] = 1 のとき… i, j のどちらを先にとっても同じ
• a[i] = 1, a[j] = 0 のとき… i, j のどちらを先にとっても同じ
• a[i] = 1, a[j] = 0 のとき… i -> j と取るのが最適

となっています。で, i < j かつ上で「最適」と言っている順に milking をすることは出来る(上で書いたような手順でやれば良い)ので上の方法が最適です。

const int MAXN = 200200;
int cnt[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cnt[i+1] = cnt[i] + a[i];
    ll tmp = 0;
    for (int i = 0; i < n; i++) if (a[i] == 0) tmp += cnt[i];
    cout << tmp << endl;
    return 0;
}