AtCoder が提供しているABC（AtCoder Beginner Contest）332 のD問題をC++とPythonで解いてみました。ABC332は、2023年12月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Swapping Puzzle（Difficulty : 1175）
問題はリンク先をご覧ください。
行と列について、順列全探索を行います。AtCoder Problems による Difficulty は 1175 でした。
解答案
最初に反転数の定義をします。
数列 $A = {a_0, a_1, \dots a_{n-1}}$ について、$a_i > a_j$ かつ $i < j$ である組 $(i, j)$ の個数を反転数と呼ぶ。
反転数については、ALDS1 5_D で計算方法を紹介しています。
反転数は、バブルソートの交換回数と等しくなります。このため、大きさ $n$ の任意の順列 $p = {p_0, p_1, \dots p_{n-1}}$ を ${1, 2, \dots, n}$ に変換するための、隣接する要素の交換回数に等しくなります。
行と列を入れ替えて行列 $A$ が行列 $B$ に等しくなれば、入れ替えた結果の行の順列と列の順列の反転数を求めることにより、隣接する行または列の交換回数を求めることができます。
C++ プログラム例（ABC332D）
行と列の順列全探索を2重ループで実装します。上記の説明と異なり配列の添え字は0からカウントしています。
- 前準備
- 行に使う順列 ph の準備（23ー26行目）
- 列に使う順列 pw の準備（27ー30行目）
- 順列全探索（33ー62行目）
- next_permutation を2重に使います。
- 行列Aを入れ替えてBに一致するか調べます（35ー42行目）。
- 行と列の反転数を調べて、その和の最小値を result に格納します（43行目のif文）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int h, w;
cin >> h >> w;
vector<vector<int>> a(h, vector<int>(w));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> a[i][j];
}
}
vector<vector<int>> b(h, vector<int>(w));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> b[i][j];
}
}
vector<int> ph(h);
for (int i = 0; i < h; ++i) {
ph[i] = i;
}
vector<int> pw(w);
for (int i = 0; i < w; ++i) {
pw[i] = i;
}
int result = INF;
do {
do {
bool t = true;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (b[i][j] != a[ph[i]][pw[j]]) {
t = false;
}
}
}
if (t) {
int rev = 0;
for (int i = 0; i < h; ++i) {
for (int j = i + 1; j < h; ++j) {
if (ph[i] > ph[j]) {
++rev;
}
}
}
for (int i = 0; i < w; ++i) {
for (int j = i + 1; j < w; ++j) {
if (pw[i] > pw[j]) {
++rev;
}
}
}
result = min(result, rev);
}
} while (next_permutation(pw.begin(), pw.end()));
} while (next_permutation(ph.begin(), ph.end()));
if (result == INF) {
result = -1;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC332D）
Python では、順列を itertools.permutations で生成します。基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 332 D"""
import itertools
INF = 1 << 30
h, w = map(int, input().split())
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
a[i] = list(map(int, input().split()))
b = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
b[i] = list(map(int, input().split()))
result = INF
for ph in list(itertools.permutations(list(range(h)))):
for pw in list(itertools.permutations(list(range(w)))):
t = True
for i in range(h):
for j in range(w):
if b[i][j] != a[ph[i]][pw[j]]:
t = False
if t:
rev = 0
for i in range(h):
for j in range(i + 1, h):
if ph[i] > ph[j]:
rev += 1
for i in range(w):
for j in range(i + 1, w):
if pw[i] > pw[j]:
rev += 1
result = min(result, rev)
if result == INF:
result = -1
print(result)こちらも「AC」と判定されました。
最後に
反転数について知識があれば解ける問題でした。自分にとって Difficulty が高い問題をコンテスト中に解くことができました。
引き続き ABC の問題を紹介していきます。
