【AtCoder】ABC 441 B - Two Languages

2026-01-22

AtCoder/ABC/B問題 AtCoder/ABC/200点問題 AtCoder/灰Diff AtCoder/NoviSteps/6Q AtCoder/アルゴリズムの基礎/条件分岐 AtCoder/データ構造/map 競技プログラミング

B - Two Languages

B - Two Languages

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 70 / NoviSteps: 6Q / 配点: 200 点

問題概要

AtCoder 国の公用語は、高橋語と青木語の $2$ つの言語である。高橋語では長さ $N$ の文字列 $S$ に含まれる英小文字のみを使い、青木語では長さ $M$ の文字列 $T$ に含まれる英小文字のみを使う。

AtCoder 国の公用語に含まれる $Q$ 個の単語 $w_1, w_2, \cdots, w_Q$ が与えられるので、それぞれの単語について次のうちどれに該当するか判定せよ。

高橋語の単語であることが確定する
青木語の単語であることが確定する
どちらともいえない

制約

$1\le N, M \le 26$
$S$ は英小文字からなる長さ $N$ の文字列
$S, T$ に含まれる文字は先頭からアルファベット順で昇順に並んでいる
$S$ に含まれる文字はすべて異なる
$T$ に含まれる文字はすべて異なる
$1\le Q \le 100$
$w_i$ は英小文字からなる長さ $1$ 以上 $100$ 以下の文字列
$w_i$ は高橋語か青木語のどちらかの単語
$N,M,Q$ は整数

考察

まず、 $S, T$ に含まれる各アルファベットごとに、以下のように分類しておく。

高橋語にのみ含まれる
青木語にのみ含まれる
両方に含まれる or 両方に含まれない

その後、 $Q$ 個の各単語について、それに含まれる各アルファベットを調べ、以下のように判定する。

高橋語にのみ含まれるアルファベットが1つでもあれば「高橋語」と確定
青木語にのみ含まれるアルファベットが1つでもあれば「青木語」と確定
どちらにも該当しなければ判断を保留し、最終的に保留の場合は「どちらともいえない」と判定する。

前半の分類は、mapを用いて実装すると良さそう。詳しくは実装例を参照。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N, M;
11.    cin >> N >> M;
12.    string S, T;
13.    cin >> S >> T;
14. 
15.    map<char, int> mp;
16.    rep(i, 0, N)
17.    {
18.        mp[S[i]] = 1;
19.    }
20.    rep(i, 0, M)
21.    {
22.        if (mp[T[i]] == 1)
23.            mp[T[i]] = 0;
24.        else
25.            mp[T[i]] = -1;
26.    }
27. 
28.    int Q;
29.    cin >> Q;
30. 
31.    while (Q--)
32.    {
33.        string w;
34.        cin >> w;
35. 
36.        bool flag = false;
37.        for (auto &&c : w)
38.        {
39.            if (mp[c] == 1)
40.            {
41.                cout << "Takahashi" << endl;
42.                flag = true;
43.                break;
44.            }
45.            else if (mp[c] == -1)
46.            {
47.                cout << "Aoki" << endl;
48.                flag = true;
49.                break;
50.            }
51.        }
52. 
53.        if (!flag)
54.            cout << "Unknown" << endl;
55.    }
56. 
57.    return 0;
58.}

https://atcoder.jp/contests/abc441/submissions/72512524

実装時間: 5 分

コメント

B問題にしては実装重ための問題だった気がする。