けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2727 M and A (JAG 模擬地区 2015 A) (200 点)

これ、問題文を一目見て簡単な問題だと気づけるようになるには、それ自体のトレーニングが必要そうなん

問題へのリンク

問題概要

文字列 S, T が与えられる。

  • S のうち偶数番目だけを抜き出してできる文字列を S1
  • S のうち奇数番目だけを抜き出してできる文字列を S2

とする。S1 と S2 のうちの少なくとも一方について、T の部分文字列 (連続していなくてよい) になっているかどうかを判定せよ。

考えたこと

Greedy にマッチングさせていけばよい

#include <iostream>
#include <string>
using namespace std;

bool check(string T, string sub) {
    int it = 0;
    for (int i = 0; i < T.size(); ++i) {
        if (T[i] == sub[it]) ++it;
        if (it == sub.size()) break;
    }
    return (it == sub.size());
}

int main() {
    string S, T; cin >> S >> T;
    bool ok = false;
    for (int start = 0; start < 2; ++start) {
        string sub = "";
        for (int cur = start; cur < S.size(); cur += 2) sub += S[cur];
        if (check(T, sub)) ok = true;
    }
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}