EZ Programming Contest #1 - C. EZPC Sort

Tags:cpcodeforcesstringsort

問題

https://codeforces.com/gym/103150/problem/C

問題文

abcdefghijklmnopqrstuvwxyz を並び変えて得られた文字列 ss が与えられる。以下の操作を 0 回以上行い、部分列として ezpc を出現させられるか？

ss の部分文字列を選び、その部分文字列について文字を辞書順に並び替える。

制約

  • テストケース数: 1≤t≤50001 \le t \le 5000

サンプル

3
ezpcabdfghijklmnoqrstuvwxy
zaepbcdfghijklmnoqrstuvwxy
orzgvlkbenwyqjmdfsctxhiaup

YES
YES
NO

考察

以下の場合は、どう並び変えても ezpc は出現しない。

  • p が z より前にある
  • c が p より前にある
  • c が z より前にある
  • c が e より前にある

それぞれの index を求めて、上のケースに当てはまるか判定すれば OK。

コード

https://codeforces.com/gym/103150/submission/120703548

void solve() {
  string s;
  cin >> s;
  vector<int> idx(4, -1);
  rep(i, s.size()){
    switch (s[i]){
      case 'e':
        idx[0] = i; break;
      case 'z':
        idx[1] = i; break;
      case 'p':
        idx[2] = i; break;
      case 'c':
        idx[3] = i; break;
    }
  }
  if(idx[3] < idx[2] || idx[2] < idx[1] || idx[3] < idx[1] || idx[3] < idx[0]){
    cout << "NO" << endl;
  }
  else{
    cout << "YES" << endl;
  }
  return;
}