【C++】ABC264 C問題 Matrix Reducing

未分類

ABC264のC問題 Matrix Reducingを解説します。

問題のポイント
A行列からどの行を選んで行列を作成するか？という部分でbit全探索という考え方を使いました。（列の選び方についても同様です。）

A行列が5×5行列、B行列が3×3行列であったとき、A行列の5行から3行を選ぶ必要があります。
選んだ行（列）を全てを列挙するのにbit全探索を利用します。
bit全探索では2進数をうまく利用してその桁に意味を持たせていきます。

上の5行の行列から3行を選ぶという例では5桁の2進数を考えます。
例えば、11001。
右から0桁目は1、1桁目は0、2桁目は0、3桁目は1、4桁目は1と見ることができ、今回の問題では下のような意味をもたせます。

i桁目が1であればi行目を選ぶ

すると、11001は、0行目、3行目、4行目を選んでできる行列という意味になります。
以下、5桁でできる2進数とその意味をざっと列挙してみます。

00000 => どの行も選ばない
00001 => 0行目を選ぶ
00010 => 1行目を選ぶ
.
.
00111 => 2行目と1行目と0行目を選ぶ
01000 => 3行目を選ぶ
01001 => 3行目と0行目を選ぶ
01010 => 3行目と1行目を選ぶ
01011 => 3行目と1行目と0行目を選ぶ
01100 => 3行目と2行目を選ぶ
.
.
11111 => 全ての行を選ぶ

こんな感じです。3行を選ぶ以外の全てのパターンが考えられている点に注意です。
今回の問題では3行だけを選ぶものを利用すればいいです。
（vectorのsizeでうまいことやっています。）

ざっと、bit全探索の考え方について解説しました。

入力例

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

回答例

#include
using namespace std;
using P = pair;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
    // ここから
    int h1, w1, h2, w2;
    cin >> h1 >> w1;
    vector< vector < int > > a(h1, vector< int >(w1));
    rep(i, h1) {
        rep(j, w1) {
            cin >> a[i][j];
        }
    }
    cin >> h2 >> w2;
    vector> b(h2, vector< int >(w2));
    rep(i, h2) {
        rep(j, w2) {
            cin >> b[i][j];
        }
    }
    // ここまで入力受け取り

    // 行列Aからh2行選び、さらにw2列選んだ行列をcとして、行列bと等しいかをチェック
    // bit全探索を用いてどの行、どの列を選ぶかを考えている
    for (int bit_h = 0; bit_h < (1 << h1); bit_h++) {
        for (int bit_w = 0; bit_w < (1 << w1); bit_w++) {
            vector< int > tmp_h;  // どの行を選ぶかを管理するvectorを準備 [0,1,2]みたいな感じにしていく
            for (int i = 0; i < h1; i++) {
                if ((bit_h >> i) & 1) tmp_h.emplace_back(i);
            }
            vector< int > tmp_w;   // どの列を選ぶかを管理するvectorを準備
            for (int j = 0; j < w1; j++) {
                if ((bit_w >> j) & 1) tmp_w.emplace_back(j);
            }
            if (tmp_h.size() != h2) continue;   // 長さがh2と合わないものもあるので、その場合はcontinue
            if (tmp_w.size() != w2) continue;   // 列も同様
            vector> c(h2, vector< int >(w2));
            rep(i, h2) {
                rep(j, w2) {
                    c[i][j] = a[tmp_h[i]][tmp_w[j]];    // tmp_hは[0,1,3]のようになっている。0行目、1行目、3行目を選択するという意味
                                                        // tmp_wも同様
                }
            }
            if (c == b) {   // vectorが等しいかどうかは"=="で判定可能
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

コメント