Official

B - Two Languages Editorial by MMNMM

ある単語 \(w\) が高橋語の単語である可能性があるということは、次の条件が成り立つということです。

  • \(w\) に含まれるすべての文字について、その文字は \(S\) に含まれている。

まずはこの条件を判定するプログラムを書くことを考えます。

高橋語の単語である可能性があるか判定するプログラムを書く

ある文字 \(c\) が \(S\) に含まれているかは、例えば for 文などを使って \(S\) の文字を一文字ずつ確認することで判定することができます。

C++, Python での実装例

bool included = false; // false にしておく
for (int i = 0; i < N; ++i) {
    if (S[i] == c) { // S の中に c があったら
        included = true; // 答えを true にする
    }
}

included = False # False にしておく
for s in S:
    if c == s: # S の中に c があったら
        included = True # 答えを True にする

いくつかのプログラミング言語には、文字列などにある文字が含まれているかを少ない記述量で判定できる機能があります。

C++, Python での実装例

ranges::contains(S, c); // S の中に c があったら true, なければ false

ranges::contains 関数を使うには、<algorithm> ヘッダをインクルードする必要があります。

c in S # S の中に c があったら True, なければ False

このような判定を \(w\) に含まれる各文字に対して行い、すべての文字が \(S\) に含まれるかを判定すればよいです。 この処理は、例えば for 文などを使って判定することができます。

C++, Python での実装例

bool all_in_S = true; // true にしておく
int L = w.size();
for (int i = 0; i < L; ++i) {
    if (!ranges::contains(S, w[i])) { // S に w[i] が含まれていなければ
        all_in_S = false; // 答えを false にする
    }
}

all_in_S = True # True にしておく
for c in w:
    if not c in S: # S に c が含まれていなければ
        all_in_S = False # 答えを False にする

いくつかのプログラミング言語には、すべての要素が条件を満たしているかを少ない記述量で判定できる機能があります。

C++, Python での実装例

ranges::all_of(w, [&S](char c) {
    return ranges::contains(S, c); // S の中に c があったら true, なければ false
}); // w の文字がすべて S に含まれていれば true, そうでなければ false

ranges::all_of 関数を使うには、<algorithm> ヘッダをインクルードする必要があります。

all(c in S for c in w) # w の文字がすべて S に含まれていれば True, そうでなければ False

青木語の単語である可能性があるかも同様のプログラムで確認することができます。

これらの判定プログラムを書くことができれば、入力で与えられるすべての単語に対して上記の判定を行い、それぞれの結果に応じて適切な出力ができればよいです。 例えば、次のような場合分けを行うことで正しい出力が得られます。

  • 高橋語の単語である可能性がなければ、青木語の単語
  • 青木語の単語である可能性がなければ、高橋語の単語
  • どちらの可能性もあれば、確定しない

判定部分の実装が長くなる場合は、その部分を関数として切り分けると見通しがよくなる場合があります。

実装例は以下のようになります。 判定の実装をネストされた for 文で行い関数に切り分けたものと、言語機能を使って判定を少ない記述量で行ったものの両方の実装例があります。

C++, Python での実装例①

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

int N;
string S;
bool is_takahashi_go_word(string w) { // 高橋語の単語である可能性があるか判定する関数
    bool is_takahashi_go = true;
    int L = w.size();
    for (int i = 0; i < L; ++i) { // w のそれぞれの文字について、
        // S に含まれているか判定する
        bool included = false;
        for (int j = 0; j < N; ++j) { // S のそれぞれの文字を見て、
            if (S[j] == w[i]) { // 文字が等しければ
                included = true; // 含まれている
            }
        }

        if (!included) { // 今見ている w の文字が S に含まれていなければ
            is_takahashi_go = false; // 高橋語の単語ではない
        }
    }
    return is_takahashi_go;
}

// 青木語についても同様
int M;
string T;
bool is_aoki_go_word(string w) {
    bool is_aoki_go = true;
    int L = w.size();
    for (int i = 0; i < L; ++i) {
        bool included = false;
        for (int j = 0; j < M; ++j) {
            if (T[j] == w[i]) {
                included = true;
            }
        }

        if (!included) {
            is_aoki_go = false;
        }
    }
    return is_aoki_go;
}

int main() {
    cin >> N >> M >> S >> T;

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        string w;
        cin >> w;

        bool is_takahashi_go = is_takahashi_go_word(w);
        bool is_aoki_go = is_aoki_go_word(w);

        if (!is_takahashi_go) { // 高橋語の単語である可能性がないなら
            cout << "Aoki" << endl; // 青木語の単語
        } else if (!is_aoki_go) { // 青木語の単語である可能性がないなら
            cout << "Takahashi" << endl; // 高橋語の単語
        } else { //どちらの可能性もあるなら
            cout << "Unknown" << endl; // 確定しない
        }
    }

    return 0;
}

N, M = map(int, input().split())
S = input()
T = input()

def is_takahashi_go_word(w): # 高橋語の単語である可能性があるか判定する関数
    is_takahashi_go = True
    for c in w: # w のそれぞれの文字について、
        # S に含まれているか判定する
        included = False
        for s in S: # S のそれぞれの文字を見て、
            if c == s: # 文字が等しければ
                included = True # 含まれている

        if not included: #今見ている w の文字が S に含まれていなければ
            is_takahashi_go = False # 高橋語の単語ではない
    return is_takahashi_go

# 青木語についても同様
def is_aoki_go_word(w):
    is_aoki_go = True
    for c in w:
        included = False
        for t in T:
            if c == t:
                included = True

        if not included:
            is_aoki_go = False
    return is_aoki_go

Q = int(input())

for i in range(Q):
    w = input()
    
    is_takahashi_go = is_takahashi_go_word(w)
    is_aoki_go = is_aoki_go_word(w)

    if not is_takahashi_go: # 高橋語の単語である可能性がないなら
        print('Aoki') # 青木語の単語
    elif not is_aoki_go: # 青木語の単語である可能性がないなら
        print('Takahashi') # 高橋語の単語
    else: # どちらの可能性もあるなら
        print('Unknown') # 確定しない

C++, Python での実装例②

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

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

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        string w;
        cin >> w;

        if (!ranges::all_of(w, [&S](char c) { return ranges::contains(S, c); })) { // 高橋語の単語である可能性がないなら
            cout << "Aoki" << endl; // 青木語の単語
        } else if (!ranges::all_of(w, [&T](char c) { return ranges::contains(T, c); })) { // 青木語の単語である可能性がないなら
            cout << "Takahashi" << endl; // 高橋語の単語
        } else { //どちらの可能性もあるなら
            cout << "Unknown" << endl; // 確定しない
        }
    }

    return 0;
}

N, M = map(int, input().split())
S = input()
T = input()

Q = int(input())

for i in range(Q):
    w = input()

    if not all(c in S for c in w): # 高橋語の単語である可能性がないなら
        print('Aoki') # 青木語の単語
    elif not all(c in T for c in w): # 青木語の単語である可能性がないなら
        print('Takahashi') # 高橋語の単語
    else: # どちらの可能性もあるなら
        print('Unknown') # 確定しない

posted:
last update: