A. ボール詰めゲーム

円柱に詰め込めるボールの体積を求める。円柱の体積は πr²h、各ボールの体積は 4/3 πr³。高さ h の中に収まるボール数は ⌊h/(2r)⌋ 個なので、答えは

πr²h − ⌊h/(2r)⌋ · 4/3 πr³

である。計算量は O(1)。

#include <bits/stdc++.h>
using namespace std;
const double PI = 3.14159265358979323846;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        double r, h; cin >> r >> h;
        int cnt = floor(h / (2 * r));
        double vol = PI * r * r * h - cnt * 4.0 / 3 * PI * r * r * r;
        cout << fixed << setprecision(3) << vol << '\n';
    }
    return 0;
}

B. 数値の集合

与えられた配列の積を 10⁹+7 で割った余りを出力。算術・幾何平均不等式より、積が最小値となるためにはすべての要素を 1 グループにまとめればよい。計算量 O(n)。

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
prod = 1
for v in a:
    prod = (prod * v) % MOD
print(prod)

C. 子猫の列

両端から取り除きながら、末尾に追加される値 a_n+1 以下の要素をまとめて削除する操作を繰り返す。deque を用いて双方向から効率的に削除し、操作回数を数える。計算量 O(n)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 0; i <= n; ++i) cin >> a[i];
    deque<int> dq(a.begin(), a.begin() + n);
    int res = 0;
    while (!dq.empty()) {
        int skip = 0;
        while (!dq.empty() && dq.back() <= a[n]) {
            dq.pop_back();
            ++skip;
        }
        if (dq.empty()) {
            res += skip + 1;
            break;
        }
        dq.pop_back(); ++res;
        if (!dq.empty()) dq.pop_front();
    }
    cout << res;
    return 0;
}

D. 文字列橋

文字列を連結して最長の文字列を作る問題。末尾文字が次の先頭文字と一致する場合のみ連結できる。dp[i] を「i 番目の文字列で終わる最長長さ」とし、各文字 c について「c で終わる最大値」を保持して更新。計算量 O(n)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        int best[128] = {0};
        int ans = 0;
        while (n--) {
            string s; cin >> s;
            int len = s.size();
            int head = s[0], tail = s.back();
            int cur = best[head] + len;
            ans = max(ans, cur);
            best[tail] = max(best[tail], cur);
        }
        cout << ans << '\n';
    }
    return 0;
}

E. カラーグリッド

各色が覆う最小矩形を求め、二次元累積和で各セルが何色に覆われているかをカウント。覆われていないセルの数を答える。計算量 O(nm + 10⁶)。

#include <bits/stdc++.h>
using namespace std;
const int MAXC = 1e6 + 5;
const int MAXN = 1e3 + 5;

struct Rect {
    int x1 = MAXN, x2 = 0, y1 = MAXN, y2 = 0;
    void add(int x, int y) {
        x1 = min(x1, x); x2 = max(x2, x);
        y1 = min(y1, y); y2 = max(y2, y);
    }
    bool valid() const { return x1 <= x2 && y1 <= y2; }
};

Rect color[MAXC];
int diff[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int c; cin >> c;
            color[c].add(i, j);
        }
    for (int c = 0; c < MAXC; ++c) {
        if (!color[c].valid()) continue;
        int x1 = color[c].x1, x2 = color[c].x2;
        int y1 = color[c].y1, y2 = color[c].y2;
        diff[x1][y1]++; diff[x1][y2 + 1]--;
        diff[x2 + 1][y1]--; diff[x2 + 1][y2 + 1]++;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            if (diff[i][j] == 0) ++ans;
        }
    cout << ans;
    return 0;
}

F. ロープウェイ

木構造上で指定された観光地を結ぶ新規路線を 1 本追加し、全ての指定地を根 k から到達可能にする最小コストを求める。指定地が k の部分木に含まれない場合はそれらの LCA に向かう辺を追加する。計算量 O(n log n)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e5 + 5;
const int LOG = 20;

vector<int> g[MAXN];
int dep[MAXN], up[MAXN][LOG];
bool need[MAXN];
ll cnt[MAXN];

void dfs(int u, int p) {
    up[u][0] = p;
    for (int i = 1; i < LOG; ++i)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : g[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        dfs(v, u);
        cnt[u] += cnt[v];
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LOG - 1; i >= 0; --i)
        if (dep[u] - (1 << i) >= dep[v])
            u = up[u][i];
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; --i)
        if (up[u][i] != up[v][i])
            u = up[u][i], v = up[v][i];
    return up[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int m, k; cin >> m >> k;
    for (int i = 0, x; i < m; ++i) {
        cin >> x; need[x] = true;
    }
    dfs(k, k);

    int bad = -1;
    for (int i = 1; i <= n; ++i)
        if (need[i] && cnt[i] == 0) {
            if (bad == -1) bad = i;
            else bad = lca(bad, i);
        }

    ll sum = 0;
    if (bad != -1) {
        for (int i = 1; i <= n; ++i)
            if (need[i]) {
                if (cnt[i]) sum += dep[i] - dep[k];
                else sum += dep[i] - dep[bad] + 1;
            }
        cout << sum;
    } else {
        for (int i = 1; i <= n; ++i)
            if (need[i]) sum += dep[i] - dep[k];
        ll best = sum;
        function<void(int, int)> dfs2 = [&](int u, int p) {
            if (u != k && cnt[u])
                best = min(best, sum - cnt[u] * (dep[u] - dep[k] - 1));
            for (int v : g[u]) if (v != p) dfs2(v, u);
        };
        dfs2(k, k);
        cout << best;
    }
    return 0;
}