Problem A: Alien Sunset

各惑星の自転周期、日の出時刻、日の入り時刻を格納します。自転周期の最大値(max_period)を求め、0からmax_period×1825までの時間を列挙します。各時間について全ての惑星で夜間であることを確認し、条件を満たす最初の時刻を出力します。

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

struct Planet {
    int period, sunrise, sunset;
};

int main() {
    int n, max_period = 0;
    cin >> n;
    vector<Planet> planets(n);
    for (int i = 0; i < n; i++) {
        cin >> planets[i].period >> planets[i].sunrise >> planets[i].sunset;
        max_period = max(max_period, planets[i].period);
    }

    for (int time = 0; time <= max_period * 1825; time++) {
        bool all_night = true;
        for (int j = 0; j < n; j++) {
            int local_time = time % planets[j].period;
            if (planets[j].sunrise < planets[j].sunset) {
                if (local_time > planets[j].sunrise && local_time < planets[j].sunset) {
                    all_night = false;
                    break;
                }
            } else {
                if (local_time < planets[j].sunset || local_time > planets[j].sunrise) {
                    all_night = false;
                    break;
                }
            }
        }
        if (all_night) {
            cout << time << endl;
            return 0;
        }
    }
    cout << "impossible" << endl;
    return 0;
}

Problem C: Cued In

貪欲法による解法です。各ボールの色と得点を対応付けた後、赤球の数をカウントします。赤球のみの場合は1点を出力し、それ以外の場合は(最高得点+1)×赤球数＋その他のボール合計点を計算します。

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

int main() {
    int n;
    cin >> n;
    unordered_map<string, int> color_score = {
        {"red", 1}, {"yellow", 2}, {"green", 3},
        {"brown", 4}, {"blue", 5}, {"pink", 6}, {"black", 7}
    };
    int max_score = 0, total = 0, red_count = 0;
    for (int i = 0; i < n; i++) {
        string color;
        cin >> color;
        if (color == "red") red_count++;
        else {
            int score = color_score[color];
            total += score;
            max_score = max(max_score, score);
        }
    }
    if (red_count == n) cout << 1 << endl;
    else cout << (max_score + 1) * red_count + total << endl;
    return 0;
}

Problem D: Deranging Hat

文字列をソートし、元の文字列と比較します。各位置で文字が異なる場合、適切な位置と交換し交換インデックスを大きい順に出力します。

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

int main() {
    string original;
    cin >> original;
    string sorted = original;
    sort(sorted.begin(), sorted.end());
    for (int i = 0; i < sorted.size(); i++) {
        if (original[i] == sorted[i]) continue;
        for (int j = i + 1; j < sorted.size(); j++) {
            if (sorted[j] == original[i]) {
                if (sorted[i] < sorted[j]) cout << j + 1 << " " << i + 1 << endl;
                else cout << i + 1 << " " << j + 1 << endl;
                swap(sorted[i], sorted[j]);
                break;
            }
        }
    }
    return 0;
}

Problem E: Education

学生グループを降順に、部屋を家賃の昇順にソートします。各学生グループに収容可能な最小家賃の部屋を割り当てます。

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

int main() {
    int student_count, room_count;
    cin >> student_count >> room_count;
    vector<pair<int, int>> students;
    for (int i = 0; i < student_count; i++) {
        int size;
        cin >> size;
        students.push_back({size, i});
    }
    vector<tuple<int, int, int>> rooms;
    for (int i = 0; i < room_count; i++) {
        int capacity;
        cin >> capacity;
        rooms.push_back({capacity, 0, i});
    }
    for (int i = 0; i < room_count; i++) {
        int rent;
        cin >> rent;
        get<1>(rooms[i]) = rent;
    }

    sort(students.rbegin(), students.rend());
    sort(rooms.begin(), rooms.end(), [](auto &a, auto &b) {
        return get<1>(a) < get<1>(b);
    });

    vector<int> assignment(student_count);
    vector<bool> occupied(room_count, false);
    int assigned_count = 0;
    for (auto &[size, idx] : students) {
        bool found = false;
        for (int j = 0; j < room_count; j++) {
            auto &[cap, rent, id] = rooms[j];
            if (!occupied[j] && cap >= size) {
                occupied[j] = true;
                assignment[idx] = id + 1;
                assigned_count++;
                found = true;
                break;
            }
        }
        if (!found) break;
    }
    if (assigned_count != student_count) cout << "impossible" << endl;
    else for (int i = 0; i < student_count; i++) cout << assignment[i] << " \n"[i == student_count - 1];
    return 0;
}

Problem F: Flipping Coins

動的計画法で確率を計算します。dp[throws][heads]をthrows回投げたときheads個が表の確率と定義し、状態遷移を行います。最終的に期待値を計算します。

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

int main() {
    int coin_count, throw_count;
    cin >> coin_count >> throw_count;
    vector<vector<double>> dp(throw_count + 1, vector<double>(coin_count + 1, 0.0));
    dp[0][0] = 1.0;
    for (int i = 1; i <= throw_count; i++) {
        for (int j = 0; j <= coin_count; j++) {
            dp[i][j] += dp[i - 1][j] * 0.5;
            if (j > 0) dp[i][j] += dp[i - 1][j - 1] * 0.5;
            if (j == coin_count - 1) dp[i][j] += dp[i - 1][coin_count] * 0.5;
        }
    }
    double expectation = 0.0;
    for (int i = 0; i <= coin_count; i++) {
        expectation += i * dp[throw_count][i];
    }
    printf("%.8f\n", expectation);
    return 0;
}

Problem I: I Work All Day

各長さで木材長さを割った余りを計算し、最小余りを生成する長さを選択します。

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

int main() {
    int n;
    cin >> n;
    vector<int> lengths(n);
    for (int i = 0; i < n; i++) cin >> lengths[i];
    int wood_length;
    cin >> wood_length;
    int min_remainder = INT_MAX, result;
    for (int len : lengths) {
        int remainder = wood_length % len;
        if (remainder < min_remainder) {
            min_remainder = remainder;
            result = len;
        }
    }
    cout << result << endl;
    return 0;
}

Problem J: Just A Minim

入力値に対応する音符の長さを加算し、合計長さを出力します。

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

int main() {
    int n;
    cin >> n;
    double total = 0.0;
    unordered_map<int, double> length_map = {
        {0, 2.0}, {1, 1.0}, {2, 0.5}, {4, 0.25}, {8, 0.125}, {16, 0.0625}
    };
    for (int i = 0; i < n; i++) {
        int note;
        cin >> note;
        total += length_map[note];
    }
    printf("%.6f\n", total);
    return 0;
}