問題文 : King Slime解いている人数が少ない問題はなんかドキドキする(小並)

問題文 : 建設事業解法 : つなぐ辺は隣り合うものだけ(Modern Manshion), 長方形の交差判定は上から操作(Fortune Telling), 空港のコストの方が辺より良いときはそれを使う, というJOI 問題のテクニックを総動員する問題です.点のソートをするときに, x 座標…

問題文 : 倉庫番解法 : 「倉庫番の逆」を考える. すなわち, 目標地点から箱を引っ張りまわすBFS を考える. 箱の置き方がO(MN) 個, 隣接する頂点がたかだか4 個であるため, 状態数はO(MN) である.各状態に遷移したら, 答えには連結成分の大きさを足してやれば…

問題文 : 庭園解法 : O(n^3) で長方形列挙を行い, 上下左右から周長の最大値を記録してやれば良い. 長方形列挙は, y 軸の2 点はO(H^2) で決め打ち, x 軸については尺取り法でO(W) で求めれば良い.計算量はO(WH^2) だが, 制限時間ギリギリなので結構大変.コー…

問題文 : Stack Maze解法 :dp[y1][x1][y2][x2] : 区間D : x ∈ [x1, x2], y ∈ [y1, y2] で宝石を置ける個数の最大値とすると, マス(y1, x1) から(y2, x2)に到達可能であれば, D' : x ∈ (x1, x2], y ∈ [y1, y2] などの, Dより小さい区間の最大値からこの値を計…

問題文 : 戦国時代解法 :見張り達の見張るエリアを, 左上と右上の線で分ける.まずは左上側の線の処理を以下のように行う.点P(x, y)を, 点P'(0, y - x)に移して, 簡単な場合分けでその点にいる見張りがどれだけの領地を見張っているかを求めることが出来る.右…

問題文 : 貫きピラミッド解法 : 自分の地点での大きさを, 次のように, 2方向から伝搬しながら更新してやれば良い.どちらから先に行なっても良い. この更新が終われば, あとは各マスの和を取るだけである.O(WH)回の上書きで答えが求まるので, 計算量はO(WH)時…