問題
考察
条件を満たす最小の$X$を求めてくださいという問題です。この問題を解くうえで、「下記の2点を満たしたときは二分探索を実装すると小さい計算量で求めることができる」という考察が重要になってきます。
- $X$を決め打った時、条件を満たすかどうかを調べることができる。
- 条件を満たす最小の$X$を求める問題だが、その最小の$X$以上だと確実に条件を満たすことが保証できる。1
では、今回の問題で、上記2点を満たすかどうか見ていきます。
Xを決め打った時、条件を満たすかどうかを調べることができる。
条件は「りんごを$X$円で売ってもよいと考える売り手の人数が、りんごを$X$円で買ってもよいと考える買い手の人数以上である」ことです。各売り手は、「この価格以上なら売ってもよい」という基準価格を持っています。仮に整数$X$を決め打った時、各売り手の基準価格以上かどうかを調べれば、売ってもよいと考える人数を調べることができます。一方、買い手は「この価格以下なら買ってもよい」という基準価格を持っています。売り手と同様に、整数$X$を決め打った時、各売り手の基準価格以下かどうかを調べれば、買ってもよいと考える人数を調べることができます。それぞれの人数を求めることができるので、あとはそれらを比較すれば条件を満たすかどうか調べることができます。
よって、整数$X$を決め打った時、条件を満たすかどうかを調べることができるといえます。
問題の出力例1の場合
(折りたたんでます)
case1: $X=100$と決め打ったとする
売り手
| 売り手1 | 売り手2 | 売り手3 |
|---|---|---|
| 110 | 90 | 120 |
| 売りたくない | 売ってもよい | 売りたくない |
買い手
| 買い手1 | 買い手2 | 買い手3 | 買い手4 |
|---|---|---|---|
| 100 | 80 | 120 | 10000 |
| 買ってもよい | 買いたくない | 買ってもよい | 買ってもよい |
売ってもよい: $1$人
買ってもよい: $3$人
→条件を満たさない。
case2: $X=120$と決め打ったとする
売り手
| 売り手1 | 売り手2 | 売り手3 |
|---|---|---|
| 110 | 90 | 120 |
| 売ってもよい | 売ってもよい | 売ってもよい |
買い手
| 買い手1 | 買い手2 | 買い手3 | 買い手4 |
|---|---|---|---|
| 100 | 80 | 120 | 10000 |
| 買いたくない | 買いたくない | 買ってもよい | 買ってもよい |
売ってもよい: $3$人
買ってもよい: $2$人
→条件を満たす。
これらのように、今回の問題は$X$の値を決め打つと、条件を満たすかを調べることができる。
条件を満たす最小のXを求める問題だが、その最小のX以上だと確実に条件を満たすことが保証できる。
売り手が売ってもよいという条件は各売り手が持つ基準価格以上に$X$が設定されていることです。つまり、$X$の値がより大きいほど、売り手の人数が増えていくことが分かります。一方で、買い手が買ってもよいという条件は各買い手が持つ基準価格以下に$X$が設定されていることです。つまり、$X$の値がより大きいほど、売り手の人数が減っていくことが分かります。このことから、条件を満たす最小の$X$以上の整数だと、確実に条件を満たすことが保証されます。
問題の出力例1の場合
(折りたたんでます)
売り手
$X=100$の場合
| 売り手1 | 売り手2 | 売り手3 |
|---|---|---|
| 110 | 90 | 120 |
| 売りたくない | 売ってもよい | 売りたくない |
売ってもよい: $1$人
$X=120$の場合
| 売り手1 | 売り手2 | 売り手3 |
|---|---|---|
| 110 | 90 | 120 |
| 売ってもよい | 売ってもよい | 売ってもよい |
売ってもよい: $3$人
→売り手の人数が増えていく(減ることがない)
買い手
$X=100$の場合
| 買い手1 | 買い手2 | 買い手3 | 買い手4 |
|---|---|---|---|
| 100 | 80 | 120 | 10000 |
| 買ってもよい | 買いたくない | 買ってもよい | 買ってもよい |
買ってもよい: $2$人
$X=120$の場合
| 買い手1 | 買い手2 | 買い手3 | 買い手4 |
|---|---|---|---|
| 100 | 80 | 120 | 10000 |
| 買いたくない | 買いたくない | 買ってもよい | 買ってもよい |
買ってもよい: $1$人
→買い手の人数が減っていく(増えることがない)
これらから、条件を満たす最小の$X$以上だと確実に条件を満たすはず
ということで、二分探索で求めることができることが分かりました。二分探索を使用して答えを求めましょう。もし二分探索で求めた場合、計算量は$O((N+M)log10^9)$程度になるので、十分に間に合いそうです。
二分探索
二分探索については下記の記事が参考になります。
実装については慣れが必要かもしれません。参考記事を読みながら、ACできるまでコードを書く練習を何度か繰り返すのがいいかもしれません。
実装の注意ですが、二分探索の初期区間(「ok, ng」や「left, right」など)は、一方は確実に条件を満たす値、もう一方は確実に条件を満たさない値を設定しましょう。そして、今回の問題、$X=10^9$は条件を満たさない可能性があります。つまり初期区間の一端に$10^9$を設定するとWAになるので注意してください。
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。
参考
-
あるいはその逆、「条件を満たす最大の$X$を求める問題だが、その最大の$X$以下だと確実に条件を満たすことが保証できる。」でもOKです。 ↩