問題1：文字列処理 - 文字と数字の間に空白を挿入
文書内の隣接する英字と数字の間に空白を追加する問題である。文書の最初と最後の文字は空白ではないことが保証されている。
getlineを用いて1行全体を読み込み、文字を順に走査しながら条件に合わせて空白を挿入する。
実装コード
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
int main() {
string input;
getline(cin, input);
cout << input[0];
for (size_t idx = 1; idx < input.length(); idx++) {
bool prevIsDigit = isdigit(input[idx-1]);
bool currIsDigit = isdigit(input[idx]);
if ((prevIsDigit && !currIsDigit && input[idx] != ' ') ||
(!prevIsDigit && currIsDigit && input[idx-1] != ' ')) {
cout << ' ';
}
cout << input[idx];
}
return 0;
}
問題2：ゲーム理論 - AliceとBobの最適戦略
n個の整数が黒板に書かれている。Aliceは先手で、自分のターンに1個以上の整数を消す。Bobは自分のターンに1個の整数を消す。Aliceは選んだ数の和を最大化、Bobは最小化を目指す。双方が最適な戦略をとるときのスコアを求める。
配列をソートし、正負の分布に基づいて戦略を決定する：
- 全て正数の場合：Aliceが全てを取る
- 全て負数の場合：個数の偶奇に依存。奇数なら最初の2個、偶数なら最初の1個を取る
- 正負混在の場合：正数を全て取り、負数の個数の偶奇に応じて追加で負数を取るか決定
問題3：データ構造 - 連続する区間の平均値が整数となる個数
n人の学生のテスト得点が与えられる。連続する番号の学生を選ぶ全ての選び方のうち、選んだ学生の平均点が整数となるものの個数を求める。
平均値をtとすると、区間[l, r]の和からt×(r-l+1)を引いたものが0になればよい。前項の条件は、各要素からtを引いた配列の前項和において、等しい値を持つ2つの位置を探すことに帰着する。
可能な平均値の範囲（配列の最小値から最大値）を列挙し、ハッシュテーブルを用いて条件を満たす区間を効率的に数える。
実装コード
#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> scores(n);
int minScore = INT_MAX, maxScore = INT_MIN;
for (int i = 0; i < n; i++) {
cin >> scores[i];
minScore = min(minScore, scores[i]);
maxScore = max(maxScore, scores[i]);
}
long long answer = 0;
for (int target = minScore; target <= maxScore; target++) {
unordered_map<long long, int> counter;
long long prefixSum = 0;
counter[0] = 1;
for (int i = 0; i < n; i++) {
prefixSum += scores[i] - target;
answer += counter[prefixSum];
counter[prefixSum]++;
}
}
cout << answer << endl;
return 0;
}
問題4：グラフ理論 - 強連結成分の構築
n個の都市とm本の一方向道路を建設する。都市群は強連結成分として定義され、全都市をX個の強連結成分に分割する必要がある。また、q個の制約で指定された都市ペアは同じ強連結成分に属さなければならない。
解法：
「同一の強連結成分に属する」関係は同値関係であるため、Union-Findで制約を処理し、各等価類のサイズを求める。サイズを昇順にソートし、s₁, s₂, ..., sₖとする。
k < X の場合、解は存在しない。それ以外の場合、sₓ, sₓ₊₁, ..., sₖに対応する等価類を1つに統合する。
辺数の範囲：
- サイズpの強連結成分：内部にp本（最小）からp(p-1)本（最大）の辺を持つ
- 異なる強連結成分間：0本から|A|×|B|本の辺
これらの下界と上界を計算し、mが範囲内にあるかを確認する。範囲外なら解は存在しない。
構築方法：
- 同一強連結成分に含むべき頂点群は、サイクルを形成させることで強連結を保証
- 異なる強連結成分間では、成分番号の小さい方から大きい方へのみ辺を張ることで、新たな強連結成分の形成を防ぐ
時間計算量は適切な実装により線形時間で動作する。