問題
問題文
長さ $N$ の配列 $A$ が与えられます。$A$ を何箇所かで切って、$A$ の連続した部分であるようないくつかの数列に分けます。この時、分けられたあとの数列は全て、単調非減少または単調非増加な列になっている必要があります。最小で何個の数列に分ければ良いかを求めて下さい。
制約
・$1 \le N \le 10^5$
・$1 \le A_i \le 10^9$
・$A_i$ は全て整数である
収録されている問題セット
回答
回答1 (AC)
まず、単調非減少とは、値が増加することがないと言うことで、同じ値が続くことは許容しています。また、単調非増加とは、値が減少することがないと言うことで、やはり同じ値が続くことは許容しています。
設問では、もとの数列を切って単調非減少または単調非増加な数列を作っていくのですが、切り分ける回数を最小にしたいわけです。そこで、もとの数列を左から順番に見ていき、単調非減少または単調非増加が途切れたところで数列を切っていけばよいでしょう。
もとの数列では同じ値が続くことがあり得ますが、同じ値は数列を切り分ける回数に影響しないので、考えやすいように、コードでは無視して考える(同じ値は連続して書き込まない)ことにします。このとき、数列の最初の2項を見れば、最初の部分が単調増加か単調減少かを判定できるので、その状況が続くまでインデックスを増加させ、続かなくなったところで数列を切れば良いでしょう。コードは以下のようになりました。
agc013a-1.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int prev = 0, curr;
vector<int> a;
for ( int i=0; i<n; i++ ) {
cin >> curr;
if ( prev!=curr ) {
a.push_back(curr);
}
prev = curr;
}
int cut = 0, index = 0;
while ( index<(int)a.size()-1 ) {
int coef = 1;
if ( a.at(index)>a.at(index+1) ) {
coef = -1;
}
while ( index<(int)a.size()-1 && coef*a.at(index)<coef*a.at(index+1) ) {
index += 1;
}
if ( index<(int)a.size()-1 ) {
cut += 1;
}
index += 1;
}
cout << cut+1 << endl;
}
個人的にはコードが整理し切れていない気がしているのですが、現時点では改良法が思いつかないので、あきらめることにしました。良いアイディアが浮かべば、後日、加筆するかも知れません。
調べたこと
AtCoder の解説 公式解説
回答1と同じ方針でした。左から増加列・減少列を最大限に選択していけば良いことの証明が紹介されていました。