kaage精進録

雑な解説とかライブラリとかおきもちの垂れ流しです。

AtCoder AGC021-C Tiling

解いた赤diffでは2問目。(1問目はReversing and Concatenating)

2種類のタイルの敷き詰めなので、片方の敷き詰め方だけ考えて、もう片方を敷ける場所がたくさん確保できるように最適化する、という方針で行った。 とりあえず横向きを敷き詰め終わった後のことを考える。 このとき、空きの長さが偶数である列の数を最大化/奇数である列の数を最小化すればいいとわかり、次のような方針が立つ。

  • 縦の長さ, 横の長さともに偶数なら、横のタイルを縦に2枚重ねて、その塊を適当に配置していく。
  • 縦の長さが奇数で横の長さが偶数なら、横のタイルを端の一行にのぺっと敷いたあと、上と同じことをする。ただし、これで1枚余る場合があるが、これはどこかに適当に置くしかない。
  • 縦の長さが偶数で横の長さが奇数なら、上のを回転するのと同じ。
  • 縦の長さ, 横の長さともに奇数なら、一行に横のタイルを敷こうとすると端に一列余る。実は、向かいの行の余った部分にかぶるように横のタイルを置くと、無駄を増やさずにタイルを敷けるので、適当に1枚置いて無駄になる、ということがなくなる。

これをそれぞれ実装したあと、あとは残った向きのタイルを貪欲に敷き詰めればよい。 また、可否の判定の不等式もこれで簡単に立つので、これでこの問題が解けた。 実装はこの方針だとかなり面倒で、250行くらい。