スキップ [技術室奥プログラミングコンテスト#4 Day1 D]

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_d

解説

https://atcoder.jp/contests/tkppc4-1/submissions/6637990

例を眺めると、a<b<cの場合はa,b,cと選んだ場合とa,cと選んだ場合は同じになる。 このように単調増加する場合は、中を削除することができる。
つまり、ジグザグになるように選んでいけばいい。
これをstackを使って実現する。
stackには常に2つ以上入っている状態を維持する。
stackにa,bと入っているとき、cがa<b<cならば、bをとって、a,cと入れ直す。
a＜b＞cならば、ジグザグなので、そのまま入れる。
こうして入れていくことで、stackの中身はジグザグになる。
最後にstackに入っている個数が答えになる。

後は、色々コーナーケースがあるので注意。
(1) 最終的に答えが1になる場合は、それをとっても取らなくても特典が0になるので、0を答える
(2) 最初の2つに同じ数が来た場合は適切に取り除かれないので、直前の数と同じであれば省くようにする

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    stack<int> st;
    rep(i, 0, N) {
        if (1 <= st.size() and st.top() == A[i]) continue;
 
        if (st.size() < 2) st.push(A[i]);
        else {
            int top = st.top(); st.pop();
            int second = st.top(); st.pop();
 
            if (second < top and top <= A[i]) {
                st.push(second);
                st.push(A[i]);
            }
            else if (second > top and top >= A[i]) {
                st.push(second);
                st.push(A[i]);
            }
            else {
                st.push(second);
                st.push(top);
                st.push(A[i]);
            }
        }
    }
    int ans = st.size();
    if (ans == 1) ans = 0;
    cout << ans << endl;
}