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

atcoder.jp

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

問題概要

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

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

制約

• は英小文字からなり、その長さは 以上 以下。
• は英大文字からなり、その長さは 。

考察

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

の末尾がXであるとき

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

の末尾がXでないとき

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

コード

#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;
        }
    }
}

atcoder.jp

実装時間: 15分

かなり冗長なコードになってしまったが、AC であれば正義。