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

問題
解法
解答

問題

解法

各マス (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 を書き込むマスの場所の通り数は１通りである．i が must に属しているならば，通り数は musts_i 通りである．もし，i がこの２つのどちらにも属していないならば，avail_i 個のマスのどこでも書き込んで良いので avail_i 通りである．i + 1 への遷移する際，avail から 1 を忘れずに引く（i を書き込んだ先のマスを引く必要があるため）．全部で O(NMlogNM)．解法・実装を工夫すれば O(NM)．