AOJ 2825 - クイズ

問題
提出コード

解法

最終問に必要な得点が最大になるとき、の中で少なくとも1人は、その人が答えることができる問題に全て答えています。
同様に、少なくとも1人は、その人しか答えられない問題以外は全て答えられません。
ということで、それぞれの人について、全ての問題に答えたパターンの総得点、そして自分しか答えることができない問題のみに答えたパターンの総得点を計算し、それぞれのパターンについて、前者は降順、後者は昇順でソートをします。
そして、

• ソートしたそれぞれの先頭の差+1

が答えになります。

しかし、ソートしたそれぞれの結果が、同じ人についての計算結果だった場合については別処理が必要です。例えば

3 3
100 1 1  
100 2 1  
1000 2 2 3  
1000 2 1 3  

のような入力例だと、最低点は3人目の0、最高点も3人目で2000となります。
このようなパターンでは、ソートした配列の前から2つをみて、最高点の1番目と最低点の2番目、最高点の2番目と最低点の1番目の差のうち大きい方を選んで、1加算したものが答えになります。

感想

この手の問題をバグなくさらっと解けるのはいいですね。
今回は貪欲が正しい確証をもって通したのでよかったと思います。
典型問題は基本このペースで通していきたいと思います。