C - Matrix Reducing Editorial by leaf1415
元の問題文のように \(1\) つずつ行や列を削除するのではなく、 「初期状態の \(A\) からいくつか( \(0\) 個でも良い)の行と列を選んで、選んだ行と列たちを同時にまとめて削除する」 のをちょうど \(1\) 回やると考えても問題ありません。 例えば、下記の入力例1の \(A\) からは、
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
\(1\) 行目、\(3\) 行目、\(2\) 列目、\(5\) 列目を選んで同時に削除することで、 下記の入力例1の \(B\) と一致させることができます。
6 8 9
16 18 19
操作によって \(A\) を \(B\) と一致させることができるかを判定するには、 「 \(H_1\) 個の行のそれぞれについて、その行を削除するかどうか」を選ぶ \(2^{H_1}\) 通りの方法と、 「 \(W_1\) 個の列のそれぞれについて、その列を削除するかどうか」を選ぶ \(2^{W_1}\) 通りの方法の組み合わせ(全 \(2^{(H_1+W_1)}\) 通り)のすべてを実際に試して、その中に操作後の \(A\) が \(B\) と一致するものがあるかを判定すれば良いです。
\(2^{(H_1+W_1)}\) 通りある行と列の選び方の組み合わせを列挙するには、bit全探索と呼ばれる以下に述べる方法を用いるのが簡潔でしょう。 「 \(H_1\) 個の行のそれぞれについて、その行を削除するかどうかを選ぶ選び方」のそれぞれを、下記を満たすような \(2\) 進数表記で \(H_1\) 桁の非負整数 \(X\) で表現します。
\(i = 0, 1, 2, \ldots, H_1-1\) について
- \(i\) 行目を削除するときは、\(X\) の下から \(i\) 桁目は \(1\) であり、
- \(i\) 行目を削除しないときは、\(X\) の下から \(i\) 桁目は \(0\) である。
例えば、\(5\) 個の行のうち \(1\) 行目と \(3\) 行目を削除するという選び方は、 \(2\) 進数表記で \(00101\) と表せます。 このようにして、\(2^{H_1}\) 通りある行の選び方は、 \(2\) 進数表記でそれぞれ \(000\cdots 00, 000\cdots 01, \ldots, 111\cdots 11\) 、 すなわち、\(10\) 進数表記でそれぞれ \(0, 1, \ldots, 2^{H_1}-1\) で表現できます。 同様に、「 \(W_1\) 個の列のそれぞれについて、その列を削除するかどうかを選ぶ選び方」も、\(0, 1, \ldots, 2^{W_1}-1\) と表現できます。
よって、行の選び方 \(0, 1, \ldots, 2^{H_1}-1\) を走査するループと、列の選び方 \(0, 1, \ldots, 2^{W_1}-1\) を走査するループの、二重ループによって行の選び方と列の選び方の組み合わせを全探索できます。その二重ループの内部で、それぞれの行と列の選び方が \(A\) を \(B\) に一致させるかを判定すれば良いです。
以下に、C++ 言語による正解例を記載します。
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
int h1, h2, w1, w2;
int a[15][15], b[15][15];
cin >> h1 >> w1;
for(int i = 1; i <= h1; i++) for(int j = 1; j <= w1; j++) cin >> a[i][j];
cin >> h2 >> w2;
for(int i = 1; i <= h2; i++) for(int j = 1; j <= w2; j++) cin >> b[i][j];
for(int i = 0; i < (1<<h1); i++){
for(int j = 0; j < (1<<w1); j++){
vector<int> hvec, wvec;
for(int k = 1; k <= h1; k++) if((i & (1<<(k-1))) == 0) hvec.push_back(k);
for(int k = 1; k <= w1; k++) if((j & (1<<(k-1))) == 0) wvec.push_back(k);
if(hvec.size() != h2 || wvec.size() != w2) continue;
bool match = true;
for(int k = 1; k <= h2; k++){
for(int l = 1; l <= w2; l++){
if(a[hvec[k-1]][wvec[l-1]] != b[k][l]){
match = false;
break;
}
}
}
if(match){
cout << "Yes" << endl;
return 0;
}
}
}
cout << "No" << endl;
return 0;
}
posted:
last update: