EZ Programming Contest #1 - C. EZPC Sort


Tags:cpcodeforcesstringsort

問題

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

問題文

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

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

制約

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

サンプル

3
ezpcabdfghijklmnoqrstuvwxy
zaepbcdfghijklmnoqrstuvwxy
orzgvlkbenwyqjmdfsctxhiaup
YES
YES
NO

考察

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

  • pz より前にある
  • cp より前にある
  • cz より前にある
  • ce より前にある

それぞれの 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;
}