Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC003-B 「Simplified mahjong」(400)

問題リンク

概要

 1 \sim Nまで書かれたカードがあり、 iのカードは A_i枚ある。

差の絶対値が1以下のカード2枚でペアを作っていくとき、ペアの数の最大値を求めよ。

制約

  •  1 \leq N \leq 10^5
  •  0 \leq A_i \leq 10^9

解説

結論を言ってしまうと、 iが小さい方から以下のように貪欲にペアを作っていくのが最善策となる。

  •  iのカード2枚からなるペアをできるだけ作る。
  •  i i + 1のカードのペアが作れるようなら作る。

なんで最適か証明しろって言われると難しい。editorialでは以下のように証明している。

 A_i = 0なる iが存在しない場合、 A_iの合計を Sとするとペア数の最大値は高々 \lceil S/2 \rceilとなる。そしてこの最大値は上の操作を適用することで達成可能である。

 A_i = 0なる iが存在する場合も、その iで分断すれば上のケースに帰着できる。よって上の操作が最適であることが示された。

上のような証明をしてから提出するのが理想だが、今回の場合は直感的に最適と感じやすいのでまぁそこまでしなくてもいいだろう。

実装例

場合分けを減らすため、「 N + 1のカードが0枚ある」としている。

int型では制約上答えがオーバーフローするので注意。

#include <iostream>
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;

    ll A[N + 1];
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    // N+1は0枚あるとすると実装しやすい
    A[N] = 0;

    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        // i同士のペアを作れるだけ作る
        ans += A[i] / 2;
        A[i] %= 2;

        // iとi+1のペアを作れれば作る
        if (A[i] > 0 && A[i + 1] > 0) {
            ++ans;
            --A[i];
            --A[i + 1];
        }
    }

    cout << ans << endl;
    return 0;
}

上のコードでは、最終的な Aは実際に操作を行ったあとの各カードの枚数と一致する。

感想

  • 証明しにくい貪欲はやはり不安になる。