Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

競技プログラミングなんでもAdvent Calendar 2024

Day 7
@shizu-p

ABC322 D Polyomino を少し噛み砕く

Last updated at Posted at 2024-12-06

始めに

実装問題として有名なABC322 Polyomino をupsolveしたときに私が考えていたことを書きます。
実装問題が苦手な方への一助になればと考えています。
AtCoder公式解説や解説放送を見て解いたので似通っている部分が多分にあります。
C++での解説になります。

問題文

問題概要

テトリスのようなブロックが3つ与えられる。回転、平行移動を行い $4 \times 4$ マスぴったり重複なく埋めることが出来るかどうかを判定しろ。

考えたこと

素直に全探索をするだけで解けそう。

1つ目のブロックの向きを探索
    2つ目のブロックの向きを探索
        3目のブロックの向きを探索
            1つ目のブロックを平行移動
                2つ目のブロックを平行移動
                    3つ目のブロックを平行移動

このようなforループをすれば全探索が可能です。
1つのブロックに対して回転を$4$回、平行移動を最大で$16$回行うことになります。
forループ回数は$4^3 \times 16^3 = 262144$ ですね。
実行制限時間は$2000$msなのでこの方針で実装しました。(実際に提出した実装は1つ目のブロックの向きの探索を省いています。1)

これを「やるだけ」なのだけれど「やるだけ」が私にとってかなり難しかったです。
1つずつやることを分解していきます。

  • 向きの探索
  • ブロックの平行移動

この$2$つを丁寧に分解します。

前提

  • 縦方向(row)を $i$ ,横方向(column)を $j$ , 0-indexed で考える
  • $n = 4$ とする。(マスの行と列の数)
  • 1つのブロックに対し操作することがたくさんあるのでPolyという構造体を作ってその中で回転と平行移動の操作を行う

Polyの基本形は以下の通りです。

struct Poly {
    int n;
    vector<string> p;
    Poly(int n = 4) : n(n) { p.resize(n); }

    void input() {
        for (int i = 0; i < n; ++i) {
            cin >> p[i];
        }
    }
};

実装

向きの探索

向きを探索するときに考えたことは

  1. どのような実装をすれば$90$度回転できるか
  2. 向きを変える前の状態(入力を受け取ったときの状態)を保持するか

この2つを考える必要があります。

どのような実装をすれば90度回転できるか

これは慣れている競プロerなら一瞬で実装できるかも。

    void rotate() {
        auto old = p;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                p[i][j] = old[n - 1 - j][i];
            }
        }
    }

これで時計周りに90度回転できます。ABCのC辺りで文字列を回転させる必要のある問題がよく出てくるのでこのまま覚えてしまうのがいいと思います。

向きを変える前の状態(入力を受け取ったときの状態)を保持するか

1つ目のブロックの向きを探索するときに1回目の探索では1回時計周りに回して探索、2回目では2回時計周りに回して探索...というふうに実装するよりも1回目の探索で1回時計回りに回す、2回目の探索でもう一度時計周りに回す...ということを繰り返したほうが実装は楽になりそうです。
入力を受け取ったときのブロックの状態をわざわざ保持する必要もないので今回は向きを変える前のブロックの状態を持たないことにします。

ブロックの平行移動

ブロックの移動をするときに考えたことは

  1. どのような実装をすれば任意の行、列分の平行移動できるか
  2. 配列外参照に対してどう対処するか
  3. 行、列を平行移動させるときにブロックの部分がはみ出てしまうときはどうすればよいか
  4. 移動前の状態を保持するべきか

どのような実装をすれば任意の行、列分の平行移動できるか

簡単のため行の移動だけを考えます。
行の移動は簡単で$i$行を$di$行分移動させたいときは p[i+di] = old[i]; すればよいです。
p[i+di] = p[i] のように実装すると想定通りの挙動をしません。

.###   .###   .###
..#. ->.### ->.###
....   ..#.   .###
....   ....   ..#.

このようなブロックの場合を考えると理解しやすいかもしれません。
列の移動も同じように$j$列を$dj$列分移動させたいときは

auto old = p;
for (int i = 0; i < n; ++i) {
    p[i][j + dj] = old[i][j];
}

for文が必要になり少々面倒ですね。
これら2つを全ての行と列に行えば平行移動ができます。

    void move(int di, int dj) {
        auto old = p;
        for (int i = 0; i < n; ++i) {
            p[i + di] = old[i];
        }
        old = p;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < n; ++i) {
                p[i][j + dj] = old[i][j];
            }
        }
    }

配列外参照に対してどう対処するか

1で記述したコードは配列外参照に対して何の対策も行っていないためdi dj が共に0のとき以外だと実行時エラーを起こしてしまいます。
これは添字の余りを取ることで解決できます。
3行目(0-indexed)を1行右にズラして0行目に持っていくようなイメージで実装します。
余りは行数(列数)の$n$で取ってあげればいいですね。

    void move(int di, int dj) {
        auto old = p;
        for (int i = 0; i < n; ++i) {
            int ni = i + di;
            ni += n;
            ni %= n;
            p[ni] = old[i];
        }
        old = p;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < n; ++i) {
                int nj = j + dj;
                nj += n;
                nj %= n;
                p[i][nj] = old[i][j];
            }
        }
    }

ni += n; nj += n; を記述しているのは探索するときにdi dj が負の値を取る場合があるからです。

行、列を平行移動させるときにブロックの部分がはみ出てしまうときはどうすればよいか

ブロックの部分がはみ出るということは先ほど実装でいうところの

3行目(0-indexed)を1行右にズラして0行目に持っていく

このパターンのときに元の状態の3行目にブロックが存在していたらブロックがはみ出るような平行移動になってしまいます。つまりi+di、j+djが$n$以上になるか負の値になった場合、その行(列)にブロックが存在すればそれはブロックがはみ出る操作ということになります。
ここで今までpを動かすmove関数の返り値をvoidにしていましたが、はみ出ているかどうかを確認する関数にしたほうが枝狩りを行いやすいのでboolを返す関数に直します。

    bool move(int di, int dj) {
        auto old = p;
        for (int i = 0; i < n; ++i) {
            int ni = i + di;
            bool out = false;
            if (ni >= n || ni < 0) out = true;
            ni += n;
            ni %= n;
            p[ni] = old[i];
            if (out) {
                if (p[ni].contains('#')){
                    return false;
                }
            }
        }
        old = p;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < n; ++i) {
                int nj = j + dj;
                bool out = false;
                if (nj >= n || nj < 0) out = true;
                nj += n;
                nj %= n;
                p[i][nj] = old[i][j];
                if (out) {
                    if (p[i][nj] == '#') return false;
                }
            }
        }
        return true;
    }

p[ni].contains('#')

あまり本題とは関係ありませんが、かなり便利なメンバ関数がC++23で登場しました。
https://cpprefjp.github.io/reference/string/basic_string/contains.html
std::map や std::setにも使用できます。

移動前の状態を保持するべきか

保持するべきです。これはそもそも行と列の平行移動を行うmove関数は途中で打ち切りになってfalseを返すような実装を行っているし、元の状態から何行(列)移動したかで考えているからです。

向きを変えて位置を変えて最後の最後で$16$マス全て重複なく埋まっているかを確認するときのことを考えると移動後専用の配列を準備しておく必要があります。初期化の際にすでに持っておきます。

struct Poly {
    int n;
    vector<string> p;
    vector<string> res;
    Poly(int n = 4) : n(n) {
        p.resize(n);
        res.resize(n, string("    "));
    }
};

move関数はresを更新していくように実装します。
ここまでの実装でPolyは以下のようになります。

struct Poly {
    int n;
    vector<string> p;
    vector<string> res;
    Poly(int n = 4) : n(n) {
        p.resize(n);
        res.resize(n, string("    "));
    }

    // 入力受け取り
    void input() {
        for (int i = 0; i < n; ++i) {
            cin >> p[i];
        }
    }

    void rotate() {
        auto old = p;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                p[i][j] = old[n - 1 - j][i];
            }
        }
    }

    bool move(int di, int dj) {
        res = p;
        for (int i = 0; i < n; ++i) {
            int ni = i + di;
            bool out = false;
            if (ni >= n || ni < 0) out = true;
            ni += n;
            ni %= n;
            res[ni] = p[i];
            if (out) {
                if (res[ni].contains('#')) {
                    return false;
                }
            }
        }

        auto old = res;
        for (int i = 0; i < n; ++i) res[i] = "    ";
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < n; ++i) {
                int nj = j + dj;
                bool out = false;
                if (nj >= n || nj < 0) out = true;
                nj += n;
                nj %= n;
                res[i][nj] = old[i][j];
                if (out) {
                    if (res[i][nj] == '#') return false;
                }
            }
        }
        return true;
    }
};

あとは上記で実装した関数を利用して最初に書いた素直な全探索を実装するだけですね。

1つ目のブロックの向きを探索
   2つ目のブロックの向きを探索
       3目のブロックの向きを探索
           1つ目のブロックを平行移動
               2つ目のブロックを平行移動
                   3つ目のブロックを平行移動

向きを探索するのは単純にrotate()をすればいいですが平行移動する辺りは実装がゴチャゴチャになりそうなので今回は再帰関数を用いて少しでもスッキリさせました。
再帰関数の中身は移動させるdi と dj を用意して3ブロックとも移動させたら$16$マス全て埋まっているかのチェックを行えばよいです。

    auto rec = [&](auto f, int count = 0) -> bool {
        // ブロックを全てくっつける
        if (count == m) {
            int n = 4;
            vector<string> checker(n, string(n, '.'));
            for (int k = 0; k < m; ++k) {
                auto &res = Polyomino[k].res;
                if (k == 0)
                    checker = res;
                else {
                    // ブロックの重複があったら false を返す
                    for (int i = 0; i < n; ++i) {
                        for (int j = 0; j < n; ++j) {
                            if (res[i][j] == '.') continue;
                            if (res[i][j] == checker[i][j]) {
                                return false;
                            }
                            checker[i][j] = res[i][j];
                        }
                    }
                }
            }

            // 16マス全て埋まっているか確認する
            bool isok = true;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (checker[i][j] == '.') isok = false;
                }
            }
            // ans はグローバル変数
            if (isok) ans = true;
            return false;
        }
        
        // 平行移動
        for (int di = -3; di < 4; ++di) {
            for (int dj = -3; dj < 4; ++dj) {
                if (!Polyomino[count].move(di, dj)) {
                    continue;
                }
                f(f, count + 1);
            }
        }
        return false;
    };

重複のマスがないかどうかのチェックが少し面倒ですが今までのmove関数に比べたらすごく楽ですね。
ansをグローバル変数に置いて一度でもピッタリハマることが出来ればans = true; にしています。
最後に最初のforループの中に再帰関数を置けば完成です。

    for (int p0 = 0; p0 < 4; ++p0) {
        for (int p1 = 0; p1 < 4; ++p1) {
            rec(rec);
            Polyomino[1].rotate();
        }
        Polyomino[0].rotate();
    }

p0のループで1つ目のブロックの回転、p1のループで2つ目のブロックの回転、rec関数で平行移動と$16$マス埋まっているかのチェックを行っています。

提出リンク
https://atcoder.jp/contests/abc322/submissions/60454195

最後に

実装問題はこまめにprintデバッグしてどこでバグがどこで起こったかをすぐに解明できるようにしたほうがよいです。この記事を書くにあたってPolyominoを解き直している最中に、記事中でも書いたp[i+di] = p[i] とコーディングしてしまい少し手間取りました。この記事を書いている私も実装問題がかなり苦手なので、みなさんの実装問題の解説記事を見てみたいです。
記事を書き終えてから思ったのですがラムダで再帰を書いているせいで思ったよりもキレイになりませんでしたね。

  1. ブロック1つだけならば向きを固定しても他の2つのブロックで向きを調整すればいいので問題ない。 ↩

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?