文字列連結

2つの文字列を入力として受け取り、連結して出力します。空白を含む可能性があるため、getline関数を使用します。

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

int main() {
    string a, b;
    getline(cin, a);
    getline(cin, b);
    cout << a + b;
    return 0;
}

最小差分値

整数配列内の隣接要素間の最小差分値を求めます。配列をソート後、隣接要素間の差を計算します。

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

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr.begin(), arr.end());
    int minDiff = INT_MAX;
    for (int i = 1; i < n; i++) {
        minDiff = min(minDiff, arr[i] - arr[i-1]);
    }
    cout << minDiff;
}

グリッド色分けゲーム

n×mグリッドの色分けゲームで、両次元が奇数の場合に先手が勝利します。中心セル戦略により決定されます。

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    if (n % 2 && m % 2) cout << "akai";
    else cout << "yukari";
    return 0;
}

abb部分列カウント

文字列内のabb形式（例: "abb"）の部分列をカウントします。各位置の後に出現する文字の頻度を記録し、組合せ計算を行います。

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

int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<vector<long>> freq(n+1, vector<long>(26));
    for (int i = n-1; i >= 0; i--) {
        freq[i] = freq[i+1];
        freq[i][s[i]-'a']++;
    }
    long result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) {
            if (j == s[i]-'a') continue;
            long count = freq[i+1][j];
            result += count * (count - 1) / 2;
        }
    }
    cout << result;
}

素因数選択最小和

各数値から一意の素因数を選択し、和の最小値を求めます。深さ優先探索で全ての組合せを探索します。

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

const int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
vector<vector<int>> factors;
vector<bool> used(25, false);
int minSum = INT_MAX;

void dfs(int idx, int currSum, int total) {
    if (idx == total) {
        minSum = min(minSum, currSum);
        return;
    }
    for (int f : factors[idx]) {
        if (used[f]) continue;
        used[f] = true;
        dfs(idx+1, currSum + primes[f], total);
        used[f] = false;
    }
}

int main() {
    int n;
    cin >> n;
    factors.resize(n);
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        for (int j = 0; j < 25; j++) {
            if (num % primes[j] != 0) continue;
            factors[i].push_back(j);
            while (num % primes[j] == 0) num /= primes[j];
        }
    }
    dfs(0, 0, n);
    cout << (minSum == INT_MAX ? -1 : minSum);
}

二分木色分け問題

木構造のノードを赤/青で塗り分け、隣接ノードが異なる色になるよう割り当てます。葉ノードから親子ペアを決定します。

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

vector<vector<int>> graph;
vector<int> color;
vector<int> groupId;
int groupCount = 0;
bool valid = true;

void buildPairs(int node, int parent) {
    int children = 0;
    for (int child : graph[node]) {
        if (child == parent) continue;
        children++;
        buildPairs(child, node);
    }
    if (children == 0 || groupId[node] == 0) {
        if (groupId[parent] != 0) valid = false;
        groupId[node] = groupId[parent] = ++groupCount;
    }
}

void assignColors(int node, int parent) {
    for (int child : graph[node]) {
        if (child == parent) continue;
        if (groupId[child] == groupId[node]) color[child] = color[node];
        else color[child] = !color[node];
        assignColors(child, node);
    }
}

int main() {
    int n;
    cin >> n;
    graph.resize(n+1);
    color.resize(n+1);
    groupId.resize(n+1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    buildPairs(1, 0);
    if (!valid || groupId[0] != 0) {
        cout << -1;
        return 0;
    }
    color[1] = 1;
    assignColors(1, 0);
    for (int i = 1; i <= n; i++) 
        cout << (color[i] ? 'R' : 'B');
}