問題 1：文字列の一致判定と出力生成

この問題では、入力された二つの文字列が完全に一致するかどうかによって出力内容が変化します。一致している場合は特定の形式で 2 行の出力を行い、一致しない場合は 4 行の出力を生成する必要があります。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void execute() {
    string str1, str2;
    if (!(cin >> str1 >> str2)) return;

    if (str1 == str2) {
        cout << 2 << endl;
        cout << str1 << endl;
        cout << str1 << str1 << endl;
    } else {
        cout << 4 << endl;
        cout << str1 << endl;
        cout << str2 << endl;
        cout << str1 << str2 << endl;
        cout << str2 << str1 << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    execute();
    return 0;
}

問題 2：順列の妥当性確認と修正

与えられた数列が 1 から N までの整数を一つずつ含む順列であるかを判定します。すでに順列の条件を満たしていない場合は修正不要を示す値を出力し、満たしている場合は一つの要素を変更して条件を崩す操作を行います。

#include <iostream>
#include <vector>
#include <set>

using namespace std;

void execute() {
    int n;
    cin >> n;
    set<int> observed;
    bool invalid = false;

    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        if (val < 1 || val > n || observed.count(val)) {
            invalid = true;
        }
        observed.insert(val);
    }

    if (invalid) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
        cout << 1 << " " << n + 1 << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    execute();
    return 0;
}

問題 3：貪欲法による文字列分割とソート

文字列を高位から走査し、数字が偶数である時点で区切りを入れて部分文字列を生成します。生成されたリストは、まず長さで比較し、同じ長さの場合は辞書順でソートされて出力されます。

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

using namespace std;

bool compareStrings(const string& a, const string& b) {
    if (a.length() != b.length()) {
        return a.length() < b.length();
    }
    return a + b < b + a;
}

void execute() {
    string input;
    cin >> input;
    vector<string> segments;
    string current;

    for (char c : input) {
        current += c;
        int digit = c - '0';
        if (digit % 2 == 0) {
            segments.push_back(current);
            current = "";
        }
    }

    sort(segments.begin(), segments.end(), compareStrings);

    for (const auto& seg : segments) {
        cout << seg << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    execute();
    return 0;
}

問題 4：配列値の伝播と整合性検証

配列内の零を、最も近い非零要素の値で埋める処理を行います。その後、隣接する要素の差の絶対値総和を計算し、条件を満たすか判定します。境界値の特別な処理も必要であり、すべての要素が零の場合や、両端の処理に注意が必要です。

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

void execute() {
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    vector<bool> original_non_zero(n + 1, false);
    queue<int> q;

    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        if (arr[i] != 0) {
            q.push(i);
            original_non_zero[i] = true;
        }
    }

    if (q.empty()) {
        cout << 2 << " ";
        for (int i = 0; i < n - 1; ++i) {
            cout << 1 << " ";
        }
        cout << endl;
        return;
    }

    while (!q.empty()) {
        int idx = q.front();
        q.pop();

        if (idx > 1 && arr[idx - 1] == 0) {
            arr[idx - 1] = arr[idx];
            q.push(idx - 1);
        }
        if (idx < n && arr[idx + 1] == 0) {
            arr[idx + 1] = arr[idx];
            q.push(idx + 1);
        }
    }

    int diff_sum = 0;
    for (int i = 2; i <= n; ++i) {
        diff_sum += abs(arr[i] - arr[i - 1]);
    }

    if (diff_sum > 1) {
        cout << -1 << endl;
    } else if (diff_sum == 0) {
        if (original_non_zero[1] && original_non_zero[n]) {
            cout << -1 << endl;
        } else {
            if (!original_non_zero[1]) {
                arr[1]++;
            } else {
                arr[n]++;
            }
            for (int i = 1; i <= n; ++i) {
                cout << arr[i] << " ";
            }
            cout << endl;
        }
    } else {
        for (int i = 1; i <= n; ++i) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    execute();
    return 0;
}

問題 5：木構造におけるノードの塗り分け

木構造におけるノードの塗り分け問題です。未確定のノードを breadth-first search で隣接ノードの色に基づいて決定し、最終的に矛盾がないか検証します。すべてのノードが未確定の場合は初期値を設定してから処理を開始します。

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

void execute() {
    int n;
    cin >> n;
    string labels;
    cin >> labels;

    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int unknown_count = 0;
    for (char c : labels) {
        if (c == '?') unknown_count++;
    }

    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (labels[i] != '?') {
            q.push(i);
        }
    }

    if (unknown_count == n) {
        labels[0] = 'p';
        q.push(0);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (labels[v] == '?') {
                labels[v] = (labels[u] == 'd') ? 'p' : 'd';
                q.push(v);
            }
        }
    }

    bool valid = true;
    for (int i = 0; i < n; ++i) {
        for (int v : adj[i]) {
            if (labels[i] == labels[v]) {
                valid = false;
                break;
            }
        }
        if (!valid) break;
    }

    if (valid) {
        cout << labels << endl;
    } else {
        cout << -1 << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    execute();
    return 0;
}