読者です 読者をやめる 読者になる 読者になる

Xmas Contest 2016 I解説

I問題の解説です。


ベースとして「盤面を白黒に塗り分けて、覆われている黒マスの個数の偶奇で判定をする」という方法を使います。
塗り分け方を変えることによって全ての場合を判定することができます。

まずは一番簡単な T ミノと他を分類します。

f:id:snuke:20161228000505p:plain

このボードのどのように T を置いても黒マスを奇数個覆いますし、それ以外のテトロミノは偶数個覆います。
このボードの上にテトロミノを置く置き方をいろいろ試してみて納得するのも面白いかもしれません(以降の例に関しても)

つまり、覆われている黒マスの個数が奇数個なら T、そうでないなら T でないと言えます。
ここまでで15点取れます。
これ以降は T ミノを無視して考えられます。

次に L ミノと他を分類します。

f:id:snuke:20161228002041p:plain

覆われている黒マスの個数が奇数個なら L、そうでないなら L でないです。
これ以降は L ミノも無視して良いです。

次に S と I,O を分類します。

f:id:snuke:20161228002152p:plain

覆われている黒マスの個数-(Sの個数)が奇数なら S、そうでないなら S でないです。

最後に I と S,O を分類します。

f:id:snuke:20161228002414p:plain

覆われている黒マスの個数-(Sの個数)-(Oの個数)が偶数なら I、そうでないなら I でないです。

ちなみに、O と I,S を分類することもできます。

f:id:snuke:20161228002542p:plain

覆われている黒マスの個数-(Oの個数)が奇数なら O、そうでないなら O でないです。

以上です。

ちなみに、残っている T や L が 0 個でなかった場合、例えば以下ようなケースが分類できません。

f:id:snuke:20161228002712p:plain

昔作った問題愚者のパズルと似たような問題。
この問題にも塗り分け解があるので考えてみて下さい。(解答はこちら

TとLが0/1であるという制約を付けるだけで全て分類できるのを見つけた時は少し興奮しました。
あと、ケースづくりは適当な局所改善山登りを実装するだけ(重いけど)で結構充填できたので良かった。
密なケースだけでなく疎なケースも入れるとデータが少し強くなった。
各ケースに正しい敷き詰め方が存在することを証明するデータはこちら