AtCoder が提供しているABC（AtCoder Beginner Contest）271 のF問題をC++で解いてみました。ABC271は、2022年10月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 XOR on Grid Path（Difficulty : 1669）
問題はリンク先をご覧ください。
正方形を対角線の左上と右下に分けて XOR を計算します。その結果を組み合わせて解を求めます。AtCoder Problems による Difficulty は、1699 でした。
解答案
制約は、$0 \leqq N \leqq 20$ です。すべての経路は、$_{40}C_{20} \doteqdot 1.3 \times 10^{11}$ 通りとなります。計算量的には、すべての経路を計算する時間はありません。
左上から出発して、右上から左下の対角線までの経路の数は、$2^{20} \doteqdot 10^6$ 通りとなります。同じ対角線から右下までの経路も同じで約 $10^6$ 通りあります。
その経路を合わせることで XOR が0となる組み合わせの数を求めることができます。
C++ プログラム例（ABC271F）
配列 sum1[i] は、左上を始点として、右上をインデックス0とする対角線にあるマスまでのXORの値とその個数を格納します（17ー40行目）。
配列 sum2[i] は、右下を始点として、右上をインデックス0とする対角線にあるマスまでのXORの値とその個数を格納します（42ー65行目）。
求めた sum1 と sum2 を合わせると、0になる組み合わせの個数が分かります（67ー73行目）。ただし、対角線の値が2回XORされているため、この値で一度XORする必要があります（70行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<vector<unsigned>> a(n, vector<unsigned>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> a[i][j];
}
}
vector<map<unsigned, ll>> sum1(n);
for (int i = 0; i < n; ++i) {
vector<int> p;
for (int j = 0; j < n - 1 - i; ++j) {
p.push_back(0);
}
for (int j = n - 1 - i; j < n - 1; ++j) {
p.push_back(1);
}
do {
unsigned t = a[0][0];
int index_j = 0;
int index_i = 0;
for (int j = 0; j < p.size(); ++j) {
if (p[j] == 0) {
++index_j;
} else {
++index_i;
}
t ^= a[index_i][index_j];
}
++sum1[i][t];
} while (next_permutation(p.begin(), p.end()));
}
vector<map<unsigned, ll>> sum2(n);
for (int i = 0; i < n; ++i) {
vector<int> p;
for (int j = 0; j < n - 1 - i; ++j) {
p.push_back(0);
}
for (int j = n - 1 - i; j < n - 1; ++j) {
p.push_back(1);
}
do {
unsigned t = a[n - 1][n - 1];
int index_i = n - 1;
int index_j = n - 1;
for (int j = 0; j < p.size(); ++j) {
if (p[j] == 0) {
--index_i;
} else {
--index_j;
}
t ^= a[index_i][index_j];
}
++sum2[i][t];
} while (next_permutation(p.begin(), p.end()));
}
ll result = 0;
for (int i = 0; i < n; ++i) {
for (auto e : sum1[i]) {
unsigned t = e.first ^ a[i][n - 1 - i];
result += e.second * sum2[i][t];
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
今回は、Python プログラムの紹介を省略します。
最後に
半分全列挙と呼ばれる手法です。実装は長くなりましたが、基本的な考え方は理解しやすい問題でした。
引き続き ABC の問題を紹介していきます。
