Codeforces Round #527 Div.3 D1 / D2: Great Vova Wall

問題概要

原文 (D1) → Problem - D1 - Codeforces
原文 (D2) → Problem - D2 - Codeforces

長さ $N$ の数列が与えられる。以下の操作を繰り返し行うことによって、全要素の値を等しくしたい。

D1 で認められる操作
- 値が同じである隣り合う要素を選び、その両方に対し 1 加算
- ある要素を選び、それに対し 2 加算
D2 で認められる操作
- 値が同じである隣り合う要素を選び、その両方に対し 1 加算

解説

D1

単一要素に対して 2 加算できることから、値の偶奇が等しいものは値も等しいとみなしてよいです。つまり、与えられた数列を 0 と 1 のみからなる数列に直すことができます。

このように直した数列に対し、全要素の値を等しくできるかを考えましょう。これは stack を利用することで効率的に処理できます。括弧の対応を取るときと同じように、stack の top にある値と追加したい値が等しい場合は pop し、そうでなければ push することを繰り返し、最終的に得られた stack の size が 1 以下であれば条件を満たせます。

この正当性を簡単に述べます。まず 0 と 1 のみからなる数列に対して「単一要素に 2 加算」の操作は必要ありません。つまり「値が等しい隣り合う要素両方に 1 加算」のみを考えれば良いです。この操作を考える際、同じ parity を持つ区間の長さの偶奇*1が重要になります。この区間長が偶数である場合、うまく操作することで区間全体の parity を変えることもできますし、変えないこともできます。つまり、他の区間の状況に応じて parity を自由に変えることができるので、この区間は元からなかったかのように無視しても構いません。区間長が奇数である場合も、1 つを残して他は全て 0 または 1 に変更可能です。つまり、区間長 $\bmod 2$ を考えれば良いことになります。全体の偶奇を揃えることが目的なので、最終的に何も区間が残らないか、区間がただ 1 つ残る場合に元々の条件を満たせます。この操作は、上で書いたように stack に対する操作で簡潔に表現できます。

D2

D1 とは異なり、単一要素に対して 2 加算することが許されていません。つまり、D1 のように偶奇の戦略を使うことができなくなります。

しかし、この場合でも stack を使うことで効率的に処理できます。stack の top にある値と追加したい値が等しい場合は pop し、そうでない場合について top にある値未満である場合に push、そうでなければその時点で条件を満たしません。

top と値が等しい場合についての操作の正当性は先ほどと同様です。では top と値が異なる場合はなぜこれでうまく動くのでしょうか？

top にある値未満である場合
- stack に残っている要素は、括弧の対応で言うところの開き括弧の状態に対応します。stack に残っている要素を閉じる前に、それよりも小さい要素が来てしまったという状況です。この場合新たに追加した値を閉じることができれば、それに対して一様に加算することで元々 stack にあった要素も閉じられる可能性があります。よって stack に値を追加して操作を続ければ良いです。
top にある値を超える場合
- stack に残っている要素を閉じる前に、それよりも大きい要素が来てしまったという状況です。全要素の値を揃えるためには stack に残る要素に対して操作を行う必要があるのですが、閉じられていないため操作を行うことができません。よって、この時点で条件を満たせなくなります。

最終的に判定する際も若干の注意が必要です。数列に対して繰り返し操作をし終えた際に、各要素の値がいくつになっているか考えます。これは明らかに元の数列の最大値 $M$ になります。このことを考慮すると、最後に得られる stack の状態として許容されるものは、中身が空であるか、 $M$ だけが残っている状態のみです。

ソースコード

D1

signed main() {
    int N; scanf("%lld", &N);

    stack<int> st;
    for(int i=0; i<N; i++) {
        int val; scanf("%lld", &val);
        val %= 2;

        if(st.size()) {
            int t = st.top();
            if(t == val) st.pop();
            else st.push(val);
        }
        else st.push(val);
    }

    cout << (st.size() > 1 ? "NO" : "YES") << endl;
    return 0;
}

D2

signed main() {
    int N; scanf("%lld", &N);

    stack<int> st;
    int ma = -INF;
    for(int i=0; i<N; i++) {
        int val; scanf("%lld", &val);
        ma = max(ma, val);

        if(st.size() and st.top() == val) st.pop();
        else if(st.empty() or st.top() > val) st.push(val);
        else {
            puts("NO");
            return 0;
        }
    }

    bool ok = st.empty() or st.top() == ma;
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}