円の面積計算

円の面積を計算する際にはπの精度に注意が必要である。以下のコードは入力値nを用いて円の面積を計算する。ここで円の半径はnに関係する（n*n*0.5をπで割る）。

#include<iostream>
#include<cmath>
using namespace std;

int main() {
    double input;
    cin >> input;
    double area = input * input * 0.5 / M_PI;
    printf("%.3f", area);
    return 0;
}

植林問題

植林の本数に応じて、奇数なら1、偶数なら2を出力する単純な条件分岐問題。

#include<iostream>
using namespace std;

int main() {
    int tree_count;
    cin >> tree_count;
    cout << (tree_count % 2 ? 1 : 2) << endl;
    return 0;
}

グループ能力差最大化

学生をkグループに分け、各グループの能力値最大と最小の差の合計を最大化する。ソート後に両端から選択する貪欲法。

#include<iostream>
#include<algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int abilities[n];
    for(int i=0; i<n; i++) cin >> abilities[i];
    
    sort(abilities, abilities+n);
    long total_diff = 0;
    for(int i=0; i<k; i++) {
        total_diff += abilities[n-1-i] - abilities[i];
    }
    cout << total_diff << endl;
    return 0;
}

分数演算

2つの分数に対して加算、減算、乗算、除算を実行し、約分した結果を出力する。

#include<iostream>
#include<algorithm>
using namespace std;

long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

void print_fraction(long num, long den) {
    long d = gcd(abs(num), den);
    cout << num/d << " " << den/d << endl;
}

int main() {
    long a_num, a_den, b_num, b_den;
    cin >> a_num >> a_den >> b_num >> b_den;
    
    // 加算
    print_fraction(a_num*b_den + b_num*a_den, a_den*b_den);
    // 減算
    long sub_num = a_num*b_den - b_num*a_den;
    if(sub_num == 0) cout << "0 0" << endl;
    else print_fraction(sub_num, a_den*b_den);
    // 乗算
    print_fraction(a_num*b_num, a_den*b_den);
    // 除算
    print_fraction(a_num*b_den, a_den*b_num);
    
    return 0;
}

グラフ接続問題

Union-Findデータ構造を用いて、特定の頂点を除外しながらグラフの環を検出し、削除すべき辺の数を計算する。

#include<iostream>
#include<vector>
using namespace std;

int find_root(int x, int parent[]) {
    if(parent[x] != x) parent[x] = find_root(parent[x], parent);
    return parent[x];
}

int main() {
    int vertices, edges, threshold;
    cin >> vertices >> edges >> threshold;
    
    int parent[vertices+1];
    for(int i=1; i<=vertices; i++) parent[i] = i;
    
    vector<pair<int,int>> edge_list;
    int removal_count = 0;
    
    for(int i=0; i<edges; i++) {
        int u, v;
        cin >> u >> v;
        edge_list.push_back({u,v});
        
        if(u > threshold && v > threshold) {
            int root_u = find_root(u, parent);
            int root_v = find_root(v, parent);
            if(root_u != root_v) parent[root_u] = root_v;
        }
    }
    
    for(auto edge : edge_list) {
        if(edge.first <= threshold || edge.second <= threshold) {
            int root_u = find_root(edge.first, parent);
            int root_v = find_root(edge.second, parent);
            if(root_u == root_v) removal_count++;
            else parent[root_u] = root_v;
        }
    }
    
    cout << removal_count << endl;
    return 0;
}

最長増加部分列

各要素の約数を利用して最長増加部分列の長さを求める動的計画法。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

const int MAX_VAL = 1000000;
int divisor_index[MAX_VAL+1] = {0};

int main() {
    int test_cases;
    cin >> test_cases;
    
    while(test_cases--) {
        int n;
        cin >> n;
        int sequence[n+1];
        int dp[n+1] = {0};
        memset(divisor_index, 0, sizeof(divisor_index));
        
        for(int i=1; i<=n; i++) cin >> sequence[i];
        sort(sequence+1, sequence+n+1);
        
        int max_length = 0;
        for(int i=1; i<=n; i++) {
            dp[i] = 1;
            int val = sequence[i];
            for(int j=1; j*j<=val; j++) {
                if(val % j != 0) continue;
                int factor1 = j;
                int factor2 = val / j;
                
                if(divisor_index[factor1]) 
                    dp[i] = max(dp[i], dp[divisor_index[factor1]] + 1);
                if(divisor_index[factor2]) 
                    dp[i] = max(dp[i], dp[divisor_index[factor2]] + 1);
            }
            
            for(int j=1; j*j<=val; j++) {
                if(val % j != 0) continue;
                divisor_index[j] = i;
                divisor_index[val/j] = i;
            }
            
            max_length = max(max_length, dp[i]);
        }
        
        cout << max_length << endl;
    }
    return 0;
}

文字編集処理

双方向編集コマンドに基づいて文字列を再構築する。左右の挿入操作を効率的に処理する。

#include<iostream>
#include<deque>
using namespace std;

int main() {
    string text, commands;
    cin >> text >> commands;
    
    deque<char> result;
    result.push_back(text[text.size()-1]);
    
    for(int i=text.size()-2; i>=0; i--) {
        if(commands[i] == 'L') {
            result.push_back(text[i]);
        } else {
            result.push_front(text[i]);
        }
    }
    
    for(char c : result) cout << c;
    return 0;
}