SRM撃墜大好きっ子に贈る：二分探索問題の撃墜 〜慎重に撃墜ケースを検討すべき一例〜
SRM582 Easy(250) "SpaceWarDiv1"
問題意訳
魔法少女（複数）と敵（複数）がいる。
魔法少女は自分と同等以下の敵を倒せるが、1人倒すたびにソウルジェムが濁っていく。
敵は全て倒したいが、ソウルジェムの濁りが特定の少女に集中し魔女化してしまうのを避けるため、戦闘回数を分散したい。
最大限にうまくやったとき、ソウルジェムの濁りはどこまで抑えられるか。
入力
{魔法少女の強さ}, {敵の強さ}, {それぞれの強さの敵が何人いるか}
出力
一番多く敵を倒した魔法少女のソウルジェムの濁り
解き方
二分探索でどうよ
submitしたWAコード
二分探索が間違っている事に気づいたのに（あれ、これでも通るんだーとか思っちゃって）再提出せず
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
vector<int> mgs;
int mgN, eN;
vector<pair<int,ll> > es;
class SpaceWarDiv1 {
bool po(ll x) {
vector<ll> res(mgN, x);
int ix = 0;
tr(es,it) {
int e_s = it->first;
ll e_c = it->second;
while (e_c > 0) {
if (ix == mgN) return false;
if (mgs[ix] < e_s) return false;
if (res[ix] > e_c) {
res[ix] -= e_c;
e_c = 0;
} else if (res[ix] == e_c) {
res[ix++] = e_c = 0;
} else {
e_c -= res[ix];
res[ix++] = 0;
}
}
}
return true;
}
public:
long long minimalFatigue(vector<int> magicalGirlStrength, vector<int> enemyStrength, vector<long long> enemyCount) {
int maxES = *max_element(all(enemyStrength)),
maxGS = *max_element(all(magicalGirlStrength));
if (maxES > maxGS) return -1LL;
mgN = sz(magicalGirlStrength);
mgs.assign(all(magicalGirlStrength));
sort(all(mgs)); reverse(all(mgs));
eN = sz(enemyStrength);
es.resize(eN);
rep(i,eN){
es[i] = make_pair(enemyStrength[i], enemyCount[i]);
}
sort(all(es)); reverse(all(es));
ll lo = 1LL, hi = LONG_LONG_MAX;
while (true) {
// lo:x hi:o
if (lo+1 == hi) return hi;
ll mi = (lo + hi)/2;
if (po(mi)) hi = mi;
else lo = mi;
}
}
};
撃墜ケース
3人の撃墜ミスを誘いました。Room1ということもあり高レーティングです。
- ltaravilse (黄2083) : {1}{1}{1}
- hjvfy (赤2562) : {1}{1}{1}
- marcina007 (赤3015) : {1}{1}{1}
同室だったPetr様がこのコードを開いて手を出して来なかったのは流石と思いました。
入力 {1}{1}{1} に対する挙動
賢明な読者の皆さんは、このコードがどういう挙動をするかお分かりですよね？
判定関数 po() の値が lo で false, hi でtrueであることを想定して、区間 [1, LONG_LONG_MAX=0x7FFFFFFFFFFFFFFF] で二分探索をしています。はい。lower boundは0であるべきです。0にすればACです。
// あと、lo+hi > LONG_LONG_MAX なことがあり得るケースでは lo + (hi - lo)/2 が良いですね。
1周目
lo=1, hi=0x7FFFFFFFFFFFFFFF
mi = (lo+hi)/2 = 0x8000000000000000/2 = 0xC000000000000000*1
po(mi<0) = falseなのでこれが次回のlo
// こういうのは実装時に assert_true(lo＜hi && !po(lo) && po(hi)) とかしたらいいですね
2周目
lo=0xC000000000000000, hi=0x7FFFFFFFFFFFFFFF
mi=(lo+hi)/2=0x3FFFFFFFFFFFFFFF/2=0x1FFFFFFFFFFFFFFF
po(0x1FFFFFFFFFFFFFFF) = true なのでこれが次回のhi
3周目以降
| lo | mi | hi | 備考 | |
|---|---|---|---|---|
| 1周目 | 1 | -4611686018427387904 | 9223372036854775807 | (lo+hi)/2<0 |
| 2周目 | -4611686018427387904 | 2305843009213693951 | 9223372036854775807 | |
| 3周目 | -4611686018427387904 | -1152921504606846976 | 2305843009213693951 | |
| 4周目 | -1152921504606846976 | 576460752303423487 | 2305843009213693951 | |
| 5周目 | -1152921504606846976 | -288230376151711744 | 576460752303423487 | |
| 6周目 | -288230376151711744 | 144115188075855871 | 576460752303423487 | |
| 7周目 | -288230376151711744 | -72057594037927936 | 144115188075855871 | |
| 8周目 | -72057594037927936 | 36028797018963967 | 144115188075855871 | |
| 9周目 | -72057594037927936 | -18014398509481984 | 36028797018963967 | |
| 10周目 | -18014398509481984 | 9007199254740991 | 36028797018963967 | |
| 11周目 | -18014398509481984 | -4503599627370496 | 9007199254740991 | |
| 12周目 | -4503599627370496 | 2251799813685247 | 9007199254740991 | |
| 13周目 | -4503599627370496 | -1125899906842624 | 2251799813685247 | |
| 14周目 | -1125899906842624 | 562949953421311 | 2251799813685247 | |
| 15周目 | -1125899906842624 | -281474976710656 | 562949953421311 | |
| 16周目 | -281474976710656 | 140737488355327 | 562949953421311 | |
| 17周目 | -281474976710656 | -70368744177664 | 140737488355327 | |
| 18周目 | -70368744177664 | 35184372088831 | 140737488355327 | |
| 19周目 | -70368744177664 | -17592186044416 | 35184372088831 | |
| 20周目 | -17592186044416 | 8796093022207 | 35184372088831 | |
| 21周目 | -17592186044416 | -4398046511104 | 8796093022207 | |
| 22周目 | -4398046511104 | 2199023255551 | 8796093022207 | |
| 23周目 | -4398046511104 | -1099511627776 | 2199023255551 | |
| 24周目 | -1099511627776 | 549755813887 | 2199023255551 | |
| 25周目 | -1099511627776 | -274877906944 | 549755813887 | |
| 26周目 | -274877906944 | 137438953471 | 549755813887 | |
| 27周目 | -274877906944 | -68719476736 | 137438953471 | |
| 28周目 | -68719476736 | 34359738367 | 137438953471 | |
| 29周目 | -68719476736 | -17179869184 | 34359738367 | |
| 30周目 | -17179869184 | 8589934591 | 34359738367 | |
| 31周目 | -17179869184 | -4294967296 | 8589934591 | |
| 32周目 | -4294967296 | 2147483647 | 8589934591 | |
| 33周目 | -4294967296 | -1073741824 | 2147483647 | |
| 34周目 | -1073741824 | 536870911 | 2147483647 | |
| 35周目 | -1073741824 | -268435456 | 536870911 | |
| 36周目 | -268435456 | 134217727 | 536870911 | |
| 37周目 | -268435456 | -67108864 | 134217727 | |
| 38周目 | -67108864 | 33554431 | 134217727 | |
| 39周目 | -67108864 | -16777216 | 33554431 | |
| 40周目 | -16777216 | 8388607 | 33554431 | |
| 41周目 | -16777216 | -4194304 | 8388607 | |
| 42周目 | -4194304 | 2097151 | 8388607 | |
| 43周目 | -4194304 | -1048576 | 2097151 | |
| 44周目 | -1048576 | 524287 | 2097151 | |
| 45周目 | -1048576 | -262144 | 524287 | |
| 46周目 | -262144 | 131071 | 524287 | |
| 47周目 | -262144 | -65536 | 131071 | |
| 48周目 | -65536 | 32767 | 131071 | |
| 49周目 | -65536 | -16384 | 32767 | |
| 50周目 | -16384 | 8191 | 32767 | |
| 51周目 | -16384 | -4096 | 8191 | |
| 52周目 | -4096 | 2047 | 8191 | |
| 53周目 | -4096 | -1024 | 2047 | |
| 54周目 | -1024 | 511 | 2047 | |
| 55周目 | -1024 | -256 | 511 | |
| 56周目 | -256 | 127 | 511 | |
| 57周目 | -256 | -64 | 127 | |
| 58周目 | -64 | 31 | 127 | |
| 59周目 | -64 | -16 | 31 | |
| 60周目 | -16 | 7 | 31 | |
| 61周目 | -16 | -4 | 7 | |
| 62周目 | -4 | 1 | 7 | ここでpo(1)が調べられる。trueなので次は-4と1の間でw |
| 63周目 | -4 | -1 | 1 | |
| 64周目 | -1 | 0 | 1 | |
| 65周目 | 0 | 0 | 1 | ここで lo+1 == hi になるのでhiの値である1を返して終了。なんと正解ではないか |
無限ループになる例
{5, 6, 10, 1, 1, 2, 2, 1, 10, 4, 9, 5, 6, 7, 3}, {6}, {20LL}*2
| lo | mi | hi | 備考 | |
|---|---|---|---|---|
| 1周目 | 1 | -4611686018427387904 | 9223372036854775807 | |
| 2周目 | 1 | -2305843009213693951 | -4611686018427387904 | |
| 3周目 | 1 | -1152921504606846975 | -2305843009213693951 | |
| 4周目 | -1152921504606846975 | -1729382256910270463 | -2305843009213693951 | |
| 5周目 | -1152921504606846975 | -1441151880758558719 | -1729382256910270463 | |
| 6周目 | -1441151880758558719 | -1585267068834414591 | -1729382256910270463 | |
| 7周目 | -1441151880758558719 | -1513209474796486655 | -1585267068834414591 | |
| 8周目 | -1513209474796486655 | -1549238271815450623 | -1585267068834414591 | |
| 9周目 | -1513209474796486655 | -1531223873305968639 | -1549238271815450623 | |
| 10周目 | -1531223873305968639 | -1540231072560709631 | -1549238271815450623 | |
| 11周目 | -1531223873305968639 | -1535727472933339135 | -1540231072560709631 | |
| 12周目 | -1535727472933339135 | -1537979272747024383 | -1540231072560709631 | |
| 13周目 | -1535727472933339135 | -1536853372840181759 | -1537979272747024383 | |
| 14周目 | -1536853372840181759 | -1537416322793603071 | -1537979272747024383 | |
| 15周目 | -1536853372840181759 | -1537134847816892415 | -1537416322793603071 | |
| 16周目 | -1537134847816892415 | -1537275585305247743 | -1537416322793603071 | |
| 17周目 | -1537134847816892415 | -1537205216561070079 | -1537275585305247743 | |
| 18周目 | -1537205216561070079 | -1537240400933158911 | -1537275585305247743 | |
| 19周目 | -1537205216561070079 | -1537222808747114495 | -1537240400933158911 | |
| 20周目 | -1537222808747114495 | -1537231604840136703 | -1537240400933158911 | |
| 21周目 | -1537222808747114495 | -1537227206793625599 | -1537231604840136703 | |
| 22周目 | -1537227206793625599 | -1537229405816881151 | -1537231604840136703 | |
| 23周目 | -1537227206793625599 | -1537228306305253375 | -1537229405816881151 | |
| 24周目 | -1537228306305253375 | -1537228856061067263 | -1537229405816881151 | |
| 25周目 | -1537228306305253375 | -1537228581183160319 | -1537228856061067263 | |
| 26周目 | -1537228581183160319 | -1537228718622113791 | -1537228856061067263 | |
| 27周目 | -1537228581183160319 | -1537228649902637055 | -1537228718622113791 | |
| 28周目 | -1537228649902637055 | -1537228684262375423 | -1537228718622113791 | |
| 29周目 | -1537228649902637055 | -1537228667082506239 | -1537228684262375423 | |
| 30周目 | -1537228667082506239 | -1537228675672440831 | -1537228684262375423 | |
| 31周目 | -1537228667082506239 | -1537228671377473535 | -1537228675672440831 | |
| 32周目 | -1537228671377473535 | -1537228673524957183 | -1537228675672440831 | |
| 33周目 | -1537228671377473535 | -1537228672451215359 | -1537228673524957183 | |
| 34周目 | -1537228672451215359 | -1537228672988086271 | -1537228673524957183 | |
| 35周目 | -1537228672451215359 | -1537228672719650815 | -1537228672988086271 | |
| 36周目 | -1537228672719650815 | -1537228672853868543 | -1537228672988086271 | |
| 37周目 | -1537228672719650815 | -1537228672786759679 | -1537228672853868543 | |
| 38周目 | -1537228672786759679 | -1537228672820314111 | -1537228672853868543 | |
| 39周目 | -1537228672786759679 | -1537228672803536895 | -1537228672820314111 | |
| 40周目 | -1537228672803536895 | -1537228672811925503 | -1537228672820314111 | |
| 41周目 | -1537228672803536895 | -1537228672807731199 | -1537228672811925503 | |
| 42周目 | -1537228672807731199 | -1537228672809828351 | -1537228672811925503 | |
| 43周目 | -1537228672807731199 | -1537228672808779775 | -1537228672809828351 | |
| 44周目 | -1537228672808779775 | -1537228672809304063 | -1537228672809828351 | |
| 45周目 | -1537228672808779775 | -1537228672809041919 | -1537228672809304063 | |
| 46周目 | -1537228672809041919 | -1537228672809172991 | -1537228672809304063 | |
| 47周目 | -1537228672809041919 | -1537228672809107455 | -1537228672809172991 | |
| 48周目 | -1537228672809107455 | -1537228672809140223 | -1537228672809172991 | |
| 49周目 | -1537228672809107455 | -1537228672809123839 | -1537228672809140223 | |
| 50周目 | -1537228672809123839 | -1537228672809132031 | -1537228672809140223 | |
| 51周目 | -1537228672809123839 | -1537228672809127935 | -1537228672809132031 | |
| 52周目 | -1537228672809127935 | -1537228672809129983 | -1537228672809132031 | |
| 53周目 | -1537228672809127935 | -1537228672809128959 | -1537228672809129983 | |
| 54周目 | -1537228672809128959 | -1537228672809129471 | -1537228672809129983 | |
| 55周目 | -1537228672809128959 | -1537228672809129215 | -1537228672809129471 | |
| 56周目 | -1537228672809129215 | -1537228672809129343 | -1537228672809129471 | |
| 57周目 | -1537228672809129215 | -1537228672809129279 | -1537228672809129343 | |
| 58周目 | -1537228672809129279 | -1537228672809129311 | -1537228672809129343 | |
| 59周目 | -1537228672809129279 | -1537228672809129295 | -1537228672809129311 | |
| 60周目 | -1537228672809129295 | -1537228672809129303 | -1537228672809129311 | |
| 61周目 | -1537228672809129295 | -1537228672809129299 | -1537228672809129303 | |
| 62周目 | -1537228672809129295 | -1537228672809129297 | -1537228672809129299 | |
| 63周目 | -1537228672809129297 | -1537228672809129298 | -1537228672809129299 | |
| 64周目 | -1537228672809129297 | -1537228672809129297 | -1537228672809129298 | lo=hi+1;以後永遠にこのまま |
| 65周目 | -1537228672809129297 | -1537228672809129297 | -1537228672809129298 | |
| 66周目 | -1537228672809129297 | -1537228672809129297 | -1537228672809129298 | |
| 67周目 | -1537228672809129297 | -1537228672809129297 | -1537228672809129298 |
教訓
二分探索のupper/lower boundsがおかしいコードを撃墜する際は要注意。
区間 [1, LONG_LONG_MAX] で二分探索したらいけない理由は、1のケースを拾いそこねるからではなく、(1+LONG_LONG_MAX)/2 は負数になるので負の領域を含めてぐるんぐるんと探索しに行くこと、しかもそれでもほとんどのテストケースが通るので気づきにくいが、場合によっては無限ループに陥ること。
