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

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

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

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

問題へのリンク

問題概要

 1, 2, \dots, N の書かれたカードがそれぞれ  a_{1}, \dots, a_{N} 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか?

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

制約

  •  1 \le N \le 10^{5}

考えたこと

一瞬、

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

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

  •  A = (1, 2, 1)

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

正しくは

正しくは、数列  A を「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;
}