B - Two Languages 解説 by en_translator
A word \(w\) can be in Takahashi-go if and only if:
- All characters in \(w\) are contained in \(S\).
First, let us write code that solves this decision problem.
Writing a program that determines if a given word can be in Takahashi-go
One can determine if character \(c\) is contained in \(S\) by, for example, inspecting the characters of \(S\) one by one using a for statement.
Sample code in C++ and Python
bool included = false; // Initialize with false
for (int i = 0; i < N; ++i) {
if (S[i] == c) { // If c is found in S
included = true; // Set the answer to true
}
}
included = False # Initialize with False
for s in S:
if c == s: # If c is found in S
included = True # Set the answer to True
Some programming languages have features that enables us to check if a character is contained in a string more concisely:
Sample code in C++ and Python
ranges::contains(S, c); // true if S contains c, and false otherwise
To use ranges::contains, one must include the <algorithm> header.
c in S # True if c is contained in C, and False otherwise
Apply this check against each character contained in \(w\) to check if all characters are contained in \(S\).
This process can be implemented with, for example, a for statement.
Sample code in C++ and Python
bool all_in_S = true; // Initialize with true
int L = w.size();
for (int i = 0; i < L; ++i) {
if (!ranges::contains(S, w[i])) { // If S does not contain w[i]
all_in_S = false; // Set it to false
}
}
all_in_S = True # Initialize with True
for c in w:
if not c in S: # If c is not contained in S
all_in_S = False # Set it to False
Some programming languages have features that helps us to check if all elements satisfy a specific condition more concisely:
Sample code in C++ and Python
ranges::all_of(w, [&S](char c) {
return ranges::contains(S, c); // true if S contains c, and False otherwise
}); // true if all characters in w are contained in S, and false otherwise
To use ranges::all_of, one must include the <algorithm> header.
all(c in S for c in w) # True if all characters in w is contained in S, and False otherwise
One can determine if a word can be in Aoki-go in the same way.
Once you write this logic, all that left is to apply it to every given word, and report the classification according to the results. For example, the following steps yield a correct classification:
- If it is not possible that the word is in Takahashi-go, classify it as an Aoki-go word.
- If it is not possible that the word is in Aoki-go, classify it as an Takahashi-go word.
- If both are possible, then the results are undecidable
If the logic for checking the condition requires long implementation, extracting it as a function may helps the code to be clear.
The following is sample code.
The former sample implements the checking logic with a for statement and extracts it as a function; the latter utilizes language features to reduce the implementation complexity.
Sample code in C++ and Python (1)
#include <iostream>
#include <string>
using namespace std;
int N;
string S;
bool is_takahashi_go_word(string w) { // Function that determines if the given word can be in Takahashi-go
bool is_takahashi_go = true;
int L = w.size();
for (int i = 0; i < L; ++i) { // For each character in w,
// determine if it is contained in S.
bool included = false;
for (int j = 0; j < N; ++j) { // Inspect each character of S.
if (S[j] == w[i]) { // If the characters match,
included = true; // then it is contained.
}
}
if (!included) { // If the character in w currently inspected is contained in S,
is_takahashi_go = false; // then it is not a Takahashi-go word
}
}
return is_takahashi_go;
}
// Same goes for Aoki-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) { // If it is not possible that it is a Takahashi-go word,
cout << "Aoki" << endl; // then it is an Aoki-go word
} else if (!is_aoki_go) { // If it is not possible that it is an Aoki-go word,
cout << "Takahashi" << endl; // then it is a Takahashi-go word.
} else { // If both are possible,
cout << "Unknown" << endl; // then it is undecidable.
}
}
return 0;
}
N, M = map(int, input().split())
S = input()
T = input()
def is_takahashi_go_word(w): # Function that determines if the given word can be in Takahashi-go
is_takahashi_go = True
for c in w: # For each character in w,
# determine if it is contais in S.
included = False
for s in S: # Inspect each character of S.
if c == s: # If the characters match,
included = True # then it is contained.
if not included: # If the character in w currently inspected is contained S,
is_takahashi_go = False # then it is not a Takahashi-go word
return is_takahashi_go
# Same goes for Aoki-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: # If it is not possible that it is a Takahashi-go word,
print('Aoki') # then it is an Aoki-go word
elif not is_aoki_go: # If it is not possible that it is an Aoki-go word,
print('Takahashi') # then it is a Takahashi-go word.
else: # If both are possible,
print('Unknown') # then it is undecidable.
Sample code in C++ and Python (2)
#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); })) { // If it is not possible that it is a Takahashi-go word,
cout << "Aoki" << endl; // then it is an Aoki-go word.
} else if (!ranges::all_of(w, [&T](char c) { return ranges::contains(T, c); })) { // If it is not possible that it is an Aoki-go word,
cout << "Takahashi" << endl; // then it is a Takahashi-go word.
} else { // If both are possible,
cout << "Unknown" << endl; // the result is undecidable.
}
}
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): # If it is not possible that it is a Takahashi-go word,
print('Aoki') # then it is an Aoki-go word.
elif not all(c in T for c in w): # If it is not possible that it is an Aoki-go word,
print('Takahashi') # then it is a Takahashi-go word.
else: # If both are possible,
print('Unknown') # the result is undecidable.
投稿日時:
最終更新: