A - Capitalized?

英字からなる文字列 $S$ が与えられる。先頭が大文字で、残りがすべて小文字であるかを判定する。

単純に先頭文字が 'A'～'Z' の範囲にあり、他の文字がすべて 'a'～'z' の範囲にあるかをチェックすればよい。

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

int main() {
    string s;
    cin >> s;
    bool ok = isupper(s[0]);
    for (int i = 1; i < s.size(); ++i) {
        if (!islower(s[i])) ok = false;
    }
    cout << (ok ? "Yes" : "No") << endl;
}

B - Frequency

小文字のみからなる文字列 $S$ が与えられる。出現頻度が最も高い文字のうち、アルファベット順で最も早いものを出力する。

各文字の出現回数をカウントし、a から z の順に走査して最大値を更新すればよい。

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

int main() {
    string s;
    cin >> s;
    vector<int> cnt(26);
    for (char c : s) cnt[c - 'a']++;
    int max_idx = 0;
    for (int i = 1; i < 26; ++i) {
        if (cnt[i] > cnt[max_idx]) max_idx = i;
    }
    cout << char('a' + max_idx) << endl;
}

C - Leftover Recipes

$N$ 種類の食材があり、それぞれ在庫量 $Q_i$ が与えられる。料理 A と B はそれぞれ材料 $A_i$, $B_i$ を消費する。両方の料理を整数回作るとき、合計の最大回数を求めよ。

$N \leq 10$ なので、料理 A を作る回数 $x$ を全探索し、各 $x$ に対して残りの材料で作れる B の最大回数 $y$ を計算する。全体の最大値 $\max(x+y)$ を求める。

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

int main() {
    int N;
    cin >> N;
    vector<ll> Q(N), A(N), B(N);
    for (auto& q : Q) cin >> q;
    for (auto& a : A) cin >> a;
    for (auto& b : B) cin >> b;

    ll max_x = 1e6;
    for (int i = 0; i < N; ++i)
        if (A[i] > 0) max_x = min(max_x, Q[i] / A[i]);

    ll ans = 0;
    for (ll x = 0; x <= max_x; ++x) {
        ll y = 1e18;
        bool valid = true;
        for (int i = 0; i < N; ++i) {
            if (Q[i] < A[i] * x) { valid = false; break; }
            if (B[i] > 0) y = min(y, (Q[i] - A[i] * x) / B[i]);
        }
        if (valid) ans = max(ans, x + y);
    }
    cout << ans << endl;
}

D - Island Tour

$n$ 個の島が円環状に接続されている。訪問順 $s_1, s_2, ..., s_m$ が与えられ、いずれかの橋を切断したときに必要な最小移動距離を求める。

各隣接ペア $(s_i, s_{i+1})$ 間には時計回り・反時計回りの2通りの経路がある。ある辺を切断すると、その経路が使えなくなるため、代替経路の距離が必要になる。

これをすべての辺について効率的に集計するために、円環上の区間加算を差分配列で処理する。具体的には、時計回り経路が区間 $[l, r)$ を通る場合、その代替距離をその区間に加算する。円環のため、区間がラップアラウンドする場合は2つの区間に分割する。

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

ll clockwise_dist(int from, int to, int n) {
    return (from <= to) ? (to - from) : (to - from + n);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> tour(m);
    for (int& x : tour) cin >> x;

    vector<ll> diff(n + 2, 0);

    auto add_range = [&](int l, int r, ll val) {
        if (l <= r) {
            diff[l] += val;
            diff[r + 1] -= val;
        } else {
            diff[l] += val;
            diff[n + 1] -= val;
            diff[1] += val;
            diff[r + 1] -= val;
        }
    };

    ll base = 0;
    for (int i = 0; i < m - 1; ++i) {
        int u = tour[i], v = tour[i + 1];
        ll cw = clockwise_dist(u, v, n);
        ll ccw = n - cw;
        base += min(cw, ccw);
        if (cw != ccw) {
            if (cw < ccw) {
                // 時計回りが最短 → 反時計回りを使うのは [v, u) の辺が切れたとき
                add_range(v, u - 1, ccw - cw);
            } else {
                // 反時計回りが最短 → 時計回りを使うのは [u, v) の辺が切れたとき
                add_range(u, v - 1, cw - ccw);
            }
        }
    }

    ll best_extra = 0;
    for (int i = 1; i <= n; ++i) {
        diff[i] += diff[i - 1];
        best_extra = min(best_extra, diff[i]);
    }

    cout << base + best_extra << '\n';
}