IOI(国際情報オリンピック) - joi2011-day4 解説

筆者: qnighy

※ここでの「IOI」は日本情報オリンピックで出題された問題のタイトルである。

100M点分の試験の各参加者の点数がわかっていて、100(N-M)点分の試験がまだ残っているとき、絶対に金メダルに入ることのできる参加者の一覧と金メダルに入る可能性のある参加者の一覧をそれぞれ列挙する問題である。

O(N^2logN)解法

明らかに、「自分だけ満点、他は全員零点」である場合と「自分だけ零点、他は全員満点」である場合を調べればよい。

それぞれの参加者について、その参加者だけ突出した点を取った場合とその参加者だけ突出して悪い点数を取った場合のそれぞれを実際にソートして調べる。

再度ソートしなくても、現在の点数でみたときの順位と、次の試験で極端な点数を取ったと仮定したときに自分が挿入される位置をそれぞれ二分探索で求めて、多少の条件分岐を行えば答えが得られる。

この問題は完全フィードバックであったため、境界条件の検討を避けてとりあえずSubmitしてみるという手もあるにはあるが、少しは考えてから提出したほうがほうがよいと思われる。