KLab株式会社 採用情報

予選B-C 天下一王国の歴史

部分点1

あたえられた変換のアルゴリズムを実装して、変換前の状態をすべて試せば良い。

部分点2

例えば、変換後の状態が以下のような状態だった場合に

#.#.#
.#.##
##...
###..
#.#..

変換前を以下のように書きあらわすとする。

AAAAA
AAAAA
AAAAA
AAAAA
AAAAA

さらに、各マスのAに対して、白黒を反転させた状態をBとして書き表すとする。
例えば、(x, y)が(2, 1)の位置について、白黒を反転した状態を以下の様に書き表す。

変換前

AAAAA
AABAA
AAAAA
AAAAA
AAAAA

変換前のあるマスの白黒が反転すると、変換後はそのマスの上下左右の位置にあるマスが白黒が反転する。

つまり、上に対応する変換後の状態は、以下である。

変換後

#...#
....#
###..
###..
#.#..

この対応関係を利用して、変換後のマスがすべて白マスになるような変換前を見つける。

変換前の1段目を仮定

最上段は、仮にすべてAの状態であると仮定する。

2段目を確定

変換後の1段目の黒マスを消去するには、その真下の変換前のAマスをBマスにしなくてはいけない。

変換前

AAAAA
BABAB
AAAAA
AAAAA
AAAAA

変換後

.....
.#.##
.##.#
###..
#.#..

3段目を確定

2段目と同様に、変換後の2段目から変換前の3段目を求める。

変換前

AAAAA
BABAB
ABABB
AAAAA
AAAAA

変換後

.....
.....
####.
#.###
#.#..

4段目を確定

変換前

AAAAA
BABAB
ABABB
BBBBA
AAAAA

変換後

.....
.....
.....
..#..
.#.#.

5段目を確定

変換前

AAAAA
BABAB
ABABB
BBBBA
AABAA

変換後

.....
.....
.....
.....
.....

この操作ですべての黒マスが消えた場合

変換後が全て白マスである場合、変換前も全て白マスという自明な解が存在するので、

AAAAA
BABAB
ABABB
BBBBA
AABAA

がすべて、白マスになるような場合の

AAAAA
AAAAA
AAAAA
AAAAA
AAAAA

を答えれば良い。

つまり、Aの位置に白マス、Bの位置に黒マスを割り当てた。

.....
#.#.#
.#.##
####.
..#..

を答えればよい。

変換前の1番上の段の状態さえ決めてやればそれより下のマスの状態は一意に決まるので、1番上段のマスの状態を全通り試してすべて白マスに変換できるか調べれば良い。この方法で、2番目の部分点を取ることができる。

このような解法はパズルゲームの「ライツアウト」の解法と知られている。「ライツアウト」の解法には他に連立方程式を使う方法があるが、こちらでも2番目の部分点を取ることができる。

満点解法

部分点2では1番上の段の状態を全通りためしたが、実際は1パターンのみを試せばいい。

黒マスが最下段のみに存在する状態になった場合を詳しく考えてみる。

1番下の段に黒マスが残った場合

変換後が

.....
.....
.....
.....
#....

のような形になった場合、以下のoで示した位置のマスについて考える。

....o
...o.
..o..
.o...
o....

このとき25コの全てのマスの上下左右にあるoの数は、偶数個になる(この場合、0コまたは2コ)。
よって、変換前がどのような状態であっても、変換後のoの位置にある黒マスは偶数個となる。

つまり、一番下段にのみしか黒マスが存在せず、かつ下段の一番左が黒であるという変換後の状態に対応する変換前の状態は存在しない

また、以下の4通りのoの配置も、黒マスが偶数個となる。

...o.
..o.o
.o.o.
o.o..
.o...
..o..
.o.o.
o.o.o
.o.o.
..o..
.o...
o.o..
.o.o.
..o.o
...o.
o....
.o...
..o..
...o.
....o

つまり、1番下の段すべてのマスに対して同様のことが言えるため、1番下の段に黒マスが残るような配置に対応する、変換前の状態は存在しない。

与えられたマス目が正方形の場合、同様の性質が成り立つためこの問題では、最上段のパターンを1パターンだけ試せば良い。

補足 : 出題が長方形だった場合

例えば、マス目が3x2で変換前が以下の時

.#.
#.#

変換後は以下になる

...
.#.

つまり、仮に盤面が長方形も許されていた場合は上記の解法を使用することはできない。