naoya_t@hatenablog

いわゆるチラシノウラであります

SRM撃墜大好きっ子に贈る:二分探索問題の撃墜 〜慎重に撃墜ケースを検討すべき一例〜

SRM582 Easy(250) "SpaceWarDiv1"

問題意訳

魔法少女(複数)と敵(複数)がいる。
魔法少女は自分と同等以下の敵を倒せるが、1人倒すたびにソウルジェムが濁っていく。
敵は全て倒したいが、ソウルジェムの濁りが特定の少女に集中し魔女化してしまうのを避けるため、戦闘回数を分散したい。
最大限にうまくやったとき、ソウルジェムの濁りはどこまで抑えられるか。

※雰囲気はそんな感じだけど正確なところは原文でちゃんと読んでください。writerは準急さん(semiexp)です。

入力

{魔法少女の強さ}, {敵の強さ}, {それぞれの強さの敵が何人いるか}

出力

一番多く敵を倒した魔法少女のソウルジェムの濁り

解き方

二分探索でどうよ

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 は負数になるので負の領域を含めてぐるんぐるんと探索しに行くこと、しかもそれでもほとんどのテストケースが通るので気づきにくいが、場合によっては無限ループに陥ること。

*1:-9223372036854775808/2 = -4611686018427387904

*2:正答は4LL