第6回 ドワンゴからの挑戦状 本選 A - 2525敷き詰め

atcoder.jp

構築ゲーなので「こうすればいい」ではなく発想法をメモ。

まず2でも5でも連結サイズが小さいことに着目する。HやWが大きい場合、例えば角や辺以外に2を配置するとその周囲8マスには2が1個しか置けないことから残りが5であることが確定する。すると5の連結サイズが7になってしまい条件を満たさない。

よって2は辺や角に配置する必要がある。

次に5を辺や角以外に配置する場合、色々試すと3x3の配置が1個見つかる。これがコーナーケースなので埋め込もう。

よって上記コーナーケースを除くと、2も5も辺や角にしか配置できないことがわかる。そのようなケースはmin(H,W)<=2 であることがわかる。

まずmin(H,W)=1の場合はかんたんで、2と5を交互に並べていけばよくmax(H,W) mod 7 が0, 2, 5のいずれかで可能。

次にmin(H,W)=2の場合を考える。以下問題にあるサイズ2またはサイズ5の連結成分を形によらず「2または5のブロック」と呼称する。min(H,W)=2の場合、合計マス数は必ず偶数になるため、5のブロックを1個以上使う場合その数は必ず偶数個使う必要がある。また5のブロック同士はくっついてはならない。そのため、最低でも5*2+2=12のブロックが必要になり、これはmax(H,W)=6に相当する。

同じような考えで、HまたはWの長い方に伸ばすことを考えると次のような構成が考えられる。

...|2のブロック｜5のブロック｜2のブロック｜5のブロック｜…

このとき考えられるパターンとして

1. 2のブロックが2n+1個、5のブロックが2n個で合計14n+2, つまりmax(H,W)=7n+1
2. 2のブロックが2n個、5のブロックが2n個で合計14n+2, max(H,W)=7n
3. 2のブロックが2n-1個、5のブロックが2n個で合計14n-2, max(H,W)=7n-1

の3通りが考えられる。これらはちょっと試すと具体的に構成可能であり、それらを場合分けするとAC。

感想：場合分けゲーは苦手です。