整理するのがちょっと大変系。でもとても教育的だと思う！

問題概要

$N$ 次元の整数ベクトル ( $h_1, h_2, \dots, h_N$ ) が与えられる。これを以下のようなベクトルの和として表したい。

( $0, 0, 0, 1, 1, 0$ ) のように「 $1$ 」が連続していてそれ以外は $0$ になっているベクトル

例えば、(1, 3, 3, 2, 3, 3, 2) であれば

(1, 3, 3, 2, 3, 3, 2) 
=
(1, 1, 1, 1, 1, 1, 1) +
(0, 1, 1, 1, 1, 1, 1) +
(0, 1, 1, 0, 0, 0, 0) +
(0, 0, 0, 0, 1, 1, 0)

のように最小で 4 本のベクトルの和で表せる。最小本数のベクトルを求めよ。

制約

$1 \le N \le 100$

考えたこと

例えば $h = (1, 2, 4, 6, 6, 3, 2, 3, 4, 3)$ だと、こんな感じになる。

これを、下図みたいに、それぞれの高さごとに集計する感じ。

例えば高さ 3 の部分を取り出すとこうなっている。

こういうのを区間ごとに切り出す処理は典型的だけど、慣れないと難しい。この種の処理の書き方は、もう毎回決まった書き方を自分なりにテンプレ化してしまうとよい気がする。

0, 0, 1, 1, 1, 1, 0, 1, 1, 1

みたいなやつで「1 が連続するところ」が何箇所あるかを数える場面を想定して、一つの書き方として

        // 区間分割する
        int i = 0;
        while (i < N) {
            if (h[i] == 0) ++i; // 0 なら何もせずに次に進む
            else {
                ++res; // 区間の始まり
                while (i < N && h[i] > 0) {
                    ++i; // 区間の終わりまで一気に
                }
            }
        }

というのがあると思う。今回もこれを利用してやってみる。

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

int main() {
    int N; cin >> N;
    vector<int> h(N);
    for (int i = 0; i < N; ++i) cin >> h[i];

    // 高さが全部 0 になるまでやる
    int res = 0;
    while (true) {
        // 最高高さが 0 だったらおしまい
        if (*max_element(h.begin(), h.end()) == 0) break;
        
        // 区間分割する
        int i = 0;
        while (i < N) {
            if (h[i] == 0) ++i; // 0 なら何もせずに次に進む
            else {
                ++res; // 区間の始まり
                while (i < N && h[i] > 0) {
                    --h[i]; // ついでに引いとく
                    ++i; // 区間の終わりまで一気に
                }
            }
        }
    }
    cout << res << endl;
}

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

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

AtCoder ABC 116 C - Grand Garden (茶色, 300 点)

問題概要

制約

考えたこと