円周率日チャレンジ

Pythonの高精度計算を活用する問題。浮動小数点数の精度問題を回避するため、整数演算で処理する。

n = int(input())
pi_value = 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
results = []
for _ in range(n):
    numerator, denominator = map(int, input().split())
    approx = numerator * (10**100) // denominator
    difference = abs(approx - pi_value)
    results.append((difference, numerator, denominator))
results.sort()
print(results[0][1], results[0][2])

正規表現検証

IPv4アドレスの形式検証を行う。各オクテットが0-255の範囲内であることを確認する。

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

int main() {
    int count;
    cin >> count;
    int valid = 0;
    
    for (int i = 0; i < count; i++) {
        int octets[4];
        char delimiter;
        cin >> octets[0] >> delimiter >> octets[1] >> delimiter >> octets[2] >> delimiter >> octets[3];
        
        bool isValid = true;
        for (int j = 0; j < 4; j++) {
            if (octets[j] > 255) {
                isValid = false;
                break;
            }
        }
        valid += isValid;
    }
    
    cout << valid << endl;
    return 0;
}

円分割問題

円上の点を結ぶ直線によって分割される領域の数を求める数学的問題。

\[f(n)=\begin{cases} (n-1)^2+n+1 & \text{if } n > 0 \\ 1 & \text{if } n = 0 \end{cases}\]

#include <iostream>
using namespace std;

int main() {
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        long long n;
        cin >> n;
        
        if (n == 0) {
            cout << 1 << " ";
        } else {
            long long result = (n - 1) * (n - 1) + n + 1;
            cout << result << " ";
        }
    }
    
    return 0;
}

連鎖消去ゲーム

配列内の連続する同一値のブロック数をカウントする問題。

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

int main() {
    int n;
    cin >> n;
    vector<int> sequence(n);
    
    for (int i = 0; i < n; i++) {
        cin >> sequence[i];
    }
    
    int blocks = 0;
    for (int i = 0; i < n; i++) {
        if (sequence[i] != sequence[i-1] && sequence[i] != 0) {
            blocks++;
        }
    }
    
    cout << blocks << endl;
    return 0;
}

区間クエリ処理

セグメント木を用いた区間内の連続する1の最大長を求める問題。

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

#define leftChild(idx) (idx << 1)
#define rightChild(idx) (idx << 1 | 1)

struct SegmentNode {
    int leftOnes, rightOnes, maxOnes;
    int leftZeros, rightZeros, maxZeros;
    int totalOnes, totalZeros;
};

class SegmentTree {
    // セグメント木の実装
};

int main() {
    int n, queries;
    cin >> n >> queries;
    
    SegmentTree tree(n);
    
    while (queries--) {
        int operation;
        cin >> operation;
        
        if (operation == 1) {
            int position;
            cin >> position;
            tree.flip(position);
        } else {
            int start, end;
            cin >> start >> end;
            cout << tree.queryMaxOnes(start, end) << endl;
        }
    }
    
    return 0;
}