CodeForces Round 609 Div2 D(Div1 B) - Domino for Young

問題文

https://codeforces.com/problemset/problem/1268/B
$n$ 列からなる高さがそれぞれ $a_i$ のヒストグラムがある。
$a_1 \geq a_2 \geq ... \geq a_n$ であり、広義単調減少になっている。
このようなヒストグラムから、 $1 \times 2$ であるか $2 \times 1$ であるような長方形を何個作ることが出来るかという問題。

制約

$1 \leq n \leq 300000$
$1 \leq a_i \leq 300000, a_i \geq a_{i+1}$

解法

ヒストグラムを市松模様に塗った時の色を例えば B と W とする。
答えは min( B の数, W の数) となる。
列ごとに B の数と W の数は $O(1)$ で求まるので、この問題は $O(n)$ で解ける。

なぜ

まず、連続する2マスの色のペアは、必ず B と W である。
つまり B と W の数より多く長方形を取れないので、答え $ans$ は
$ans \leq min( B の数, W の数)$
であることが示される。

では、 $ans = min( B の数, W の数)$ であることはどう示せばいいのだろうか。

このような形のヒストグラムを考えてみる。

B

WBW

BWB

WBW

BWBWBW

WBWBWBW

BWBWBWB

WBWBWBWBW

BWBWBWBWBW

WBWBWBWBWB

BWBWBWBWBWB

WBWBWBWBWBWBW

BWBWBWBWBWBWBW

このヒストグラムで高さが連続に2つ揃っているところをまず埋めてしまうとする。
埋めるには高さ $1$ 幅 $2$ の長方形を縦に並べればよい。
埋めた所を E と置いてみる。

B

WEE

BEE

WEE

BEEEEW

WEEEEBW

BEEEEWB

WEEEEBWEE

BEEEEWBEEW

WEEEEBWEEB

BEEEEWBEEWB

WEEEEBWEEBWEE

BEEEEWBEEWBEEW

このような部分を埋めても、埋めていない部分のBの数とWの数の差は変わらないことがわかる。

次は埋めたところを削除する。

B

W

B

W

BW

WBW

BWB

WBW

BWBW

WBWB

BWBWB

WBWBW

BWBWBW

このように削除すると、市松模様を保っていることがわかる。

実はこれを新たな小さいヒストグラムと考えて同じ問題を解いても良い。
削除した列があるため、実際にはWBなどの部分がWEEEEBのようになっているかもしれない。
この場合、WBで長方形は作れないが、これはつじつま合わせすることが出来る。
削除した4列をずらしてEEEEWBにすることが可能であるため、このWBを連続しているとみなしても良い。
こうすることで小さな問題にすることが出来る。

次は幅が2行揃っているところを削除する。

E

E

E

E

BW

EEE

EEE

WBW

EEEE

EEEE

EEEEE

EEEEE

BWBWBW

↓

BW

WBW

BWBWBW

行に対する処理を行っても、Bの数とWの数の差は変わらない。
これも小さなヒストグラムを埋める問題と考えて良くて、理由は先ほどの横消しの説明を縦消しに置き換えると良い。

次は揃っている列を削除する。

EE

EEW

EEBWEE

↓

W

BW

この処理を繰り返すと、最終的にヒストグラムは、階段状になる。
今回の例では2段になったが、多段に及ぶこともある。

つまり

B

WB

BWB

WBWB

BWBWB

WBWBWB

BWBWBWB

のような形となる。

この時、元のヒストグラムとBの数とWの数の差が変わっていないため、この階段上のヒストグラムにおいて、min(Bの数, Wの数)だけ長方形を取ることが出来たならば、元のヒストグラムについても証明できる。

上の図であれば、Wの数がBの数より少ない。
この図で長方形を作る時、必ずWは含ませられる。
高さ $1$ 幅 $2$ の長方形を左から敷き詰めてみる。
すると、

B

EE

EEB

EEEE

EEEEB

EEEEEE

EEEEEEB

というようになり、Bだけ残ることがわかる。
確かにWは全てEで置き換えられた。

列数が奇数である行は一番右を取ることは出来ないが、一番右はBであるので、Wは全て取れたことになる。
このようにして、階段状のヒストグラムでmin(Bの数, Wの数)だけ長方形を取ることが出来たため、
元のヒストグラムの長方形もmin(Bの数, Wの数)だけ取ることが出来ることがわかった。
おわりです

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    long long b = 0, w = 0;
    for (int i = 0; i < N; i++) {
        long long A;
        cin >> A;
        if (i & 1) b += A / 2, w += (A + 1) / 2;
        else b += (A + 1) / 2, w += A / 2;
    }
    cout << min(b, w) << endl;
    return (0);
}