A. Telephone Number

この問題では、与えられた文字列から標準的な11桁の電話番号を作成できるかを判定します。電話番号の最初の数字は'8'でなければならないため、最初の'8'が現れる位置が重要です。文字列の長さを n とすると、最初の'8'のインデックスが n - 11 以下であれば、その後ろに残りの10桁を配置するための十分な文字数が存在します。

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int len;
        string inputStr;
        cin >> len >> inputStr;
        
        size_t firstEightPos = inputStr.find('8');
        
        // 最初の8が見つからない、または位置が後ろすぎる場合
        if (firstEightPos == string::npos || firstEightPos > static_cast<size_t>(len - 11)) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
    
    return 0;
}

B. Lost Numbers

この問題は対話型であり、隠された6つの数字の並び順を推測することが求められます。隣接する2つの要素の積をシステムに問い合わせることで得られる4つのヒントを使用します。使用される数字の集合 {4, 8, 15, 16, 23, 42} は既知であるため、これらの順列（6! = 720通り）を生成し、問い合わせ結果の積と一致するかどうかを総当たりで確認するのが最も確実な方法です。対話型問題であるため、標準入出力の同期を無効化しないよう注意が必要です。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    // 対話型問題では同期を無効化しない
    vector<int> products(5);
    
    // 隣接する要素の積を問い合わせる
    for (int i = 1; i <= 4; ++i) {
        cout << "? " << i << " " << i + 1 << endl;
        cout.flush();
        cin >> products[i];
    }

    vector<int> candidates = {4, 8, 15, 16, 23, 42};
    
    do {
        bool isValid = true;
        // 積が一致するか検証
        for (int i = 1; i <= 4; ++i) {
            if (candidates[i] * candidates[i + 1] != products[i]) {
                isValid = false;
                break;
            }
        }
        
        if (isValid) {
            cout << "!";
            for (int num : candidates) {
                cout << " " << num;
            }
            cout << endl;
            cout.flush();
            return 0;
        }
    } while (next_permutation(candidates.begin() + 1, candidates.end()));

    return 0;
}

C. News Distribution

この問題は、ユーザーが複数のグループに所属しており、ニュースがグループ全体に共有される状況をモデル化しています。特定のユーザーがニュースを知ったとき、それが到達するユーザーの総数は、そのユーザーが属する連結成分（グループ）のサイズと等しくなります。Union-Find（素集合データ構造）を使用して、グループのメンバーを統合し、最終的に各ユーザーの属する集合のサイズをカウントすることで解決できます。

#include <iostream>
#include <vector>

using namespace std;

// Union-Findデータ構造の実装
struct DisjointSet {
    vector<int> parent;
    vector<int> rank_;
    vector<int> setSize;

    DisjointSet(int n) {
        parent.resize(n + 1);
        rank_.resize(n + 1, 0);
        setSize.resize(n + 1, 1);
        for (int i = 0; i <= n; ++i) parent[i] = i;
    }

    int findRoot(int x) {
        if (parent[x] != x) {
            parent[x] = findRoot(parent[x]); // 経路圧縮
        }
        return parent[x];
    }

    void unionSets(int x, int y) {
        int xRoot = findRoot(x);
        int yRoot = findRoot(y);
        
        if (xRoot == yRoot) return;

        // ランクによる統合
        if (rank_[xRoot] < rank_[yRoot]) {
            parent[xRoot] = yRoot;
            setSize[yRoot] += setSize[xRoot];
        } else {
            parent[yRoot] = xRoot;
            setSize[xRoot] += setSize[yRoot];
            if (rank_[xRoot] == rank_[yRoot]) {
                rank_[xRoot]++;
            }
        }
    }

    int getSize(int x) {
        return setSize[findRoot(x)];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    DisjointSet ds(n);
    
    for (int i = 0; i < m; ++i) {
        int groupSize;
        cin >> groupSize;
        
        if (groupSize == 0) continue;
        
        int firstMember, currentMember;
        cin >> firstMember;
        
        for (int j = 1; j < groupSize; ++j) {
            cin >> currentMember;
            ds.unionSets(firstMember, currentMember);
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        cout << ds.getSize(i) << (i == n ? "\n" : " ");
    }
    
    return 0;
}

D. Bicolored RBS

正しい括弧列（Regular Bracket Sequence）が与えられ、各括弧を2色（例えば0と1）で塗り分ける必要があります。条件は、どの正しい部分列についても、すべての括弧が同じ色になってはならないということです。正しい括弧列において、単純に文字列の先頭から順番に色を交互に割り当てる（奇数インデックスは0、偶数インデックスは1など）だけで、この条件を常に満たすことが証明できます。

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int len;
    string sequence;
    cin >> len >> sequence;
    
    // インデックスに基づいて交互に色を出力
    for (int i = 0; i < len; ++i) {
        cout << (i % 2);
    }
    cout << "\n";
    
    return 0;
}