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

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

Codeforces Round #609 (Div. 1) B. Domino for Young (R2000)

半分エスパー

問題へのリンク

問題概要

 i 列目の高さが  a_{i} であるようなヤング図形が与えられる。

f:id:drken1215:20200119144557p:plain

これを 1 × 2 のドミノを重ならないように敷き詰めたい。最大で何個置けるか?

制約

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

考えたこと

ドミノ敷き詰め系の問題は、市松模様に塗るのが基本ではある。そして、

  • 黒の個数
  • 白の個数

のうちの小さい方が答えではないかと。それで正解だった。

f:id:drken1215:20200119144845p:plain

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<long long> a;
 
long long solve() {
    long long b = 0, w = 0;
    for (int i = 0; i < N; ++i) {
        if (i % 2 == 0) b += a[i]/2, w += (a[i]+1)/2;
        else b += (a[i]+1)/2, w += a[i]/2;
    }
    return min(b, w);
}
 
int main() {
    scanf("%d", &N);
    a.resize(N);
    for (int i = 0; i < N; ++i) scanf("%lld", &a[i]);
    auto res = solve();
    printf("%lld\n", res);
}