2024年問題

RC-u1 熱天気判定

1からnまでのループを行い、気温が35度以上かどうかをチェックし、指定されたルールに従ってカウントします。

void resolve() {
    cin >> n >> k;
    int result = 0, count = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> temp;
        if (temp >= 35) {
            if (k == 4) count++;
            else result++;
        }
        k++;
        if (k == 8) k = 1;
    }
    cout << result << " " << count << endl;
}

RC-u2 ランキングポイント計算

各試合の順位とキル数を読み取り、それに基づいてチームごとの合計スコアを計算します。

int scores[21];
void resolve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 20; ++j) {
            cin >> rank >> kills;
            switch (rank) {
                case 1: scores[j] += 12; break;
                case 2: scores[j] += 9; break;
                case 3: scores[j] += 7; break;
                case 4: scores[j] += 5; break;
                case 5: scores[j] += 4; break;
                case 6: case 7: scores[j] += 3; break;
                case 8: case 9: case 10: scores[j] += 2; break;
                default: scores[j] += 1; break;
            }
            scores[j] += kills;
        }
    }
    for (int i = 1; i <= 20; ++i) cout << i << " " << scores[i] << endl;
}

RC-u3 ウォームアップマシン配置

既存のウォームアップマシンのカバー範囲を事前に処理し、隠れたウォームアップマシンを探すために全ての空地を列挙します。

#include <bits/stdc++.h>
using namespace std;

int grid[1010][1010], covered[1010][1010];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

void resolve() {
    cin >> n >> m;
    char ch;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> ch;
            if (ch == '.') grid[i][j] = 0;
            else if (ch == 'c') grid[i][j] = 1;
            else if (ch == 'w') grid[i][j] = 2;
            else {
                grid[i][j] = 3;
                for (int k = 0; k < 4; ++k) {
                    int nx = i + dx[k], ny = j + dy[k];
                    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) covered[nx][ny] = 1;
                }
            }
        }
    }
    vector= 1 && nx <= n && ny >= 1 && ny <= m && !grid[nx][ny]) {
                        candidates.emplace_back(nx, ny);
                    }
                }
            }
        }
    }
    bool found = false;
    for (auto [x, y] : candidates) {
        bool valid = true;
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
                covered[nx][ny]++;
                if (grid[nx][ny] == 1) valid = false;
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (grid[i][j] == 2 && !covered[i][j]) {
                    valid = false;
                    break;
                }
            }
            if (!valid) break;
        }
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) covered[nx][ny]--;
        }
        if (valid) {
            cout << x << " " << y << endl;
            found = true;
            break;
        }
    }
    if (!found) cout << "Too cold!" << endl;
}

RC-u4 オクトパスグラフ判定

BFSを使って各連結成分を分離し、その後トポロジカルソートを利用してサイクルを見つけるアルゴリズムを実装します。

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1010];
int degree[1010];

void resolve() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        degree[u]++, degree[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 1) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (--degree[v] == 1) q.push(v);
        }
    }
    int cycle_nodes = 0;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] > 1) cycle_nodes++;
    }
    if (cycle_nodes > 0) {
        int cycle_count = 0;
        for (int i = 1; i <= n; ++i) {
            if (degree[i] == 2) cycle_count++;
        }
        if (cycle_count == cycle_nodes) cout << "Yes " << cycle_nodes << endl;
        else cout << "No " << cycle_nodes << endl;
    } else {
        cout << "No 0" << endl;
    }
}

RC-u5 タスクスケジューリング

タスクの期限と報酬を考慮に入れた01バックパックDPを使用します。

struct Task {
    int time, deadline, profit;
};

bool compare(const Task &a, const Task &b) {
    if (a.deadline != b.deadline) return a.deadline < b.deadline;
    return a.time < b.time;
}

void resolve() {
    cin >> n;
    vector<Task> tasks(n);
    for (auto &task : tasks) cin >> task.time >> task.deadline >> task.profit;
    sort(tasks.begin(), tasks.end(), compare);
    int dp[5010] = {0};
    for (const auto &task : tasks) {
        for (int j = task.deadline; j >= task.time; --j) {
            dp[j] = max(dp[j], dp[j - task.time] + task.profit);
        }
    }
    int max_profit = *max_element(dp, dp + 5010);
    cout << max_profit << endl;
}

2023年問題

RC-u1 アジアンゲームメダルチャレンジ

各国が獲得した金、銀、銅メダルの数をカウントし、指定された順序で並べ替えます。

struct MedalCount {
    int medals[3];
    int id;
};

bool compare(MedalCount &a, MedalCount &b) {
    if (a.medals[0] != b.medals[0]) return a.medals[0] > b.medals[0];
    if (a.medals[1] != b.medals[1]) return a.medals[1] > b.medals[1];
    return a.medals[2] > b.medals[2];
}

void resolve() {
    cin >> n;
    MedalCount countries[2] = {{0, 0, 0, 0}, {0, 0, 0, 1}};
    for (int i = 0; i < n; ++i) {
        int country, medal;
        cin >> country >> medal;
        countries[country - 1].medals[medal - 1]++;
    }
    sort(countries, countries + 2, compare);
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            cout << countries[i].medals[j];
            if (j != 2) cout << " ";
            else cout << endl;
        }
    }
    if (countries[0].id == 0) cout << "The first win!" << endl;
    else cout << "The second win!" << endl;
}

RC-u2 退院手続き

各薬剤の種類と薬剤名を保持し、入力された薬剤がどの薬剤の組み合わせであるかを検索します。

vector<string> drinks[4];

void resolve() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        string drink, category;
        cin >> drink >> category;
        drinks[category[0] - 'A'].push_back(drink);
    }
    for (int i = 0; i < m; ++i) {
        string input;
        cin >> input;
        bool found = false;
        for (int j = 0; j < 4; ++j) {
            for (const auto &drink : drinks[j]) {
                if (drink == input) {
                    cout << (char)('A' + j) << endl;
                    found = true;
                    break;
                }
            }
            if (found) break;
        }
        if (found) continue;
        vector<string> possibilities;
        for (int j = 0; j < 4; ++j) {
            for (const auto &prefix : drinks[j]) {
                if (input.substr(0, prefix.size()) != prefix) continue;
                for (int k = 0; k < 4; ++k) {
                    for (const auto &suffix : drinks[k]) {
                        if (prefix.size() + suffix.size() != input.size()) continue;
                        if (input.substr(prefix.size(), suffix.size()) != suffix) continue;
                        possibilities.push_back(string(1, 'A' + j) + string(1, 'A' + k));
                    }
                }
            }
        }
        if (possibilities.size() != 1) cout << 'D' << endl;
        else cout << possibilities[0] << endl;
    }
}

RC-u3 ダイスゲーム戦略

ダイスを振る可能性のある全てのシナリオを列挙し、最良の戦略を選択します。

int dice[10], mask[10];
double probability[10][10];
int best_mask, best_count, best_dice;

void generate(int pos, int count) {
    if (pos > 5) {
        double prob = 1.0;
        for (int i = 1; i <= 5; ++i) {
            prob *= probability[dice[i]][mask[i]];
        }
        if (prob > probability[best_dice][best_count]) {
            best_dice = dice[1];
            best_count = count;
            best_mask = 0;
            for (int i = 1; i <= 5; ++i) {
                best_mask |= (mask[i] << (i - 1));
            }
        }
        return;
    }
    for (int i = 0; i < 2; ++i) {
        mask[pos] = i;
        generate(pos + 1, count + i);
    }
}

void resolve() {
    for (int i = 1; i <= 5; ++i) cin >> dice[i];
    for (int i = 1; i <= 6; ++i) {
        probability[i][0] = 1.0 / 6.0;
        probability[i][1] = 1.0;
    }
    best_dice = 0;
    best_count = 0;
    generate(1, 0);
    cout << best_dice << " " << best_count << " " << best_mask << endl;
}

RC-u4 相対論マスター

論点をノード、推論をエッジとしての有向グラフを作成し、BFSを使用して論理的な矛盾を見つけるアルゴリズムを実装します。

#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> node_id;
vector<string> id_node;
vector<vector<int>> graph;
bool visited[10010];
int level[10010];

void resolve() {
    cin >> n;
    graph.resize(2 * n + 1);
    for (int i = 0; i < n; ++i) {
        string a, b;
        int na, nb;
        cin >> a >> na >> b >> nb;
        if (node_id.find(a) == node_id.end()) {
            node_id[a] = id_node.size();
            id_node.push_back(a);
        }
        if (node_id.find(b) == node_id.end()) {
            node_id[b] = id_node.size();
            id_node.push_back(b);
        }
        na = node_id[a];
        nb = node_id[b];
        if (nb % 2 == 0) nb--;
        else nb++;
        graph[na].push_back(nb);
    }
    int min_length = INT_MAX;
    string result;
    for (int start = 0; start < id_node.size(); ++start) {
        fill(visited, visited + 2 * n + 1, false);
        fill(level, level + 2 * n + 1, 0);
        queue<int> q;
        q.push(start);
        visited[start] = true;
        level[start] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : graph[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    level[v] = level[u] + 1;
                    q.push(v);
                    if (v == start) {
                        if (level[v] < min_length) {
                            min_length = level[v];
                            result = id_node[u];
                        }
                    }
                }
            }
        }
    }
    if (min_length == INT_MAX) cout << "No contradiction found." << endl;
    else cout << "Contradiction found at " << result << " with length " << min_length << "." << endl;
}

RC-u5 相対的成功と失敗

各生徒の競技とゲームの参加状況をもとに、最長の非減少部分列を見つけるDPアルゴリズムを実装します。

struct Student {
    int compete, game;
};

int dp[3];

void resolve() {
    cin >> n;
    vector<Student> students(n);
    for (auto &student : students) cin >> student.compete >> student.game;
    for (int i = 0; i < 3; ++i) dp[i] = 0;
    for (const auto &student : students) {
        int val = student.compete - student.game + 1;
        for (int j = val; j <= 2; ++j) {
            dp[val] = max(dp[val], dp[j] + 1);
        }
    }
    int longest = max(dp[0], max(dp[1], dp[2]));
    cout << n - longest << endl;
}

2022年問題

RC-u1 金币管理

モンスターからの報酬を追跡し、指定されたしきい値を超えた場合に消費を行います。

void resolve() {
    cin >> n >> m;
    int current = 0, transactions = 0;
    for (int i = 0; i < n; ++i) {
        int reward;
        cin >> reward;
        if (current + reward > m) {
            transactions++;
            current = 0;
        }
        current += reward;
    }
    cout << transactions << endl;
}

RC-u2 スマート薬剤管理

各薬剤の最終服用時間を追跡し、薬剤の服用間隔が適切であるかチェックします。

int last_taken[1001];

void resolve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> last_taken[i];
    for (int i = 0; i < m; ++i) {
        int time, k;
        cin >> time >> k;
        for (int j = 0; j < k; ++j) {
            int med;
            cin >> med;
            if (last_taken[med] + last_taken[med] > time) {
                cout << "Don't take " << med << " at " << time << "!" << endl;
            } else {
                last_taken[med] = time;
            }
        }
    }
}

RC-u3 ダンジョンマスター

ダイスロールの表現式を解析し、ダイスの最小値と最大値を計算します。

void resolve() {
    cin >> expression;
    if (expression[0] != '+' && expression[0] != '-') expression = '+' + expression;
    int min_val = 0, max_val = 0;
    int i = 0, sign = 1;
    while (i < expression.size()) {
        if (expression[i] == '+') sign = 1;
        else if (expression[i] == '-') sign = -1;
        i++;
        int count = 0, faces = 0;
        while (i < expression.size() && isdigit(expression[i])) {
            count = count * 10 + (expression[i] - '0');
            i++;
        }
        if (expression[i] == 'd') {
            i++;
            while (i < expression.size() && isdigit(expression[i])) {
                faces = faces * 10 + (expression[i] - '0');
                i++;
            }
            if (faces == 0) faces = 1;
            min_val += sign * count;
            max_val += sign * count * faces;
        } else {
            min_val += sign * count;
            max_val += sign * count;
        }
    }
    cout << min_val << " " << max_val << endl;
}

RC-u4 パーティー編成

可能な全てのパーティーコンポジションを列挙し、最適なパーティーコンポジションを見つけるアルゴリズムを実装します。

struct Member {
    int count;
    bool roles[3];
};

Member members[6];
bool used[6];
int optimal_score, optimal_diff, optimal_first, optimal_second;
string first_party, second_party;

void dfs(int index, int score, int first_count, int second_count, string first, string second) {
    if (index == 6) {
        if (score > optimal_score || (score == optimal_score && abs(first_count - second_count) < optimal_diff)) {
            optimal_score = score;
            optimal_diff = abs(first_count - second_count);
            optimal_first = first_count;
            optimal_second = second_count;
            first_party = first;
            second_party = second;
        }
        return;
    }
    used[index] = true;
    dfs(index + 1, score + 1, first_count + members[index].count, second_count, first + to_string(index + 1), second);
    dfs(index + 1, score + 1, first_count, second_count + members[index].count, first, second + to_string(index + 1));
    used[index] = false;
}

void resolve() {
    for (int i = 0; i < 6; ++i) cin >> members[i].count;
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 3; ++j) {
            char role;
            cin >> role;
            members[i].roles[j] = (role == '1');
        }
    }
    optimal_score = 0;
    optimal_diff = INT_MAX;
    dfs(0, 0, 0, 0, "", "");
    if (optimal_score == 0) cout << "GG" << endl;
    else {
        cout << first_party << endl;
        cout << second_party << endl;
    }
}

RC-u5 木構造と二部グラフ

木構造を二部グラフに分解し、その辺の最大数を計算します。

vector<int> adj_list[1001];
bool colored[1001];

void dfs(int node, int color) {
    colored[node] = color;
    for (int neighbor : adj_list[node]) {
        if (!colored[neighbor]) dfs(neighbor, 3 - color);
    }
}

void resolve() {
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    int color1 = 0, color2 = 0;
    for (int i = 1; i <= n; ++i) {
        if (!colored[i]) {
            dfs(i, 1);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (colored[i] == 1) color1++;
        else color2++;
    }
    int max_edges = color1 * color2 - (n - 1);
    cout << max_edges << endl;
}