Mister雑記

競プロやります。

AGC021 「Tiling」 (900)

初の900点AC。

問題リンク

概要

 Nマス横 Mマスのグリッドに、

  • 縦1マス横2マスのタイル A
  • 縦2マス横1マスのタイル B

を重ねたり回転させたりせずに敷き詰めることは可能か。可能ならば敷き詰め方の例を出力せよ。

なお出力形式のvが小文字であることに注意。

制約

  •  1 \leq N, M \leq 10^3
  •  0 \leq A, B \leq 5 \times 10^5

解説

この問題で最大の鍵となるのは、 N Mの偶奇である。これによって大きく3つのパターンに場合分けする。

1.  N, Mが共に偶数の場合

この場合、以下のようにグリッドを2×2の小さい領域に分割してそれぞれに同じ種類のタイルを2枚ずつ置くのが最適となる。

f:id:misteer:20180911210204p:plain

これが可能な条件は NM \geq 4 \left( \lceil A / 2 \rceil + \lceil B / 2 \rceil \right)である1ため、これが可能性の必要十分条件となる。

どうやって埋めるかは自由だが、私は上のように縦パネルを左上から、横パネルを右下から順に埋めるように実装した。

2.  N, Mの一方が奇数の場合

この場合も実のところさっきと大差はなく、下のように端の行か列を先に埋めてしまって1のケースに帰着させるだけでOK。

f:id:misteer:20180911210219p:plain

3.  N, Mが共に奇数の場合

これも上と同様に端の行と列を先に埋めれば大抵の場合いいのだが、余った1マスが原因でコーナーケースが生じる。それが「残った A, Bが共に奇数の場合」である。

このとき1と同様に考えると A, Bでそれぞれ余った1個のタイルが2個分の領域を占めることになるが、実は画像下のように余ったタイルを1つの領域にねじ込むことができる。これによって可能性の条件が僅かながら緩くなるわけだ。

f:id:misteer:20180911210233p:plain

実装例

以上を全て考慮してグリッドを埋めればACなのだが、いかんせん実装が難しい。 私が書いたコードもコピーだらけで正直あまり見せたくないので、見たい人は以下のリンクを踏んでください。

提出コード

感想

  • 場合分けをするってところまでeditorialを見たが、そこからは全部自力で解けたので満足
    • ちなみにeditorialを見る前は「マスを頂点とみなすとグラフになるから、両端を共有しない辺の選び方は......」といった具合に迷走していた
  • コピペ部分を上手いことまとめるなりタイルの埋め方を効率化するなどして、上のコードももっとキレイにできないだろうか

  1.  \lceil x \rceil xの小数点以下切り上げを意味する。切り上げるのは A, Bが奇数のとき余った1個が2個分の領域を占めるためである。