7月は主に学校の夏期個人戦に参加し、その他の時間は主に学習やゲームに費やした。

上海大学プログラミングコンテスト 2024

上海地区のコンテストで、結果は芳しくなかった。主に実力不足が原因。

問題E - 無線ソフトウェア日

文字の出現頻度をカウントし、必要な文字数の最小値を求める問題。

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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int count[256] = {0};
    
    for (int i = 0; i < n; i++) {
        count[tolower(s[i])]++;
    }
    
    int result = 1e9;
    result = min(result, count['s']);
    result = min(result, count['h'] / 2);
    result = min(result, count['a'] / 2);
    result = min(result, count['n']);
    result = min(result, count['g']);
    result = min(result, count['i']);
    
    cout << result << endl;
    return 0;
}

問題J - 最小合成数列

合成数の判定と区間和を用いた最短部分列の探索を行う。

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

const int MAX_N = 1050;
long long prefix_sum[MAX_N];
int arr[MAX_N];

bool is_composite(long long x) {
    if (x < 4) return false;
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) return true;
    }
    return false;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        prefix_sum[i] = prefix_sum[i-1] + arr[i];
    }
    
    int min_length = 1e9;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (is_composite(prefix_sum[j] - prefix_sum[i-1])) {
                min_length = min(min_length, j - i + 1);
            }
        }
    }
    
    if (min_length == 1e9) {
        cout << -1 << endl;
    } else {
        cout << min_length << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

問題A - 無線ネットワーク格子点統計

正方形の頂点を基準に他の頂点を計算し、範囲内にあるかを判定する幾何問題。

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

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            int count = 0;
            for (int x = 0; x <= n; x++) {
                for (int y = 0; y <= m; y++) {
                    if (x == i && y == j) continue;
                    
                    // 正方形の他の2点を計算
                    int p1 = x - (j - y);
                    int q1 = y + (i - x);
                    int p2 = i - (j - y);
                    int q2 = j + (i - x);
                    
                    int valid_count = 0;
                    if (p1 >= 0 && p1 <= n && q1 >= 0 && q1 <= m) valid_count++;
                    if (p2 >= 0 && p2 <= n && q2 >= 0 && q2 <= m) valid_count++;
                    
                    if (valid_count == 2) count++;
                    
                    // 反対側の正方形
                    p1 = x + (j - y);
                    q1 = y - (i - x);
                    p2 = i + (j - y);
                    q2 = j - (i - x);
                    
                    valid_count = 0;
                    if (p1 >= 0 && p1 <= n && q1 >= 0 && q1 <= m) valid_count++;
                    if (p2 >= 0 && p2 <= n && q2 >= 0 && q2 <= m) valid_count++;
                    
                    if (valid_count == 2) count++;
                }
            }
            printf("%d ", count / 2);
        }
        printf("\n");
    }
    return 0;
}

江西省プログラミングコンテスト 2024

チームでの参加で銅賞を獲得。二人チームでの結果としては良い成績。

問題A - マリアンの絵画学習

基本的な入力処理問題。

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

int main() {
    long long a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c << endl;
    return 0;
}

問題C - 嘘つき

貪欲法を用いた問題。総和が目標値と一致する場合の判定が必要。

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

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> values(n);
    int sum = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> values[i];
        sum += values[i];
    }
    
    if (sum == target) {
        cout << n << endl;
    } else {
        cout << n - 1 << endl;
    }
    return 0;
}

問題K - 魔法の木

指数関数的な増加パターンを持つ問題。繰り返し二乗法を適用。

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

long long power(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

int main() {
    long long n;
    cin >> n;
    cout << power(2, n - 1) << endl;
    return 0;
}

問題G - 5の倍数

大きな数の処理において、桁ごとの計算を行う必要がある。

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

int main() {
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        int n;
        cin >> n;
        long long sum = 0;
        
        for (int i = 0; i < n; i++) {
            char digit_char, count_char;
            cin >> digit_char >> count_char;
            int count = count_char - '0';
            if (count_char == 'A') count = 10;
            
            sum += (digit_char - '0') * count;
            sum %= 10;
        }
        
        if (sum % 5 == 0) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

問題H - 畳み込み

二次元配列に対する畳み込み演算。効率的な計算のために二次元累積和を使用。

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

const int MAX_SIZE = 1050;
long long matrix[MAX_SIZE][MAX_SIZE];
long long prefix_sum[MAX_SIZE][MAX_SIZE];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int rows, cols, kernel_rows, kernel_cols;
    cin >> rows >> cols >> kernel_rows >> kernel_cols;
    
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            cin >> matrix[i][j];
            prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j-1] 
                             - prefix_sum[i-1][j-1] + matrix[i][j];
        }
    }
    
    int result_rows = rows - kernel_rows + 1;
    int result_cols = cols - kernel_cols + 1;
    long long total = 0;
    
    for (int i = 0; i < result_rows; i++) {
        for (int j = 0; j < result_cols; j++) {
            int x1 = i + 1, y1 = j + 1;
            int x2 = i + kernel_rows, y2 = j + kernel_cols;
            
            long long region_sum = prefix_sum[x2][y2] - prefix_sum[x1-1][y2] 
                                 - prefix_sum[x2][y1-1] + prefix_sum[x1-1][y1-1];
            total += abs(region_sum);
        }
    }
    
    cout << total << endl;
    return 0;
}

牛客練習賽127

難易度が予想以上で苦戦したコンテスト。

問題A - 小紅の最大価値

ソート後の要素の比較により最大値を求める。

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

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> arr(n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    sort(arr.begin(), arr.end());
    
    if (arr[0] + k >= arr[n-1]) {
        printf("%d\n", arr[n-2]);
    } else {
        printf("%d\n", arr[n-1]);
    }
    return 0;
}

AtCoder Beginner Contest 361

いくつかの問題で苦戦したが、最終的にレートは安定して上昇。

問題A - 挿入

指定された位置に要素を挿入するシミュレーション問題。

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

int main() {
    int n, pos, value;
    cin >> n >> pos >> value;
    vector<int> arr(n + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    for (int i = 1; i <= n; i++) {
        cout << arr[i] << " ";
        if (i == pos) {
            cout << value << " ";
        }
    }
    cout << "\n";
    return 0;
}

問題C - 狭くする

ソート後にスライディングウィンドウ法で最小差を求める。

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

int main() {
    int n, keep_count;
    cin >> n >> keep_count;
    int remove_count = n - keep_count;
    vector<int> arr(n);
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    sort(arr.begin(), arr.end());
    
    int min_diff = 1e9;
    for (int i = 0; i + remove_count - 1 < n; i++) {
        min_diff = min(min_diff, arr[i + remove_count - 1] - arr[i]);
    }
    
    cout << min_diff << endl;
    return 0;
}

問題B - 直方体の交差

三次元空間における直方体の交差判定。

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

int main() {
    int x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4;
    cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2 >> x3 >> y3 >> z3 >> x4 >> y4 >> z4;
    
    int overlap_count = 0;
    
    if ((x1 <= x3 && x3 < x2) || (x3 <= x1 && x1 < x4)) overlap_count++;
    if ((y1 <= y3 && y3 < y2) || (y3 <= y1 && y1 < y4)) overlap_count++;
    if ((z1 <= z3 && z3 < z2) || (z3 <= z1 && z1 < z4)) overlap_count++;
    
    if (overlap_count == 3) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;
}

Codeforces Round #956 (Div. 2)

レート向上に貢献したコンテスト。

問題A - 配列の割り算可能性

条件を満たす配列の構築問題。

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

int main() {
    int test_cases;
    scanf("%d", &test_cases);
    
    while (test_cases--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            printf("%d ", i);
        }
        printf("\n");
    }
    return 0;
}

問題C - ケーキを食べる

三つの配列について、それぞれの部分和が条件を満たすかどうかを二分探索で判定。

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

const int MAX_N = 200010;
long long a[MAX_N], b[MAX_N], c[MAX_N];
long long prefix_a[MAX_N], prefix_b[MAX_N], prefix_c[MAX_N];

void solve() {
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        prefix_a[i] = prefix_a[i-1] + a[i];
    }
    
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
        prefix_b[i] = prefix_b[i-1] + b[i];
    }
    
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &c[i]);
        prefix_c[i] = prefix_c[i-1] + c[i];
    }
    
    long long total = prefix_a[n];
    long long threshold = (total + 2) / 3;
    
    // 各種パターンのチェック
    for (int pattern = 0; pattern < 6; pattern++) {
        int start_a, end_a, start_b, end_b, start_c, end_c;
        
        switch (pattern) {
            case 0:
                start_a = 1;
                end_a = lower_bound(prefix_a + 1, prefix_a + n + 1, threshold) - prefix_a;
                start_b = end_a + 1;
                long long target_b = prefix_b[end_a] + threshold;
                end_b = lower_bound(prefix_b + 1, prefix_b + n + 1, target_b) - prefix_b;
                start_c = end_b + 1;
                end_c = n;
                break;
            // 他のパターンも同様に実装...
        }
        
        if (end_a <= n && end_b <= n && end_c <= n &&
            prefix_a[end_a] - prefix_a[start_a-1] >= threshold &&
            prefix_b[end_b] - prefix_b[start_b-1] >= threshold &&
            prefix_c[end_c] - prefix_c[start_c-1] >= threshold) {
            printf("%d %d %d %d %d %d\n", start_a, end_a, start_b, end_b, start_c, end_c);
            return;
        }
    }
    
    printf("-1\n");
}

int main() {
    prefix_a[0] = prefix_b[0] = prefix_c[0] = 0;
    int test_cases = 1;
    scanf("%d", &test_cases);
    
    while (test_cases--) {
        solve();
    }
    return 0;
}

問題B - コーナーのねじれ

各行・各列の和の剰余が一致することを確認する問題。

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

const int MAX_SIZE = 510;
char matrix_a[MAX_SIZE][MAX_SIZE], matrix_b[MAX_SIZE][MAX_SIZE];

int main() {
    int test_cases;
    scanf("%d", &test_cases);
    
    while (test_cases--) {
        int rows, cols;
        scanf("%d%d", &rows, &cols);
        
        for (int i = 0; i < rows; i++) {
            scanf("%s", matrix_a[i]);
        }
        
        for (int i = 0; i < rows; i++) {
            scanf("%s", matrix_b[i]);
        }
        
        bool valid = true;
        
        // 行のチェック
        for (int i = 0; i < rows; i++) {
            int sum_a = 0, sum_b = 0;
            for (int j = 0; j < cols; j++) {
                sum_a += matrix_a[i][j] - '0';
                sum_b += matrix_b[i][j] - '0';
            }
            if (sum_a % 3 != sum_b % 3) {
                valid = false;
                break;
            }
        }
        
        if (!valid) {
            printf("No\n");
            continue;
        }
        
        // 列のチェック
        for (int j = 0; j < cols; j++) {
            int sum_a = 0, sum_b = 0;
            for (int i = 0; i < rows; i++) {
                sum_a += matrix_a[i][j] - '0';
                sum_b += matrix_b[i][j] - '0';
            }
            if (sum_a % 3 != sum_b % 3) {
                valid = false;
                break;
            }
        }
        
        if (valid) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

7月上旬のコンテストは以上で終了。下旬は主に牛客の多校合同コンテストに注力する予定。