人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:D - Double Landscape

問題

atcoder.jp

解法

各マス (i, j) に書くことが出来る数字の最大値を max_(i, j) とする.また,数字 i が書くことが出来る数字の最大値になっているマスの個数を cnt_i とし,数字 i を書く時点で書くことが出来るマスの総数を avail_i とする.

前処理として,A_i == B_j を満たす (i, j) の組が存在した場合,数字 A_i (B_j) はマス (i, j) に書くしかない.なぜならば,もしマス (i, j) 以外に書いたら必ず条件に反してしまうから.このような数字の集合を kotei とする.

また,kotei に属さず,A_i, B_j に表れている数字の集合を must とする.must のそれぞれの要素について,A_i を書き込むことのできるマスは A_i < B_j を満たすマス (i, j),B_j を書き込むことのできるマスは B_j < A_i を満たすマス (i, j) であるので,各 must の要素について書き込める先のマスの個数を数えておく.このような数字 i を書き込める先のマスの個数を musts_i とおく.

数字を N*M ~ 1 の順番に書いていくことを考える.書き込む数字を i (N*M >= i >= 1) とおく.まず,avail_i に cnt_i を加える.これは新しく cnt_i 個のマスに書くことが出来ようになったということを意味する.

ここで,i が kotei に属しているならば,i を書き込むマスの場所の通り数は1通りである.i が must に属しているならば,通り数は musts_i 通りである.もし,i がこの2つのどちらにも属していないならば,avail_i 個のマスのどこでも書き込んで良いので avail_i 通りである.i + 1 への遷移する際,avail から 1 を忘れずに引く(i を書き込んだ先のマスを引く必要があるため).全部で O(NMlogNM).解法・実装を工夫すれば O(NM).

解答

atcoder.jp

一発 AC 出来たのでよかった.考察にものすごく時間がかかった.

f:id:babcs2035:20190113233650p:plain