2009JOI春合宿2-3 Contest 解説
解説
まず、順位を決める対象となる国の成績が確定していなかった場合、その成績をどう決めるか考える。 これは、その国の成績とできる点数の最大値でない場合を考えると、これを最大値と交換しても決して損しないので、なるべく最大値を取れば良いことがわかる。
こうして対象の国の成績を決めると、すでに成績の確定している他の国との順位の関係が明らかになる。これは先に計算しておけばいいので、以降では無視して考える。
残りの国は、点数がひとつだけ確定している国とひとつも確定していない国の2種類に分けられる。 点数が片方確定している国のうち、対象の国の成績を超えるものの個数を決めて、これを $X$ 個としてみる。 すると、国が確定している片方の点数と残りの点数のうちそれぞれ上位 $X$ 個を組み合わせてこれをその $X$ 個とするのが最適となる。 $X$ 個はすでに成績が対象の国を超えることが確定していれば、成績はなるべく高くした方が残りの国の成績が低くなって得だからである。
上位 $X$ 個以外は対象の国の成績を超えてはいけないので、これは、超えないような最大の点数を、国の確定していない点数のリストから二分探索で探してとってくればよい。
最後に、国の確定していない点数のリストだけが残り、これらを組み合わせて成績を作ることになるが、これは点数の低い順に見て、また組み合わせられる最大値を二分探索で求めて組み合わせられるか判定すれば良い。
これで時間計算量が $O(N^2\log N)$ になって、この問題が解けた。
