競技プログラミングにハマるプログラマのスレ 258 (311ﾚｽ)
上下前次1-新
260: 11/15(土)22:58 AAS
# D
初期状態の黒マス集合は 1 個の長方形 [0, X − 1] × [0, Y − 1] です。
各大嵐は、平面を直線 x = Ai（または y = Ai）で 2 つに分け、一方を上（または右）、他方を下（または左）へ平行移動させる全単射なので、黒マス集合は「互いに重ならない長方形の集合」として表現し続けられます。
1 回の大嵐で各長方形は高々 2 個に分割されるため、長方形の総数は高々 2^N（N ≤ 14）です。
最終的な長方形集合に対し、2 つの長方形がマスの辺を共有する（x 区間が重なり y 距離 1、または y 区間が重なり x 距離 1）ときに Union-Find で連結させます。
各連結成分の面積は、その成分に属する長方形の面積の総和として求まり、個数と面積を昇順に出力すればよいです。
# E
省16
上下前次1-新書関写板覧索設栞歴
あと 51 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.005s