PKU2976 Dropping tests

PKU memo

国内予選に向けての練習で見つけた面白かった問題を忘れないうちに書いておこうと思う。

この問題は、2005年のStanford Local Contestの問題セットをやったときに出会った問題だ。

問題

Inputの形式は以下のように与えられる。

n k
a_1 a_2 ... a_n
b_1 b_2 ... b_n

問題の内容は、
ある人がn個のテストをうけた。それぞれの結果はb_i点満点中a_i点であった。このうちk個のテストの結果はなかったことにして良いとすると、この人の得点百分率(100点中何点か)は最大でいくらになるでしょう？という問題。
このとき、計算の方法は
100 \times \sum_{i \in opt} \frac{a_i}{b_i}
ではなく、
100 \times \frac{\sum_{i \in opt} a_i}{\sum_{i \in opt} b_i}
なのがポイントである。
ちなみに、答えは丸めて整数で表すものとする。

解法

この問題はGreedyにやってもできないし、DPでもできない。


解説を見ても、「GreedyAlgorithmやDynamicProgrammingを思いつくだろうけど、ちゃんとどっちもできないように作ってやったよーん」と書かれている。


でどうやってとくかというと答えを仮定して２分探索とかいう近似解法。
ここら辺うまい表現ができないのは経験不足です・・・。


まず得点率をXとおくと、

\frac{\sum_{i \in opt} a_i}{\sum_{i \in opt} b_i} = X

と表せる。

仮定した得点率をxとし、Xがx以上であるか確かめるためには、

\frac{\sum_{i \in opt} a_i}{\sum_{i \in opt} b_i} \ge x
\sum_{i \in opt} a_i \ge x \times \sum_{i \in opt} b_i
\sum_{i \in opt} a_i - x \times \sum_{i \in opt} b_i \ge 0
\sum_{i \in opt} (a_i - x \times b_i) \ge 0

という式を満たすか調べればよいことになる。
このようにシグマの中に全ての式が入ってしまえば簡単に計算できる。

xは0から1までと決まっているから、この範囲で二分探索してやればよい。

考察

まぁ、こんな問題はあんまり現れないだろうから、どうすればこの解法を思いつけ、どのような問題に適用できるのかが問題だろう。


自分なりに考えてみたところ、
まず、これの出力すべき答えの候補は、0から100までの101通りしかない。この程度の数であれば、その答えを仮定して、それが充足可能かを調べてみる方法もあるのではないか？と思うことぐらいできそうである。


次に、この問題の大きな特徴は、得点率xを満たすかどうか調べることが容易であるという部分にある。容易といっても結構ちゃんと考えないと思いつかない。しかし、はじめから充足可能か調べようと思ってこの問題を考えていればそんなに難しい式変形はしていない。


これは四捨五入してどんな値になるかという問題なので単に"0, 1, 2, ..., 100"について充足可能かを調べたのではできない。しかし、充足可能かの判断が容易とわかっていれば、２分探索で調べるという方法も思いつけるだろうし、"0.5, 1.5, 2.5, ..., 99.5"を大きいほうから順に調べていくという方法でもできそうである。

まとめ

  • 答えを仮定して、充足可能かどうか確かめる

という解法は考えて見る価値がある

参考

このコンテストのサイトは
http://ai.stanford.edu/~chuongdo/acm/2005/
ここに問題、答え、解説がある。


ここのサイトのほかの年度の問題もやってみる価値があるだろう。