D – Tiling とは？
D – Tiling は「モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）」で出題された問題です。管理人がはじめて AtCoder Beginner Contest に参戦したときの記念すべき問題です。初陣の結果は散々なもので 2 問しか解けませんでした。当然 D – Tiling にいたってはどう考えていいかまったくわかりませんでした。
問題の概要は以下のとおりです。
一辺の長さが 1 のマスからなる H 行 W 列のマス目と、N 枚のタイルがある。
i 枚目のタイルは A[i] × B[i] の長方形である。
使用しないタイルがあっても良いし、タイルを回転させて置いても良い。ただし各タイルはマスの線に合わせてマス目からはみ出ることがないように置かなければならない。
このような条件ですべてのマスがちょうど 1 枚のタイルで覆われている状態にすることができるか判定せよ。
解法ですが、すべてのタイルをどの順場で置くか、タイルを置くときはそのまま、90度回転した場合で全パターン試します。すべてのマスがちょうど 1 枚のタイルで覆われている状態にすることができるものがひとつでもあれば “Yes” が答えです。順列全列挙と bit 全探索を組み合わせたような問題といえます。
しかしもっとうまい方法があります。全部 bit 全探索でやってしまうのです。マスは縦横最大 10（合計 100）なので long 型（64bit）ではできません。128bit 整数型を使います。
先に AC コードを示します。2次元配列を使って全探索するのと比べると 10 倍の速さです。なぜこれでいいのかは後で解説します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
class Program { static void Main() { // ビット bit に i 番目のフラグが立っているかどうか bool IsSet(int bit, int idx) => (bit & (1 << idx)) != 0; // ビット bit に i 番目のフラグを消す int RemoveIndex(int bit, int idx) => bit & ~(1 << idx); int[] nhw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nhw[0]; int H = nhw[1]; int W = nhw[2]; W += 1; (Int128, Int128)[] X = new (Int128, Int128)[N]; for (int i = 0; i < N; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0]; int b = ab[1]; X[i] = (F(a, b), F(b, a)); } int bit = (1 << N) - 1; Int128 S = F(H, W - 1); Console.WriteLine(Calc(S, bit) ? "Yes" : "No"); Int128 F(int a, int b) { Int128 one = Int128.One; return (((one << (a * W)) - 1) / ((one << W) - 1)) * ((one << b) - 1); } bool Calc(Int128 s, int bit) { if (s == 0) return true; s /= (s & -s); for (int i = 0; i < N; i++) { if (IsSet(bit, i)) { foreach (var x in new Int128[] { X[i].Item1, X[i].Item2 }) { if ((s & x) == x) { int next = RemoveIndex(bit, i); if (Calc(s ^ x, next)) return true; } } } } return false; } } } |
グリッド上の連続した長方形領域をビット列で表現する
グリッド上の連続した長方形領域をビット列で表現する方法があります。
グリッドの高さを H、グリッドの幅を W、長方形領域の高さを a、長方形領域の幅を b とします。
まず W をインクリメントします。
そして (((1 << (a * W)) – 1) / ((1 << W) – 1)) * ((1 << b) – 1) とすれば、これでグリッド上の連続した長方形領域をビット列で表現することができるのです。
W をインクリメントする理由ですが、こうすることで行末に番兵を置くことができます。行末に番兵を置くことで行境界をまたぐ事故（番兵なしだと横端と次行頭がつながってしまい、矩形判定がうまくいかない場合がある）を防ぐことができます。また << W で「真下」が簡単に表現できるようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int H = 5; int W = 6; int a = 2; int b = 4; W++; Int128 bit = (((Int128.One << (a * W)) - 1) / ((Int128.One << W) - 1)) * ((Int128.One << b) - 1); for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) Console.Write(((bit & (Int128.One << r * W + c)) != 0) ? 1 : 0); Console.WriteLine(); } // 出力： // 1111000 // 1111000 // 0000000 // 0000000 // 0000000 |
s /= (s & -s) の意味
s & -s は最下位の 1 ビットだけを取り出すという有名なテクニックです。s を割り切る最大の 2 のべき乗を得ることができるのです。
たとえば s = 40 であれば二進数表記すると 00101000 となります。-s = -40 なら 11011000 です。
s & -s を計算すると、
00101000
11011000
——–
00001000 = 8
となります。8 は 40 を割り切る最大の 2 のべき乗です。
s /= (s & -s) を計算すると
00000101 = 5
となりますが、これは 40 = 00101000 の末尾の 0 をすべて取り除いたものと同じです。
グリッド上の連続した長方形領域をビット列との関連でいえば、すでにタイルが置かれている部分を切り捨てて、これを平行移動させたものを取得することができるのです。その状態で新たに置こうとしているタイルを x として (s & x) == x であるなら既存のタイルと重なることなくそのタイルを置くことができることになります。
最後に
AC コードを再掲します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
class Program { static void Main() { int[] nhw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nhw[0]; int H = nhw[1]; int W = nhw[2]; W += 1; // N 種類のタイルを格納する（そのまま置く、90度回転して置くの 2 種類） (Int128, Int128)[] X = new (Int128, Int128)[N]; for (int i = 0; i < N; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0]; int b = ab[1]; X[i] = (F(a, b), F(b, a)); } int bit = (1 << N) - 1; // 未使用のタイルの集合（最初は N 個の bit がすべて立っている） Int128 S = F(H, W - 1); // 行末の番兵以外すべての bit を 1 で埋め尽くす Console.WriteLine(Calc(S, bit) ? "Yes" : "No"); int RemoveIndex(int bit, int idx) => bit & ~(1 << idx); bool IsSet(int bit, int idx) => (bit & (1 << idx)) != 0; // グリッド上の連続した長方形領域をビット列で表現する Int128 F(int a, int b) { Int128 one = Int128.One; return (((one << (a * W)) - 1) / ((one << W) - 1)) * ((one << b) - 1); } bool Calc(Int128 s, int bit) { if (s == 0) // s == 0 とはグリッド上がすべてタイルで覆われた状態（終了。解："Yes"） return true; s /= (s & -s); for (int i = 0; i < N; i++) { if (IsSet(bit, i)) // i 番目のタイルは未使用なので置けるなら置いてみる { foreach (var x in new Int128[] { X[i].Item1, X[i].Item2 }) { if ((s & x) == x) // 既存のタイルと重なることなく置くことができる { // i 番目のタイルは使ったので未使用ではなくなった int next = RemoveIndex(bit, i); // グリッドの一部が x によって覆われた状態で再帰呼び出し if (Calc(s ^ x, next)) return true; } } } } // 全パターン試したがグリッド全体をタイルで埋め尽くすことはできなかった（解："No"） return false; } } } |
