天下一プログラミングコンテスト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 | 3 | 6 | 8 | 8 | 8 | 8 | 9 | 10 | 9 | 8 | 9 | 10 | 9 | 8 | 9 | 10 | 9 | 8 | 9 | 10 |
2 | 6 | 18 | 20 | 16 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | |
3 | 8 | 20 | 28 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | |
4 | 8 | 16 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | |
5 | 8 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | |
6 | 8 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | |
7 | 9 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | |
8 | 10 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | |
9 | 9 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | |
10 | 8 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | |
11 | 9 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | |
12 | 10 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | |
13 | 9 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | |
14 | 8 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | |
15 | 9 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | |
16 | 10 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | |
17 | 9 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | |
18 | 8 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | |
19 | 9 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | |
20 | 10 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 | 20 | 18 | 16 | 18 |
以下、N ≥ M と仮定します。
まず、重要な性質として、同じ行または同じ列にある3のマスの間にあるマスの個数はちょうど3になり、4以上にはできません。 また、間にある3マスの並びは1,2,1以外ありません。
もう一つの重要な性質として、3は斜めに並びます。
3 | 1 | 2 | 1 | 3 | |||
1 | 3 | 1 | 2 | 1 | 3 | ||
2 | 1 | 3 | 1 | 2 | 1 | 3 | |
1 | 2 | 1 | 3 | 1 | 2 | 1 | |
3 | 1 | 2 | 1 | 3 | 1 | 2 | |
1 | 3 | 1 | 2 | 1 | 3 | 1 | |
2 | 1 | 3 | 1 | 2 | 1 | 3 | |
: |
3 | 1 | 2 | 1 | 3 | 2 | ||
3 | 1 | 2 | 1 | 3 | 1 | 2 | |
1 | 2 | 1 | 3 | 1 | 2 | 1 | |
2 | 1 | 3 | 1 | 2 | 1 | 3 | |
1 | 3 | 1 | 2 | 1 | 3 | 1 | |
3 | 1 | 2 | 1 | 3 | 1 | 2 | |
1 | 2 | 1 | 3 | 1 | 2 | 1 | |
: |
M = 1 の場合
N ≥ 11と仮定すると3のマスは2つ以上あることになります。 これにより内側の並びは固定されるので、端の余った部分のみを考えれば良く、 余りが無いとき、余りが3マスのときは1通りに、余りが1マス、余りが2マスのときは2通りの配置の仕方があります。 したがって、配置の仕方の数は以下の通りとなります。
N (mod 4) | 一方の余り:もう一方の余り | 配置の仕方の数 |
---|---|---|
0 | 0:3, 1:2, 2:1, 3:0 | 1×1 + 2×2 + 2×2 + 1×1 = 10 |
1 | 0:0, 1:3, 2:2, 3:1 | 1×1 + 2×1 + 2×2 + 1×2 = 9 |
2 | 0:1, 1:0, 2:3, 3:2 | 1×2 + 2×1 + 2×1 + 1×2 = 8 |
3 | 0:2, 1:1, 2:0, 3:3 | 1×2 + 2×2 + 2×1 + 1×1 = 9 |
M ≥ 2 の場合
同様にN ≥ 11と仮定して端の余った部分を考え、左右反転を除くと端の余り方は以下の4通りになります。
余り0
| 余り1
| 余り2
| 余り3
|
上図での余り1, 余り2の空マスの配置の仕方はそれぞれ2通りあります。
|
|
|
|
一方の余りが決まるともう一方の余りが決まるので、以下の通りになります。
M + N (mod 4) | 一方の余り:もう一方の余り | 配置の仕方の数 |
---|---|---|
0 | 0:2, 1:1, 2:0, 3:3 | (1×2 + 2×2 + 2×1 + 1×1)×2 = 18 |
1 | 0:3, 1:2, 2:1, 3:0 | (1×1 + 2×2 + 2×2 + 1×1)×2 = 20 |
2 | 0:0, 1:3, 2:2, 3:1 | (1×1 + 2×1 + 2×2 + 1×2)×2 = 18 |
3 | 0:1, 1:0, 2:3, 3:2 | (1×2 + 2×1 + 2×1 + 1×2)×2 = 16 |
予選A解説:[A] [B] [C] [D] [E(PDF)]
[トップページ]