はじめに
本記事では、2023年中国大学コンピュータ大会-チームプログラミング天梯大会（GPLT）上海理工大学校内選手大会のA-D問題の解法を紹介します。大会では4問中2問を解き、その後残り2問を追加で解決しました。他の問題についても、一部は他の参加者のソースコードを参考に理解しました。
以下に解いた4つの問題の解法を記載します。
A問題: Xor B問題
問題文は長いですが、本質的には配列の要素を二重ループで走査し、a[i]とa[j]（i≠j）が等しい場合にカウントを増やすというものです。
しかし、データの範囲を考慮すると二重ループでは時間超過が発生すると判断したため、別のアプローチを考えました。各数字の出現回数を記録する配列を一つ用意し、各数字の出現回数の二乗の合計を計算する方法です。
（注意：データ範囲は10^5ではなく、少なくとも10^6以上である必要があります。これを満たさない場合はAC（正解）にならない可能性があります）
実装コード:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAX = 1000010;
int n, m;
vector<int> count_array(MAX, 0);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> m;
count_array[m]++;
}
long long result = 0;
for (int i = 0; i < MAX; i++) {
result += static_cast<long long>(count_array[i]) * count_array[i];
}
cout << result << endl;
return 0;
}
りんごを食べる
問題の意味は、小龍のn個のりんごを朝か夜に食べたときの愉悦値の合計を最大化することです。ただし、夜に食べられるのはk日までです。したがって、朝と夜の愉悦値の差（朝の愉悦値 - 夜の愉悦値）が小さいものをk日選び、残りは朝の愉悦値で計算します。
実装コード:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Apple {
int morning_value;
int evening_value;
int difference;
};
bool compare_apples(const Apple &a, const Apple &b) {
return a.difference < b.difference;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<Apple> apples(n);
for (int i = 0; i < n; i++) {
cin >> apples[i].morning_value >> apples[i].evening_value;
apples[i].difference = apples[i].morning_value - apples[i].evening_value;
}
sort(apples.begin(), apples.end(), compare_apples);
long long total_value = 0;
for (int i = 0; i < n; i++) {
if (i < k) {
total_value += apples[i].evening_value;
} else {
total_value += apples[i].morning_value;
}
}
cout << total_value << endl;
return 0;
}
=
N-Queen問題
この問題も理解しやすいです。Queenの移動経路（同じ行、同じ列、同じ対角線）をマークし、後から入力される位置が安全かどうかを判断します。
データ範囲が10^6のため、二次元配列は使用できません。ここでのコツは、座標軸上の対角線の差（x-y）と和（x+y）が一定であることを利用することです。Queenと同じ対角線上にあるかどうかを判定するために、これらの値をマークします。負の値になる場合は、大きな数（例えばn）を加えて扱いやすくします。
実装コード:
#include <iostream>
using namespace std;
const int MAX_SIZE = 10000010;
int n, test_cases;
int row_used[MAX_SIZE], col_used[MAX_SIZE];
int diag1_used[MAX_SIZE], diag2_used[MAX_SIZE];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> test_cases;
while (test_cases--) {
int x, y;
cin >> x >> y;
if (!row_used[x] && !col_used[y] &&
!diag1_used[x+y] && !diag2_used[x-y+n]) {
row_used[x] = 1;
col_used[y] = 1;
diag1_used[x+y] = 1;
diag2_used[x-y+n] = 1;
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}
りんごを分配する
4番目の問題ですが、最初の提出で正解できました。
問題の概要は、2本の棒を交差させ、その4つの領域にあるリンゴの数を小さい順に出力することです。
座標軸のように考え、2本の直線の方程式にリンゴの座標を代入して、4つの象限にあるリンゴの数をカウントし、小さい順に出力します。
実装コード:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int a1, b1, c1; // 1本目の直線: a1*x + b1*y + c1 = 0
int a2, b2, c2; // 2本目の直線: a2*x + b2*y + c2 = 0
cin >> a1 >> b1 >> c1;
cin >> a2 >> b2 >> c2;
vector<int> regions(4, 0);
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
int line1_result = a1 * x + b1 * y + c1;
int line2_result = a2 * x + b2 * y + c2;
if (line1_result > 0 && line2_result > 0) {
regions[0]++;
} else if (line1_result > 0 && line2_result < 0) {
regions[1]++;
} else if (line1_result < 0 && line2_result > 0) {
regions[2]++;
} else if (line1_result < 0 && line2_result < 0) {
regions[3]++;
}
}
sort(regions.begin(), regions.end());
for (int i = 0; i < 4; i++) {
cout << regions[i] << " ";
}
cout << endl;
return 0;
}
おわりに
今回の大会で学んだ技術的なポイントを共有します：
ios::sync_with_stdio(0) を使用してcinの効率を最適化する際は、scanfと混在させないでください。
この最適化を行うと、入力データの誤りや効率低下が発生する可能性があります。具体的な理由については、C++の入出力ストリームの仕組みを参照してください。