AGC013Aを解いた

A: Sorted Arrays - AtCoder Grand Contest 013 | AtCoder

AGC013Aを解きました

最初に思いついたWAな解法

1. 配列BにB[i] に A[i] - A[i-1] (2 <= i < N) を代入する。 このときB[i] = 0ならB[i]にB[i-1]を代入する。
2. 以降は以下の擬似コードのとおりにやる

  int ans = 1;
  for(int i = 2; i < N;){
    if(B[i]とB[i+1]の符号が異なる){
      iを2増やす;
      ansを1増やす;
    }
    //B[i]とB[i+1]の符号が同じ場合
    else{
      iを1増やす;
    }
  }
  ansを出力

この方法だと何故か2/14がWAになってしまい2~3時間くらい考えても原因はわかりませんでしたorz 解説を見てもなにがおかしいのかはわかりませんでした><

そこで以下のようにやり方を変えました

ACした解法

以下の擬似コードの通りにしました。

int flag = 0;
int ans = 0;
for(int i = 1; i < N; i++){
  if(flagが0){
    A[i+1] - A[i]が正ならflagに1を負ならflagに-1を0なら0を代入;
  }else{
    if(A[i+1] - A[i]とflagの正負が異なる場合){
      ansを1増やす;
      flagを0にする;
    }
  }
  
}
ansを出力

なぜかこの方法だとACしました。 ですが最初の方法でなぜWAになってしまったのか今でもわかりません><

今回は途中で大幅に方針を変更した結果うまくいきました。 WAの数が少なくても一からやりなおしたほうがいい場合もあるということですかね。