天下一プログラミングコンテスト2013 予選A

C. 天下一二三パズル解説

[問題文]

部分点解法(40点)

全てのパターンを列挙して条件を満たすか計算しても良いですし、手で列挙して数えても良いでしょう。 マス目は最大16マスなので、最大 316 = 43,046,721 パターンになりますが、条件を満たす数字の配置の仕方はそれほど多くありません。 M×N の結果とN×M の結果が等しいことを用いると、10通りの入力に対する答えを考えれば良いことがわかります。

全列挙の結果

1×1 : 以下の 3 通り

  1  2  3

2×1 : 以下の 6 通り

  12  13  21  23  31  32

3×1 : 以下の 8 通り

  121  123  131  132  213  231  312  321

4×1 : 以下の 8 通り

  1213  1231  1312  1321  2131  2132  2312  3121

2×2 : 以下の 18 通り


12  12  12  13  13  13
21  23  31  21  31  32

21  21  21  23  23  23
12  13  32  12  31  32

31  31  31  32  32  32
12  13  23  13  21  23
		

3×2 : 以下の 20 通り


121  121  123  123  131  131  132  132
213  312  231  312  213  312  213  321

213  213  213  213  231  231
121  131  132  321  123  312

312  312  312  312  321  321
121  123  131  231  132  213
		

4×2 : 以下の 20 通り


121  121  123  123  131  131  132  132
213  312  231  312  213  312  213  321

213  213  213  213  231  231
121  131  132  321  123  312

312  312  312  312  321  321
121  123  131  231  132  213
		

3×3 : 以下の 28 通り


121  121  121  121  123  123  123
213  213  312  312  231  312  312
131  132  131  231  312  131  231

131  131  131  131  132  132  132
213  213  312  312  213  213  321
121  321  121  123  121  321  213

213  213  213  213  231  231  231
121  131  132  321  123  312  312
312  312  321  132  312  121  123

312  312  312  312  321  321  321
121  123  131  231  132  213  213
213  231  213  123  213  131  132
		

4×3 : 以下の 16 通り


1213  1213  1213  1213  1231  1312  1312  1321
2131  2132  3121  3121  2312  2131  3121  2132
1312  1321  1312  2312  3121  1213  1213  1213

2131  2131  2132  2312  3121  3121  3121  3121
1213  1312  1213  3121  1213  1213  1312  2312
3121  3121  3121  1213  2131  2132  2131  1231
		

4×4 : 以下の 18 通り


1213  1213  1213  1231  1312  1312  1312  1321
2131  3121  3121  2312  2131  3121  3121  2132
1312  1312  2312  3121  1213  1213  1213  1213
3121  2131  1231  1213  3121  2131  2132  3121

2131  2131  2131  2132  2132  2312  2312  3121  3121  3121
1213  1213  1312  1213  1213  3121  3121  1213  1213  1312
3121  3121  3121  3121  3121  1213  1213  2131  2132  2131
1312  2312  1213  1312  2312  2131  2132  1312  1321  1213
		

部分点解法(40点 + 20点)

実際には条件を満たす数字の配置の仕方はそれほど多くないので、 1マスずつ数字を入れて条件を満たさない場合を枝刈りすれば 深さ優先探索や幅優先探索のような探索アルゴリズムで間に合います。

満点解法

20×20までの答えを見ると、以下のように結果が規則的になることがわかります。 これを利用すればN, Mが大きくても高速に答えを求めることができます。

M
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
N 1 368888910989109891098910
2 618201616182018161820181618201816182018
3 820281618201816182018161820181618201816
4 816161820181618201816182018161820181618
5 816182018161820181618201816182018161820
6 818201816182018161820181618201816182018
7 920181618201816182018161820181618201816
8 1018161820181618201816182018161820181618
9 916182018161820181618201816182018161820
10 818201816182018161820181618201816182018
11 920181618201816182018161820181618201816
12 1018161820181618201816182018161820181618
13 916182018161820181618201816182018161820
14 818201816182018161820181618201816182018
15 920181618201816182018161820181618201816
16 1018161820181618201816182018161820181618
17 916182018161820181618201816182018161820
18 818201816182018161820181618201816182018
19 920181618201816182018161820181618201816
20 1018161820181618201816182018161820181618

以下、N ≥ M と仮定します。

まず、重要な性質として、同じ行または同じ列にある3のマスの間にあるマスの個数はちょうど3になり、4以上にはできません。 また、間にある3マスの並びは1,2,1以外ありません。

もう一つの重要な性質として、3は斜めに並びます。

31213
131213
2131213
1213121
3121312
1312131
2131213
:
312132
3121312
1213121
2131213
1312131
3121312
1213121
:

M = 1 の場合

N ≥ 11と仮定すると3のマスは2つ以上あることになります。 これにより内側の並びは固定されるので、端の余った部分のみを考えれば良く、 余りが無いとき、余りが3マスのときは1通りに、余りが1マス、余りが2マスのときは2通りの配置の仕方があります。 したがって、配置の仕方の数は以下の通りとなります。

N (mod 4)一方の余り:もう一方の余り配置の仕方の数
00:3, 1:2, 2:1, 3:01×1 + 2×2 + 2×2 + 1×1 = 10
10:0, 1:3, 2:2, 3:11×1 + 2×1 + 2×2 + 1×2 = 9
20:1, 1:0, 2:3, 3:21×2 + 2×1 + 2×1 + 1×2 = 8
30:2, 1:1, 2:0, 3:31×2 + 2×2 + 2×1 + 1×1 = 9

M ≥ 2 の場合

同様にN ≥ 11と仮定して端の余った部分を考え、左右反転を除くと端の余り方は以下の4通りになります。

余り0
31
12
21
13
31
:
余り1
3
31
12
21
13
:
余り2
  
3
31
12
21
:
余り3
12
21
13
31
12
:

上図での余り1, 余り2の空マスの配置の仕方はそれぞれ2通りあります。

13
31
12
21
13
:
23
31
12
21
13
:
21
13
31
12
21
:
12
23
31
12
21
:

一方の余りが決まるともう一方の余りが決まるので、以下の通りになります。

M + N (mod 4)一方の余り:もう一方の余り配置の仕方の数
00:2, 1:1, 2:0, 3:3(1×2 + 2×2 + 2×1 + 1×1)×2 = 18
10:3, 1:2, 2:1, 3:0(1×1 + 2×2 + 2×2 + 1×1)×2 = 20
20:0, 1:3, 2:2, 3:1(1×1 + 2×1 + 2×2 + 1×2)×2 = 18
30:1, 1:0, 2:3, 3:2(1×2 + 2×1 + 2×1 + 1×2)×2 = 16

予選A解説:[A] [B] [C] [D] [E(PDF)]
[トップページ]