問題一覧

• A: StringGame (考察)
• B: SequenceGame (貪欲法+二分探索)
• C: 猫の世話 (幾何学、考察)
• D: 数列H (数学)
• E: キャンディーH (考察)
• F: エンコーディング1.0 (動的計画法)
• G: エンコーディング2.0 (深さ優先探索)
• H: 迷路 (幅優先探索+二点探索)
• I: レーティング (考察+優先度付きキュー)
• J: 文字列変換 (総当り)
• K: 新ゲーム! (計算幾何学+最短経路)

A: StringGame (考察)

概要: 長さnの文字列strと操作回数xが与えられる。操作は文字列の先頭文字を末尾に移動し、先頭を削除する。x回操作後の文字列を求めよ。

制約: 1≤n≤1e5, 1≤x≤1e18

解法: 操作をn回行うと元の文字列に戻る。よってxをnで割った余りを求める。その後、文字列の後ろn-x文字と先頭x文字を連結して出力する。

計算量: O(n)

#include <iostream>
#include <string>
using namespace std;
int main() {
    long long len, op_count;
    string str;
    cin >> len >> op_count;
    cin >> str;
    op_count %= len;
    if (op_count == 0) {
        cout << str << endl;
    } else {
        cout << str.substr(op_count) << str.substr(0, op_count) << endl;
    }
    return 0;
}

B: SequenceGame (貪欲法+二分探索)

概要: n個の配列があり、各配列はm個の整数を含む。各配列から最大1つの要素を選択するか、何も選ばない場合に形成できる最長増加部分列の長さを求めよ。

制約: n<1e4, 要素値≤10

解法: 最長増加部分列の貪欲+二分探索手法を拡張。各グループを処理する際、一時配列tempを用いてグループ内の更新を分離し、グループ処理後に本配列を更新する。

計算量: O(n*m*log n)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> data(n+1, vector<int>(m+1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> data[i][j];
        }
    }
    int max_len =打ち0;
    vector<int> dp(n+1, 1e9);
    vector<int> temp(n+1, 1e9);
    for (int i = 1; i <= n; ++i) {
        int current_len = max_len;
        for (int j = 1; j <= current_len; ++j) {
            temp[j] = dp[j];
        }
        for (int j = 1; j <= m; ++j) {
            int left = 1, right = current_len + 1, mid;
            while (left < right) {
                mid = (left + right) >> 1;
                if (dp[mid] >= data[i][j]) right = mid;
                else left = mid + 1;
            }
            temp[left] = min(temp[left], data[i][j]);
            max_len = max(max_len, left);
        }
        for (int j = 1; j <= max_len; ++j) {
            dp[j] = temp[j];
        }
    }
    cout << max_len << endl;
    return 0;
}

C: 猫の世話 (幾何学、考察)

概要: 第一象限またはx軸・y軸上にn個の点がある。これらの点を結び、x軸・y軸と閉図形を形成する場合の最小線分長を求めよ。

制約: 1≤n≤1e5, 0≤x_i,y_i≤1e9

解法: x軸とy軸上に少なくとも1点ずつ必要。最小長はy軸上でx軸に最も近い点と、x軸上でy軸に最も近い点を結ぶ線分。

計算量: O(n)

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    double min_x = 1e18, min_y = 1e18;
    bool x_axis = false, y_axis = false;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        double u, v;
        cin >> u >> v;
        if (u == 0) {
            y_axis = true;
            min_y = min(min_y, v);
        }
        if (v == 0) {
            x_axis = true;
            min_x = min(min_x, u);
        }
    }
    if (x_axis && y_axis) {
        cout << fixed << setprecision(6) << hypot(min_x, min_y) << '\n';
    } else {
        cout << "Poor Little H!" << '\n';
    }
    return 0;
}

D: 数列H (数学)

概要: a_1=1, 4*a_{i-1}*a_i = (a_{i-1}+a_i-1)^2 を満たす数列の第n項を求めよ。

制約: nは大きな整数

解法: 式を変形すると√a_i - √a_{i-1} = 1となる。これは完全平方数の列であり、第n項はn^2。

計算量: O(1)

n = int(input())
print(n * n)

E: キャンディーH (考察)

概要: T組のテストケース。各ケースで整数k,nが与えられる。初期値1から始め、+1または*kの操作でnにする最小操作回数を求めよ。

制約: n<1e4, k≤10

解法: k=1の場合はn-1。それ以外は逆から計算し、nがk以上ならn%k回の加算と1回の乗算を行い、nをkで割る。最終的にn<kとなったらn-1を加算。

計算量: O(T log_k n)

#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        long long k, n;
        cin >> k >> n;
        if (k == 1) {
            cout << n - 1 << '\n';
            continue;
        }
        long long steps = 0;
        while (n >= k) {
            steps += n % k;
            steps++;
            n /= k;
        }
        cout << steps + n - 1 << '\n';
    }
    return 0;
}

F: エンコーディング1.0 (動的計画法)

概要: 16進数文字からなる長さnの文字列について、重複しない増加部分列の総数を求めよ。

制約: 1≤n≤1e6

解法: dp配列で各文字を末尾とする部分列数を管理。同じ文字が複数回現れる場合、後ろの文字のカウントが前のものを包含するため、都度リセットする。

計算量: O(16n)

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
    string s;
    cin >> s;
    vector<long long> cnt(16, 0);
    int n = s.length();
    s = " " + s;
    for (int i = 1; i <= n; ++i) {
        int idx;
        if (s[i] >= 'A' && s[i] <= 'F') {
            idx = s[i] - 'A' + 10;
        } else {
            idx = s[i] - '0';
        }
        cnt[idx] = 1;
        for (int j = 0; j < idx; ++j) {
            cnt[idx] += cnt[j];
        }
    }
    long long total = 0;
    for (int i = 0; i < 16; ++i) {
        total += cnt[i];
    }
    cout << total << endl;
    return 0;
}

G: エンコーディング2.0 (深さ優先探索)

概要: 16進数文字列の全ての重複しない増加部分列を辞書順で出力せよ。

制約: 1≤n≤1e6

解法: 各文字の出現位置を記録し、DFSで部分列を構築。次に使用可能な文字の位置を二分探索で決定。

計算量: O(2^16 log n)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> pos[16];
int seq[16];
void dfs(int depth, int last_char, int last_pos) {
    for (int i = 0; i < depth; ++i) {
        if (seq[i] < 10) cout << seq[i];
        else cout << char(seq[i] - 10 + 'A');
        if (i == depth - 1) cout << endl;
    }
    for (int ch = last_char + 1; ch < 16; ++ch) {
        if (!pos[ch].empty()) {
            auto it = upper_bound(pos[ch].begin(), pos[ch].end(), last_pos);
            if (it != pos[ch].end()) {
                seq[depth] = ch;
                dfs(depth + 1, ch, *it);
            }
        }
    }
}
int main() {
    string s;
    cin >> s;
    for (size_t i = 0; i < s.length(); ++i) {
        if (s[i] >= '0' && s[i] <= '9') {
            pos[s[i] - '0'].push_back(i);
        } else {
            pos[s[i] - 'A' + 10].push_back(i);
        }
    }
    dfs(0, -1, -1);
    return 0;
}

H: 迷路 (幅優先探索+二点探索)

概要: n×nグリッドの各セルに重みがある。(1,1)から(n,n)へのパスで通過するセルの最大重みと最小重みの差の最小値を求めよ。

制約: 1≤n≤100, 重み≤3000

解法: 最小重みlと最大重みrの範囲をスライドさせ、BFSで到達可能性を確認。lとrを適切に増減させて最小範囲を探索。

計算量: O(6000*n^2)

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int grid[101][101];
bool visited[101][101];
int n;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool can_reach(int low, int high) {
    memset(visited, 0, sizeof(visited));
    queue<pair<int,int>> q;
    q.push({1,1});
    visited[1][1] = true;
    if (min(grid[1][1], grid[n][n]) < low || max(grid[1][1], grid[n][n]) > high) {
        return false;
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (x == n && y == n) return true;
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n &&
                grid[nx][ny] >= low && grid[nx][ny] <= high && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    return false;
}
int main() {
    cin >> n;
    int max_val = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> grid[i][j];
            max_val = max(max_val, grid[i][j]);
        }
    }
    int left = 0, right = 0;
    int ans = max_val;
    while (left <= max_val && right <= max_val) {
        if (can_reach(left, right) && right >= left) {
            ans = min(ans, right - left);
            left++;
        } else {
            right++;
        }
    }
    cout << ans << endl;
    return 0;
}

I: レーティング (考察+優先度付きキュー)

概要: n個の初期レートとm個のパフォーマンス値が与えられる。各試合でいずれかのレートを選び、(レート+パフォーマンス)/2に更新する。最終的な全レート合計の最大値を求めよ。

制約: n,m≤1e5

解法: 毎回最小レートを選択することで総和の減少を最小化。優先度付きキューで最小値を管理。

計算量: O((n+m) log n)

#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    priority_queue<double, vector<double>, greater<double>> pq;
    double sum = 0.0;
    for (int i = 0; i < n; ++i) {
        double x;
        cin >> x;
        pq.push(x);
        sum += x;
    }
    for (int i = 0; i < m; ++i) {
        double lowest = pq.top();
        pq.pop();
        double perf;
        cin >> perf;
        double updated = (lowest + perf) / 2.0;
        pq.push(updated);
        sum = sum - lowest + updated;
        cout << fixed << setprecision(2) << sum << endl;
    }
    return 0;
}

J: 文字列変換 (総当り)

概要: 長さnの文字列について、奇数インデックスではs_i + i、偶数インデックスではs_i - i に変換する。加算・減算は巡回的(a+1=b, z+1=a)。

制約: 1≤n≤1e5

解法: 各文字について基数0-25に変換し、インデックスに応じて加減算後、mod 26で元の文字に戻す。

計算量: O(n)

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    s = " " + s;
    for (int i = 1; i <= n; ++i) {
        int base = s[i] - 'a';
        if (i % 2 == 1) {
            base = (base + i) % 26;
        } else {
            base = (base - i % 26 + 26) % 26;
        }
        cout << char('a' + base);
    }
    cout << endl;
    return 0;
}

K: 新ゲーム! (計算幾何学+最短経路)

概要: 2本の平行直線とn個の円が与えられる。直線上または円内の移動は無料、それ以外はユークリッド距離の体力を消費する。直線間の最小消費体力を求めよ。

制約: 1≤n≤1000, |座標|≤10000

解法: 直線と円をノードとし、ノード間距離を計算してグラフを構築。ダイクストラ法で最短経路を求める。

計算量: O(n^2)

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
    int n;
    double A, B, C1, C2;
    cin >> n >> A >> B >> C1 >> C2;
    vector<double> dist(n+2, 1e12);
    vector<double> cx(n+1), cy(n+1), cr(n+1);
    vector<vector<double>> adj(n+2, vector<double>(n+2, 0.0));
    adj[0][n+1] = adj[n+1][0] = abs(C1 - C2) / hypot(A, B);
    for (int i = 1; i <= n; ++i) {
        cin >> cx[i] >> cy[i] >> cr[i];
        double denom = hypot(A, B);
        adj[0][i] = adj[i][0] = max(0.0, abs(A*cx[i] + B*cy[i] + C1)/denom - cr[i]);
        adj[i][n+1] = adj[n+1][i] = max(0.0, abs(A*cx[i] + B*cy[i] + C2)/denom - cr[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) continue;
            double dx = cx[i] - cx[j];
            double dy = cy[i] - cy[j];
            adj[i][j] = max(0.0, hypot(dx, dy) - cr[i] - cr[j]);
        }
    }
    dist[0] = 0.0;
    vector<bool> finalized(n+2, false);
    for (int iter = 0; iter <= n+1; ++iter) {
        int u = -1;
        double min_d = 1e12;
        for (int v = 0; v <= n+1; ++v) {
            if (!finalized[v] && dist[v] < min_d) {
                min_d = dist[v];
                u = v;
            }
        }
        if (u == -1) break;
        finalized[u] = true;
        for (int v = 0; v <= n+1; ++v) {
            if (!finalized[v]) {
                dist[v] = min(dist[v], dist[u] + adj[u][v]);
            }
        }
    }
    cout << dist[n+1] << endl;
    return 0;
}