トヨタ自動車プログラミングコンテスト2023#1 (AtCoder Beginner Contest 298) F - Rook Score (500)
愚直に行と列の組み合わせを全部求めると$ 10^{18}通りもある
しかし実際に数が書かれる行と列はそれぞれ$ \mathcal{O}(N)ずつ
重複を無視して行と列に書かれている数の積の多い方から$ N+1個を選べるとすると、重複は高々$ N個のため、その内最低1個は重複を考えた場合でもそのままの値になり、上から$ N+2個目以降のいずれよりも大きい値になる
もちろん重複した分を引いても$ N個の内どれかが重複無しのより大きい値になることもある
優先度付きキューで重複の無い場合の大きい方$ N+1個とそのときの値を求める
重複の無い場合の値、行、列の配列内でのインデックスを持つ
行と列をそれぞれ値の降順でソートし、先頭をキューに入れる
次のように行う
求めた行列のマスに数が書いてあればそれは重複カウントしているので引く
最大値を更新できるか確認
行と列のインデックスをそれぞれ後ろにずらした場合の値をキューに追加
この操作が$ N+1回回ったら終了
配列のソートが$ \mathcal{O}(N \log N)、ループ内での1周の操作が$ \mathcal{O}(\log N)で全体で$ \mathcal{O}(N \log N)
問題: https://atcoder.jp/contests/abc298/tasks/abc298_f
提出: https://atcoder.jp/contests/abc298/submissions/40661348
#トヨタ自動車プログラミングコンテスト2023#1 #トヨタ自動車プログラミングコンテスト #ABC298 #500pt #F #ABC #AtCoder
#優先度付きキュー #O(NlogN) #グリッド