Codeforces Edu Contest 161 解法と分析

問題A: 文字列照合判定

この問題では、文字列cの各文字が対応する位置の文字列aまたは文字列bのいずれかと一致するかを判定する必要があります。すべての文字が一致する場合は"NO"、そうでない場合は"YES"を出力します。


#include 
#include 
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        int length;
        cin >> length;
        string str_a, str_b, str_c;
        cin >> str_a >> str_b >> str_c;
        
        bool mismatch_found = false;
        
        for (int i = 0; i < length; i++) {
            if (str_c[i] != str_a[i] && str_c[i] != str_b[i]) {
                mismatch_found = true;
                break;
            }
        }
        
        cout << (mismatch_found ? "YES" : "NO") << "\n";
    }
    
    return 0;
}

問題B: 三角形の組み合わせ数

この問題では、棒から三角形を作る場合の組み合わせ数を計算します。考えられるケースは2つです：

3本の同じ長さの棒（長さmの棒が3本以上ある場合、C(m,3)の組み合わせが可能）
2本の同じ長さの棒と、それより短い任意の長さの棒1本

組み合わせ数を計算する際には、各長さの棒の出現頻度をカウントし、組み合わせの公式を適用します。


#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;

LL combination(LL n, LL k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;
    
    LL result = 1;
    for (LL i = 1; i <= k; i++) {
        result = result * (n - k + i) / i;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        int stick_count;
        cin >> stick_count;
        
        vector sticks(stick_count);
        map frequency;
        
        for (int i = 0; i < stick_count; i++) {
            cin >> sticks[i];
            frequency[sticks[i]]++;
        }
        
        sort(sticks.begin(), sticks.end());
        
        LL total_triangles = 0;
        LL accumulated_sticks = 0;
        
        for (auto& pair : frequency) {
            int count = pair.second;
            
            // 3本同じ長さの棒で三角形を作る場合
            if (count >= 3) {
                total_triangles += combination(count, 3);
            }
            
            // 2本同じ長さの棒と1本短い棒で三角形を作る場合
            total_triangles += accumulated_sticks * combination(count, 2);
            
            accumulated_sticks += count;
        }
        
        cout << total_triangles << "\n";
    }
    
    return 0;
}

問題C: 最寄り都市と累積コスト

この問題では、各地点の最寄り都市を特定し、前缀和と后缀和を利用して2地点間の移動コストを計算します。マップを使用して各地点に対応する最寄り都市を保存し、クエリに応じて効率的にコストを計算します。


#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;

const int MAX_N = 1000000;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        int city_count;
        cin >> city_count;
        
        vector city_values(city_count + 1);
        vector prefix_cost(city_count + 1, 0);
        vector suffix_cost(city_count + 1, 0);
        map nearest_city;
        
        for (int i = 1; i <= city_count; i++) {
            cin >> city_values[i];
        }
        
        // 各都市の最寄り都市を特定
        for (int i = 1; i <= city_count; i++) {
            if (i == 1) {
                nearest_city[city_values[i]] = i + 1;
            } else if (i == city_count) {
                nearest_city[city_values[i]] = i - 1;
            } else {
                if (abs(city_values[i] - city_values[i-1]) > abs(city_values[i] - city_values[i+1])) {
                    nearest_city[city_values[i]] = i + 1;
                } else {
                    nearest_city[city_values[i]] = i - 1;
                }
            }
        }
        
        // 前缀和の計算
        for (int i = 2; i <= city_count; i++) {
            if (nearest_city[city_values[i-1]] == i) {
                prefix_cost[i] = prefix_cost[i-1] + 1;
            } else {
                prefix_cost[i] = prefix_cost[i-1] + abs(city_values[i] - city_values[i-1]);
            }
        }
        
        // 后缀和の計算
        for (int i = city_count - 1; i >= 1; i--) {
            if (nearest_city[city_values[i+1]] == i) {
                suffix_cost[i] = suffix_cost[i+1] + 1;
            } else {
                suffix_cost[i] = suffix_cost[i+1] + abs(city_values[i] - city_values[i+1]);
            }
        }
        
        int query_count;
        cin >> query_count;
        
        while (query_count--) {
            int start, end;
            cin >> start >> end;
            
            if (end > start) {
                cout << prefix_cost[end] - prefix_cost[start] << "\n";
            } else {
                cout << suffix_cost[end] - suffix_cost[start] << "\n";
            }
        }
    }
    
    return 0;
}

タグ: codeforces アルゴリズム文字列処理組み合わせ数学累積和

7月7日 20:03 投稿

異端開発室

Codeforces Edu Contest 161 解法と分析

問題A: 文字列照合判定

問題B: 三角形の組み合わせ数

問題C: 最寄り都市と累積コスト

ホットタグ