AtCoder AGC 003 B - Simplified mahjong (水色, 400 点)

微妙なコーナーケースに注意

問題へのリンク

問題概要

の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか？

• ペアとなるカードの数値の差は 1 以下

制約

• 

考えたこと

一瞬、

• 値が等しいペアを作れるだけ作って
• 残った中で値が小さい方から順にペアリングしていく

という方法が最適解を導きそうな気がしてしまう。しかしこれは嘘で、以下のようなケースがある:

• 

この場合は、(1, 2) と (2, 3) の 2 ペア作れる。しかし (2, 2) をペアリングしてしまうと (1, 3) をペアにできないのだ。

正しくは

正しくは、数列 を「0」の部分で区切った区間ごとに考えたとき、

• 区間の総和が偶数なら余すことなく、ペアリングできる
• 区間の総和が奇数なら 1 枚だけ余して、ペアリングできる

ということがいえる (厳密な証明は数学的帰納法など)。逆にこれらが最適であることも明らか。

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

int main() {
    int N; cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    long long res = 0, sum = 0;
    for (int i = 0; i < N;) {
        int j = i;
        while (j < N && a[j]) sum += a[j++];
        res += sum / 2;
        sum = 0;
        i = j+1;
    }
    cout << res << endl;
}