AtCoder が提供しているABC（AtCoder Beginner Contest）348 のF問題をC++で解いてみました。ABC348は、2024年4月6日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Oddly Similar（Difficulty : 1955）
問題はリンク先をご覧ください。
AtCoderの実行環境について考えてみます。AtCoder Problems による Difficulty は 1955 でした。
解答案
以下は、素直に実装したプログラムです。すべての行の組み合わせについて、一致している列の個数が奇数か調べています。難易度としてはB問題程度でしょうか。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
int result = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int same_col = 0;
for (int k = 0; k < m; ++k) {
if (a[i][k] == a[j][k]) {
++same_col;
}
}
if (same_col % 2 == 1) {
++result;
}
}
}
cout << result << endl;
return 0;
}このプログラムは、TLE（Time Limit Exceed）判定となります。まぁ、F問題がこの考えで解けるわけはありません。
計算量（ループ回数）を評価します。$1 \leqq N, M \leqq 2000$ です。すべての行の組み合わせは、$2000 \times 1999 / 2$ となり約 $2 \times 10^6$ 通りです。すべての列を調べますから、計算量は $4 \times 10^9$ となります。
計算の複雑さに依存しますが1秒で $10^8$ 回程度のループが処理できると概算されています。この問題の制限時間は2秒です。微妙に足りません。
公式解説では、bitset高速化という手法で定数倍（64分の1）高速に処理する方法を紹介しています。
この記事では、AtCoder の C++ の実行環境を工夫して解く方法を紹介します。えびまラボ様の動画を参考にしました。
C++ プログラム例（ABC348F）
最適化オプションの強化
わたしは、C++ 環境では、「C++ 20 (gcc 12.2)」を使っています。GCC では、pragma でコンパイルオプションが指定できます。最適化 O3 に指定するだけでAC判定となりました。差分は最初の行だけです。
参考までに AtCoder が採用している gcc の最適化オプションは、O2 が指定されていました（こちらをご覧ください）。
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
int result = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int same_col = 0;
for (int k = 0; k < m; ++k) {
if (a[i][k] == a[j][k]) {
++same_col;
}
}
if (same_col % 2 == 1) {
++result;
}
}
}
cout << result << endl;
return 0;
}整数の大きさを変える。
Vector コンテナの型を int（32ビット）から short（16ビット）にすると、少し速くなります。差分は以下です。
vector<vector<short>> a(n, vector<short>(m));入力の高速化
以下のおまじないを加えることによって、高速化できます。ただし、scanf/printf のような標準入力が使えなくなります。
cin.tie(nullptr);
ios::sync_with_stdio(false);それぞれのプログラムの実行時間は以下でした。
| 条件 | 実行時間（2回の平均） |
| (1) 対応無し | TLE（2200 msec 超え） |
| (2) O3 を指定する。 | 1000.5 msec |
| (3) (2)に加えて、shortを利用 | 742.5 msec |
| (4) (3)に加えて、入力の高速化 | 400.5 msec |
O3、short利用、入力の高速化でかなり速くなっていることが分かりました。最終版のプログラムは以下です。
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
int main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<vector<short>> a(n, vector<short>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
int result = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int same_col = 0;
for (int k = 0; k < m; ++k) {
if (a[i][k] == a[j][k]) {
++same_col;
}
}
if (same_col % 2 == 1) {
++result;
}
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
今回の解き方は、邪道かもしれません。ただし、gcc などの言語処理系について新しく学べることができました。
引き続き ABC の問題を紹介していきます。
