11/16 PKU

2430 Lazy Cows

2*Bのグリッド上に牛がN頭いる。K個の長方形を置いて牛を全部カバーしたい。面積の和の最小値を求めよ。

牛をソートしておいて、左から順に見ていくが、「上段をカバー」「下段をカバー」「両方の段をそれぞれ幅1でカバー」「両方の段を幅2でカバー」の状態を覚えておいてDP。

2185 Milking Grid

各マスに文字が書いてあるグリッドが与えられるので、「それを敷き詰めると元のグリッドになる」ような、最小の長方形を求めよ。

まず、縦方向と横方向に独立に考えて良い。
縦方向の周期について考える。文字列をソートなどして、各行同じパターンのものには同じ数を、違うパターンのものには違う数を与えるようにしておく。
その後、各行についてつけられた数字について、KMPを行うと、N - fail[N]が周期である。これを横方向についても行う。

KMPでなぜ周期がわかるかというと、文字列の[0, fail[N]) の部分と、[N-fail[N], N)の部分は一致していることからすぐにわかる。