【AtCorder】A - Sorted Arrays

会社の同僚の影響で夏頃からAtCorder初めたんだが一向に成長する気配がないから少しでも学習の質を上げるべくちょこちょこ記事にしていこうと思う。

ちなみに今は灰色コーダー、悲しすぎる。

atcoder.jp

左からずらっと舐めてその時点でのポジションの値 v.at(i) >= v.at(i+1) or v.at(i) <= v.at(i+1) つまり単調増加or単調減少していればそのままポジションを移動するということを繰り返すというもの。

提出して通したコードは以下なのだが解いているときに貪欲法であることを意識できていないことがよくわかるコードである。。。 ロジックは

• その時点でのポジションが単調増加/減少どちらかを記憶
• 次のポジションを見たときに傾向が変わる場合にカウントアップ
• カウントアップ直後は無条件で次のポジションへ移動する
• v.at(i) == v.at(i+1) なら何もしない

というもの。

このレベルの問題ならパターンマッチしてコーディングしたいし、そのことが伝わるようなコードになっていないと先の成長はないなと思った。以上。

int main() {
  ll n;
  cin >> n;
  vector<ll> v(n);
  ll count = 1;
  bool desc = false;
  bool refreshed = true;
  
  for(ll i=0; i<n; i++) cin >> v.at(i);
  
  for(ll i=0; i<n-1; i++){
    if (v.at(i) == v.at(i+1)) continue;

    if (refreshed) {
      refreshed = false;
      desc =  v.at(i) < v.at(i+1);
      continue;
    }

    if ( desc != (v.at(i) < v.at(i+1)) ) {
      refreshed = true;
      desc = v.at(i) < v.at(i+1);
      count++;
    }
    
  }
  cout << count;
  
}

本日の気づき

ポジションを進めるためにfor文の中で i++ するのスマートだなと思った。

for (int i = 0; i < N; ++i) {
    while (i+1 < N && A[i] == A[i+1]) ++i;
}