【AtCoder】ABC 349 C - Airport Code | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 219

問題概要

英小文字からなる文字列 $S$ から、英小文字からなる長さ3の文字列 $T$ を次の2つのうちいずれかの方法で得られるとき、 $T$ は $S$ の「空港コード」であるとする。与えられた文字列 $S, T$ に対して、 $T$ が $S$ の空港コードであるかを判定せよ。

方法1 : $S$ の長さ3の部分列をとり、それを英大文字に変換したものを $T$ とする。
方法2 : $S$ の長さ2の部分列をとり、それを英大文字に変換したものの末尾にXを追加したものを $T$ とする。

制約

$S$ は英小文字からなり、その長さは $3$ 以上 $10 ^5$ 以下。
$T$ は英大文字からなり、その長さは $3$ 。

考察

基本的には $T$ の生成方法を逆にたどり、条件に合うかを確認していけばよい。 $T$ の末尾がXであるかそうでないかで処理が若干異なるので、場合分けを行う。

$T$ の末尾が`X`であるとき

c1を $T$ の1文字目を小文字化したもの、c2を $T$ の2文字目を小文字化したものとして、c1, c2がこの順に $S$ に含まれているかをチェックすればよい。 $S$ の長さは最大でも $10^5$ なので、愚直にループを回していくだけで解決できる。

$T$ の末尾が`X`でないとき

c1を $T$ の1文字目を小文字化したもの、c2を $T$ の2文字目を小文字化したもの、c3を $T$ の3文字目を小文字化したものとして、c1, c2, c3がこの順に $S$ に含まれているかをチェックすればよい。処理は前項とほぼ同じ。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    string S, T;
    cin >> S >> T;

    if (T[2] == 'X')
    {
        char c1 = tolower(T[0]);
        char c2 = tolower(T[1]);

        bool flag = false;
        int idx1 = 0;
        rep(i, 0, S.size()) if (S[i] == c1)
        {
            flag = true;
            idx1 = i;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }

        flag = false;
        rep(i, idx1 + 1, S.size()) if (S[i] == c2)
        {
            flag = true;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }
        else
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    else
    {
        char c1 = tolower(T[0]);
        char c2 = tolower(T[1]);
        char c3 = tolower(T[2]);

        bool flag = false;
        int idx1 = 0, idx2 = 0;
        rep(i, 0, S.size()) if (S[i] == c1)
        {
            flag = true;
            idx1 = i;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }

        flag = false;
        rep(i, idx1 + 1, S.size()) if (S[i] == c2)
        {
            flag = true;
            idx2 = i;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }

        flag = false;
        rep(i, idx2 + 1, S.size()) if (S[i] == c3)
        {
            flag = true;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }
        else
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
}