問題1: 数字の出現回数のカウント
与えられた区間 $[L, R]$ 内のすべての整数について、数字「2」が合計で何回現れるかを求める問題です。
输入例:
2 22
出力例:
6
解法:
各区間内の整数を1つずつ走査し、各数字を10進数桁ごとに分解して「2」の出現回数をカウントします。
#include <iostream>
using namespace std;
int main() {
int left, right;
cin >> left >> right;
int totalCount = 0;
for (int num = left; num <= right; ++num) {
int temp = num;
while (temp > 0) {
if (temp % 10 == 2) {
++totalCount;
}
temp /= 10;
}
}
cout << totalCount << endl;
return 0;
}
問題2: 接水問題
m 個の水道栓と n 人の学生がおり、各学生の必要な水量が与えられます。水は1秒あたり1ユニットずつ供給され、順番に次の学生が接管します。全員がWaterを終えるまでにかかる最小時間を求めます。
入力例:
5 3
4 4 1 2 1
出力例:
4
解法:
各水道栓の Finish Time を管理し、常に最も早く空く栓に次の学生を割り当てていく貪欲法が適しています。優先度付きキュー（最小ヒープ）を用いることで効率的に実装できます。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int totalPeople, taps;
cin >> totalPeople >> taps;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < taps; ++i) {
int w;
cin >> w;
pq.push(w);
}
for (int i = taps; i < totalPeople; ++i) {
int w;
cin >> w;
int earliestFinish = pq.top(); pq.pop();
pq.push(earliestFinish + w);
}
int maxTime = 0;
while (!pq.empty()) {
maxTime = max(maxTime, pq.top());
pq.pop();
}
cout << maxTime << endl;
return 0;
}
問題3: 弾幕回避（2系統官僚）
2つの防御システムがあり、それぞれ座標 $(x_1, y_1)$ と $(x_2, y_2)$ に設置されています。
各ミサイル $(x_i, y_i)$ をいずれかのシステムで迎撃する際、 workload（コスト）＝各システムのランチ半径の2乗和が最小となるような配分を求めます。
入力例:
0 0 10 0
2
-3 3
10 0
出力例:
18
解法:
各ミサイルについて、2つのシステムからの距離の2乗をあらかじめ計算しておきます。その後、片方のシステムがカバーするミサイルを決めて（たとえば距離順でソートし)i番目までをA、残りをBと仮定して、その場合の最大値+補助系の最大距離の2乗の組み合わせを全探索し、最小値を求めます。
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
struct Missile {
long long distA, distB;
};
bool cmpA(const Missile& a, const Missile& b) {
return a.distA < b.distA;
}
int main() {
long long x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int N;
cin >> N;
vector<Missile> missiles(N + 2);
for (int i = 1; i <= N; ++i) {
long long x, y;
cin >> x >> y;
missiles[i].distA = (x - x1) * (x - x1) + (y - y1) * (y - y1);
missiles[i].distB = (x - x2) * (x - x2) + (y - y2) * (y - y2);
}
sort(missiles.begin() + 1, missiles.begin() + 1 + N, cmpA);
long long minCost = LLONG_MAX;
long long maxB = 0;
for (int i = N; i >= 0; --i) {
maxB = max(maxB, missiles[i + 1].distB);
long long cost = missiles[i].distA + maxB;
minCost = min(minCost, cost);
}
cout << minCost << endl;
return 0;
}
問題4: 三国志ゲーム
偶数 $N$ 人の武将が存在し、任意2人の武将間に「默契値」（隠し値）があります。
プレイヤー「小涵」とコンピュータが交互に武将を選択します。ただし、コンピュータの選択戦略は「小涵の次回の最強ペアを壊すために最適な自由武将を選ぶ」とします。
小涵が勝てる場合、その中で可能な高い默契値のペアを求める問題です。
入力例:
6
5 28 16 29 27
23 3 20 1
8 32 26
33 11
12
出力例:
1
32
解法:
コンピュータの戦略を模倣しながら全探索するのは計算量的に困難です。しかし、注目すべきは「最終的に選ばれる8人のうち、最高のペアが必ず存在する」という洞察です。すべての武将毎に、自分とペアになった場合の最大・次大となる默契値をソートして求めておき、各武将に対して「自分が選ばれた場合に最も強く成立しそうなペアの第2候補（最大の次）」のうち最も大きいものを答えとします。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<long long>> memo(n + 1, vector<long long>(n + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
cin >> memo[i][j];
memo[j][i] = memo[i][j];
}
}
long long bestSecondPair = 0;
for (int i = 1; i <= n; ++i) {
vector<long long> vals;
for (int j = 1; j <= n; ++j) {
if (i != j) vals.push_back(memo[i][j]);
}
sort(vals.rbegin(), vals.rend());
if (vals.size() >= 2) {
bestSecondPair = max(bestSecondPair, vals[1]);
}
}
cout << 1 << "\n" << bestSecondPair << endl;
return 0;
}