AtCoder AGC 013 A - Sorted Arrays (茶色, 300 点)

個人的には超苦手系。。。
でもちゃんと Greedy 思考を整理すればできる。こういうのは Greedy 思考の「型」を理解することが大事そう。

問題へのリンク

問題概要

長さ の数列 が与えられる。 を何箇所かで切って、 の連続した部分であるようないくつかの数列に分ける。

このとき、各区間については「単調非減少」または「単調非増加」になっている必要がある。

最小で何個の区間に分ければ良いかを求めよ。

制約

• 

考えたこと

基本的には下図のようなことがしたい！！！

でも頭が混乱するケースとして、以下のようなケースがある！！！

30, 40, 50, 60, 55, 65, 75, 85

これは正解は

(30, 40, 50, 60) 
(55, 65, 75, 85)

なのだけども、一見こうしてもよさそうに思えてしまう

(30, 40, 50)
(60, 55)
(65, 75, 85)

つまり何が難しいかというと、今回の 60 とか 55 みたいに「極小」や「極大」になってるやつを、左右のどちらに振り分けるかによって、答えが変わってしまう場合がある！！！！！！！！！！！

しかしこれは、以下のように考えればよい:

• 左から順に見て行って、単調性が崩れないように区間を切り出していくことを考える
• このとき、例えば「極大」になっているやつは含めるか含めないか迷うけど、含めずに後に残すメリットはない！！！！！

後に残しても後が厳しくなるだけなのだ。さっきの事例も「左から見ていく」とルールを決めたのなら、

30, 40, 50

と入れたときに、60 も入れて限界まで入れて切っていれば、60 が後で悪さをすることがなかったのだ。

こういう風に、迷ったときは「左から見ていく」とルールを決めて、後に残すメリットがないという Greedy 性を見出せないかを考えるのがよさそう。

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

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

    int res = 0;
    for (int i = 0; i < N; ++i) {
        // same を抜ける
        while (i+1 < N && A[i] == A[i+1]) ++i;

        // up
        if (i+1 < N && A[i] < A[i+1]) {
            while (i+1 < N && A[i] <= A[i+1]) ++i;
        }
        // down
        else if (i+1 < N && A[i] > A[i+1]) {
            while (i+1 < N && A[i] >= A[i+1]) ++i;
        }
        ++res;
    }
    cout << res << endl;
}