ABC152

珍しく[B]までは詰まらず6分半で出せたんだけど，[C]を

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

int main(void){
  int N;
  cin >> N;
  vector<int> p(N);
  for(int i=0; i<N; i++){
    cin >> p.at(i);
  }

  int ans = 1;
  int threshold = N+1;
  for(int i = 1; i < N; i++){

    if(p.at(i) >= threshold){
      continue;
    }

    sort(p.begin(), p.begin()+i);

    if(p.at(0) >= p.at(i)){
      ans++;
      threshold = p.at(i)+1;
    }
  }

  cout << ans << endl;
}

とかソートを使って書いてて，TLEが消えなくて発狂していた． 一個ずつ考える要素を増やしていくんだから，最小値は一回ずつ更新していけばわかる．

mespace std;

int main(void){
  int N;
  cin >> N;
  vector<int> p(N);
  for(int i=0; i<N; i++){
    cin >> p.at(i);
  }

  int ans = 1;
  int threshold = N+1;
  for(int i = 1; i < N; i++){
    if(p.at(i) > threshold){
      continue;
    }else{
      ans++;
      threshold = p.at(i);
    }
  }

  cout << ans << endl;
}

で良いんだよな…（これは酷い）
結局[D]を書く時間がなくなってしまったけど，i=1,...,Nについてループを書いてiをi=i_1...i_tと表示したとして，i_tとi_1の間に数字を挟んでいくときに，Nと同じ桁まで来たら，どこまで大きくして良いかはループを書くしかない気がして，そうすると内側のループが最大O(10^4)になってTLEになってしまうのでは…？とか思っていた．

学んだこと

• char型をint型に変換する方法と注意【数値化 キャスト 文字列変換】：charをintに型キャストするときは'0'を引かないと駄目．
• 2016/6/21 【c++】vectorとsortの謎(一部の区間だけをソートしたい！)：部分ソートの書き方と仕様
• string->intはatoi(...)，int->stringはto_string(...)

追記

• 解説PDFの[B]言われてみれば確かにすぎる．[C]も賢いなあ…
• [D]は問題文を誤読していてA<=Bのときだけ考えようとしてたのでどのみち終わっていた．うーん駄目だなあ…