A. Hitoshizuku 貪欲法で解きます。 右端点でソートした後、マッチングされていない点に対して、各右端点以下の点を管理し、その端点が管理されている集合の中で右端点が最も小さい2点とマッチングします。 最適性の証明は調整法によるそうです。 コード例

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct Interval {
    int left, right, id;
    bool operator<(const Interval& other) const {
        if (right != other.right) return right < other.right;
        return left > other.left;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        n *= 3;
        vector<Interval> intervals(n);
        set<Interval> remaining;
        vector<bool> visited(n, false);
        vector<tuple<int, int, int>> result;
        
        for (int i = 0; i < n; ++i) {
            cin >> intervals[i].left >> intervals[i].right;
            intervals[i].id = i + 1;
            remaining.insert(intervals[i]);
        }
        
        sort(intervals.begin(), intervals.end());
        
        for (const auto& interval : intervals) {
            if (visited[interval.id - 1]) continue;
            visited[interval.id - 1] = true;
            
            // 管理集合から現在の区間を削除
            remaining.erase(interval);
            
            // 右端点が現在の区間の右端点以下のものを管理集合に追加
            vector<Interval> to_add;
            for (auto it = remaining.begin(); it != remaining.end(); ) {
                if (it->right <= interval.right) {
                    to_add.push_back(*it);
                    it = remaining.erase(it);
                } else {
                    break;
                }
            }
            
            for (const auto& add : to_add) {
                remaining.insert(add);
            }
            
            if (remaining.size() < 2) {
                cout << "No\n";
                goto next_case;
            }
            
            // 管理集合から最も右端点が小さい2点を選択
            auto first = *remaining.begin();
            remaining.erase(remaining.begin());
            auto second = *remaining.begin();
            remaining.erase(remaining.begin());
            
            visited[first.id - 1] = true;
            visited[second.id - 1] = true;
            result.emplace_back(interval.id, first.id, second.id);
        }
        
        cout << "Yes\n";
        for (const auto& match : result) {
            cout << get<0>(match) << ' ' << get<1>(match) << ' ' << get<2>(match) << '\n';
        }
        
    next_case:
        continue;
    }
    
    return 0;
}

E. Corrupted Scoreboard Log 大規模シミュレーション問題です。全探索が必要です。 0299と1100の組み合わせ文字列を事前に処理し、各"try"の前の数字からどの組み合わせかを特定します。注意点として"22tries"のようなケースは"2 2 tries"のように分割可能で、問題の正解/不正解を別々に処理する必要があります。 データに"00"が含まれる場合があるため、特別な処理が必要です。 最初の数字列には問題数、ペナルティ、最初の"try"の情報が含まれており、情報を列挙して問題数とペナルティを取得できます。問題数は最大2桁なので、分岐処理が必要です。 その他の注意点として、DFSで後続の組み合わせを事前に処理するとタイムアウトするため、列挙の中にDFSを配置する必要があります。変数名の再利用に注意してください。 コード例

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

using i64 = long long;

map<string, vector<pair<int, int>>> combinations;

void preprocess() {
    for (int i = 1; i <= 299; ++i) {
        string si = to_string(i);
        for (int j = 1; j <= 100; ++j) {
            string sj = to_string(j);
            combinations[si + sj].emplace_back(i, j);
        }
    }
    
    for (int i = 1; i <= 100; ++i) {
        string si = to_string(i);
        combinations[si].emplace_back(0, i);
        si = "0" + si;
        combinations[si].emplace_back(0, i);
    }
}

bool solve_case(const string& s) {
    if (s == "00") {
        cout << "0 0\n";
        return true;
    }
    
    vector<string> parts;
    int last = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'y' || s[i] == 's') {
            parts.push_back(s.substr(last, i - last + 1));
            last = i + 1;
        }
    }
    
    int first_size = parts[0].size();
    first_size -= 3;
    bool first_plural = false;
    if (parts[0].back() == 's') {
        first_size -= 2;
        first_plural = true;
    }
    
    int total_parts = parts.size();
    bool found = false;
    
    auto dfs = [&](auto& self, int idx, int remaining_tasks, int remaining_penalty, 
                  vector<tuple<int, int, bool>>& current) -> bool {
        if (found) return true;
        if (remaining_tasks < 0 || remaining_penalty < 0) return false;
        if (idx >= parts.size()) {
            if (remaining_tasks == 0 && remaining_penalty == 0) {
                cout << get<0>(current[0]) << " " << get<1>(current[0]) << " ";
                for (int i = 0; i < current.size(); ++i) {
                    auto& [tasks, penalty, solved] = current[i];
                    if (solved) cout << tasks << " ";
                    cout << penalty << " " << (penalty > 1 ? "tries" : "try");
                    if (i != current.size() - 1) cout << " ";
                }
                cout << "\n";
                found = true;
                return true;
            }
            return false;
        }
        
        string part = parts[idx];
        int part_size = part.size();
        part_size -= 3;
        bool part_plural = false;
        if (part.back() == 's') {
            part_size -= 2;
            part_plural = true;
        }
        string key = part.substr(0, part_size);
        
        for (auto& [tasks, penalty] : combinations[key]) {
            if ((part_plural && penalty > 1) || (!part_plural && penalty == 1)) {
                current.emplace_back(tasks, penalty, true);
                if (to_string(tasks) + to_string(penalty) == key) {
                    if (self(self, idx + 1, remaining_tasks - 1, 
                           remaining_penalty - tasks - (penalty - 1) * 20, current)) {
                        return true;
                    }
                } else {
                    current.back() = {tasks, penalty, false};
                    if (self(self, idx + 1, remaining_tasks, remaining_penalty, current)) {
                        return true;
                    }
                }
                current.pop_back();
            }
        }
        return false;
    };
    
    first_size -= 1;
    for (int len = 1; len <= 6 && first_size >= 2; ++len, --first_size) {
        string key = parts[0].substr(first_size, len);
        string num = parts[0].substr(1, first_size - 1);
        
        if (num.size() > 7 || !combinations.count(key)) continue;
        
        int tasks = parts[0][0] - '0';
        int penalty = stoi(num);
        
        vector<tuple<int, int, bool>> current;
        if (dfs(dfs, 1, tasks - 1, penalty - get<1>(combinations[key][0]) - 
               (get<1>(combinations[key][0]) - 1) * 20, current)) {
            return true;
        }
        
        if (parts[0][0] == '1' && parts[0][1] <= '3' && penalty > 10) {
            tasks = tasks * 10 + (parts[0][1] - '0');
            penalty = stoi(num.substr(1));
            current.clear();
            if (dfs(dfs, 1, tasks - 1, penalty - get<1>(combinations[key][0]) - 
                   (get<1>(combinations[key][0]) - 1) * 20, current)) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    preprocess();
    
    int t, M;
    cin >> t >> M;
    while (t--) {
        string s;
        cin >> s;
        if (!solve_case(s)) {
            cout << "No solution found\n";
        }
    }
    
    return 0;
}

G. Collatz Conjecture 数論問題です。 連続する+B操作を/Aできるまで続けることを1回の操作と見なします。この操作は modulo B の意味で ×A⁻¹ (mod B) と見なせます。 AとBが互いに素であるため、オイラーの定理より A^φ(B) ≡ 1 (mod B) が成り立ち、 modulo B の意味で必ず循環します。 数n自体を考えた場合、1回の操作後は (n+B(A-1))/A 以下になります。n > B の場合、変換後の数字は必ず n 未満になります。n ≤ B の場合、変換後の数字は B 以下になります。 したがって、1回の操作を考えると、最終的に循環に入るのは 1B の間の数字です。 n自体が循環に入るかを考えるには、1Bの間でnと合同なn'を考えます。このn'が循環に入る際に、Aの倍数になる前に+B操作でnに到達できる場合、nは循環内にあり、そうでない場合はnは到達不能です。 つまり、exgcdを用いて A|n'+tB を満たす最小の非負整数tを求め、n ≤ n'+tB かどうかを確認します。 時間計算量は O(T log min(A,B)) です。 コード例

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

using ull = unsigned long long;
using ll = long long;

ull modmul(ull a, ull b, ull mod) {
    ll ret = a * b - mod * ull(1.L / mod * a * b);
    return ret + mod * (ret < 0) - mod * (ret >= (ll)mod);
}

ull modpow(ull base, ull exp, ull mod) {
    ull result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = modmul(result, base, mod);
        base = modmul(base, base, mod);
        exp >>= 1;
    }
    return result;
}

bool is_prime(ull n) {
    if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
    vector<ull> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    ull s = __builtin_ctzll(n - 1), d = n >> s;
    for (ull a : bases) {
        ull p = modpow(a % n, d, n), i = s;
        while (p != 1 && p != n - 1 && a % n && i--) p = modmul(p, p, n);
        if (p != n - 1 && i != s) return false;
    }
    return true;
}

ull pollard_rho(ull n) {
    auto f = [n](ull x) { return modmul(x, x, n) + 1; };
    ull x = 0, y = 0, prd = 2, i = 1, q;
    while (true) {
        if (x == y) x = ++i, y = f(x);
        if ((q = modmul(prd, max(x, y) - min(x, y), n))) prd = q;
        x = f(x), y = f(f(y, i));
        if (__gcd(prd, n) > 1) break;
    }
    return __gcd(prd, n);
}

vector<ull> factorize(ull n) {
    if (n == 1) return {};
    if (is_prime(n)) return {n};
    ull d = pollard_rho(n);
    auto left = factorize(d), right = factorize(n / d);
    left.insert(left.end(), right.begin(), right.end());
    return left;
}

ll extended_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1;
    ll g = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

bool solve_case(ll A, ll B, ll n) {
    vector<ull> factors = factorize(A);
    sort(factors.begin(), factors.end());
    factors.erase(unique(factors.begin(), factors.end()), factors.end());
    
    ll phi = 1;
    for (ull p : factors) {
        phi *= (p - 1) * (A / p);
    }
    
    ll inv_B = modpow(B, phi - 1, A);
    ll lower_bound = n - B * min(((n % A - B % A + A) % A * inv_B % A), n / B);
    ll step = (A - B % A) % A * inv_B % A;
    
    lower_bound *= A;
    ll max_steps = min(step, lower_bound / B);
    lower_bound -= max_steps * B;
    
    if (lower_bound % B == n % B && n >= lower_bound) {
        cout << "Yes\n";
        return true;
    }
    
    if (lower_bound < B) {
        cout << "Yes\n";
        return true;
    }
    
    cout << "No\n";
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        ll A, B, n;
        cin >> A >> B >> n;
        solve_case(A, B, n);
    }
    
    return 0;
}

I. Color-Balanced Tree 二部グラフ彩色問題です。 まず木全体を二部グラフ彩色し、同色のノード間の距離が3以下になるようにします。しかし、この方法では色の数が不均衡になる可能性があるため、余分な色をすべて葉ノードに割り当てます。このようにすると、菊石グラフの場合でも最大距離は3になります。 コード例

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

using ll = long long;

void solve_case() {
    int n;
    cin >> n;
    n *= 2;
    vector<vector<int>> graph(n + 1);
    
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    vector<int> colors(n + 1);
    vector<int> count(2, 0);
    
    function<void(int, int, int)> dfs = [&](int node, int parent, int color) {
        colors[node] = color;
        count[color]++;
        for (int neighbor : graph[node]) {
            if (neighbor != parent) {
                dfs(neighbor, node, color ^ 1);
            }
        }
    };
    
    dfs(1, 0, 0);
    
    // 色の不均衡を調整
    if (count[0] != count[1]) {
        int target_color = (count[0] > count[1]) ? 1 : 0;
        for (int i = 1; i <= n; ++i) {
            if (graph[i].size() == 1 && colors[i] == target_color ^ 1) {
                colors[i] = target_color;
                count[0] = (target_color == 0) ? count[0] + 1 : count[0] - 1;
                count[1] = (target_color == 1) ? count[1] + 1 : count[1] - 1;
                break;
            }
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        cout << colors[i] << (i == n ? '\n' : ' ');
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve_case();
    }
    
    return 0;
}