Codeforces #180 Div2 D "Fish Weight"
問題
http://codeforces.com/contest/298/problem/D
訳
北極の海には 1~kと番号付けられた、k 種類の魚がいることが分かっている
これらの魚は重さが非減少となるように番号が振られている。
i番目の魚の重さをwiとすると、0 < w1 <= w2 <= ... <= wk となっている。
ホッキョクグマのアリスとボブは何匹か魚を釣ることができていて、
釣った魚の合計が、どちらが上回っているかを考えている。
彼らが釣った魚の種類が与えられたとき、アリスの魚の重さの合計が、
ボブのそれを上回っている可能性があるかを判断せよ。
制約
1 <= アリス、ボブの釣った魚の数 <= 10^5
1 <= k <= 10^9
考えた事
アリスのほうが多く魚を釣っていた場合、
全ての種類の魚を同じ重さと仮定すれば、アリスのほうが重い可能性があるな。
アリスとボブの釣った魚の数が同じ場合どうすればいいか・・
例えばサンプル2の場合
種類 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
アリス | 1 | 1 | 1 | 1 | ||||
ボブ | 1 | 2 | 1 | 2 | 1 |
まあ確かにアリスが上回ることは無理だね。
でもこうだったら?
種類 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
アリス | 2 | 1 | 1 | 1 | ||||
ボブ | 9 | 9 | 9 | 1 | 2 | 1 |
全体の魚の数はボブの圧勝だけど、
4~8番目の魚の数だったら、
アリスが5匹・ボブが4匹となる。
だから例えば1~3の魚の重さを0.1gに
4~8の魚の重さを100kgとかって仮定しちゃえば、
アリスの方が重い可能性がでてくるわけだ。
つまり、
8から8
8から7
8から6
.
.
.
8から1
の魚の数をそれぞれだして、
アリスの方が数が多かったら可能性がある・・けど、
k <= 10^9のため、走査することはできないな。
これは
アリスとボブの釣った魚の種類を降順にソートして、
アリスの方が大きい種類の魚であるインデックスが存在すれかを調べればいいっぽい
アリス 7 6 5 4 4 ボブ 8 7 7 5 3 3 3 3 3.... ↑ koko!!
ソースコード
int a[100010]; int b[100010]; int main() { int n, m, k; cin >> n >> m >> k; for( int i = 0; i < n; i++ ){ cin >> a[i]; } for( int i = 0; i < m; i++ ){ cin >> b[i]; } bool isYes = false; if( n > m ){ isYes = true; // アリスの方が多く釣っていればYES }else{ // 降順ソート sort( a, a+n, greater<int>() ); sort( b, b+m, greater<int>() ); // アリス > ボブなインデックスがあるか調べる for( int i = 0; i < n; i++ ){ if( a[i] > b[i] ) isYes = true; } } cout << (isYes ? "YES " : "NO") << endl; }