C++で特定の行列から回文行列を作成できるかどうかを判定するプログラム

問題の概要

h × w のサイズを持つ行列が与えられ、各要素には英字が格納されているとします。この行列をもとに、すべての行と列が回文となっている行列を作成することを考えます。

作成にあたっては、元の行列の行や列を自由に入れ替えることは許されますが、要素そのものを書き換えることはできません。つまり、「a」を「b」に変更するような操作は禁止されています。回文行列を作成できる場合は true を、作成できない場合は false を返します。

例として、入力が h = 4、w = 4、mat = {"xxyy", "xyxx", "yxxy", "xyyy"} である場合、出力は true となります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

マップ mp を定義する
サイズ4の配列 count を定義する
i := 0 から i < h まで、i を1ずつ増やしながら繰り返す:
    j := 0 から j < w まで、j を1ずつ増やしながら繰り返す:
        tp[mat[i, j]] を1増やす
tp 内の各値 val に対して:
    count[val の second 値 mod 4] を1増やす
check := true
h mod 2 が 0 かつ w mod 2 が 0 の場合:
    count[1] + count[2] + count[3] > 0 ならば:
        check := false
h mod 2 が 1 かつ w mod 2 が 1 の場合:
    count[1] + count[3] > 1 ならば:
        check := false
    そうでなく count[2] > h / 2 + w / 2 ならば:
        check := false
それ以外の場合:
    count[1] + count[3] > 0 ならば:
        check := false
    そうでなく h mod 2 が 1 かつ count[2] > w / 2 ならば:
        check := false
    そうでなく w mod 2 が 1 かつ count[2] > h / 2 ならば:
        check := false
check を返す

考え方のポイント

回文の性質上、行・列ともに回文となる行列では、各文字が対称な位置にペアで現れる必要があります。そこで、各文字の出現回数を4で割った余り(0〜3)ごとに分類し、行列の寸法 h と w の偶奇に応じて条件を判定することで、回文行列が構築可能かどうかを効率的に判断できます。

• h・w が両方偶数の場合: すべての文字が4の倍数回出現していなければなりません。
• h・w が両方奇数の場合: 余り1または3の文字は高々1種類、余り2の文字数にも制限が生じます。
• 片方だけ奇数の場合: 余り1または3の文字は存在してはならず、余り2の文字数に上限があります。

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

bool solve(int h, int w, vector<string> mat){
   map<char, int> tp;
   vector<int> count(4);
   for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j)
      tp[mat[i][j]]++;
   }
   for (auto val : tp)
      count[val.second % 4]++;
   bool check = true;
   if (h % 2 == 0 && w % 2 == 0) {
      if (count[1] + count[2] + count[3] > 0)
         check = false;
   }
   else if (h % 2 == 1 && w % 2 == 1) {
      if (count[1]+count[3] > 1)
         check = false;
      else if (count[2] > h / 2 + w / 2)
         check = false;
   } else {
      if (count[1] + count[3] > 0)
         check = false;
      else if (h % 2 == 1 && count[2] > w / 2)
         check = false;
      else if (w % 2 == 1 && count[2] > h / 2)
         check = false;
   }
   return check;
}
int main() {
   int h = 4, w = 4;
   vector<string> mat = {"xxyy", "xyxx", "yxxy", "xyyy"};
   cout<< solve(h, w, mat);
   return 0;
}

入力

4, 4, {"xxyy", "xyxx", "yxxy", "xyyy"}

出力

1