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

半分エスパー

問題へのリンク

問題概要

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

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

制約

• 

考えたこと

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

• 黒の個数
• 白の個数

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

#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);
}