競技プログラミング用知識集積所

ABC433E - Max Matrix 2

最終更新：2025年11月27日 02:33

sport_programming

- view

管理者のみ編集可

問題
必要知識
考え方
解答例
注意点
別解

問題

ABC433E

必要知識

B以下レベルの内容は省略

考え方

構成問題※。
条件が厳しいものから詰めていく。

まず、XとYそれぞれの中でダブりがある場合、明らかに無理である。
以下は、それがないとして考える。

XとYの両方に登場している数は、その行その列に入れるしかない。

Xにのみ登場する数は、その行のYが最大である列に入れてしまってよい。
この貪欲法※が成立するのは、これを他の列に入れたとしたら、Y最大の列にはそれより小さい数が入っているはずなので、それら2つを入れ替えても条件が崩れないためである。
ただし、Yの最大値が小さすぎる場合は不可能判定とする。

同様に、Yにのみ登場する数は、その列のXが最大である行に入れてしまってよい。
ただし、Xの最大値が小さすぎる場合は不可能判定とする。

これであとは、各行各列に指定の数未満の数しか入れないように残りのマスを埋めることができればクリア。
これは、残っているマスを全ての上限が大きい順に、残っている数を大きい方から割り当てていく貪欲法※で1つずつ正当性を確認しながらよい。
実装はいくつか方法があり、解答例ではマスをpriority_queue※で、数をset※で管理している。