naoya_t@hatenablog

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

SRM582

久しぶりにSRMに出てみた。

Easy ("SpaceWarDiv1", 250)

二分探索が間違っている事に気づいたのに(あれ、これでも通るんだーとか思っちゃって)再提出せず

区間 [1, LONG_LONG_MAX] で二分探索したらいけない理由は、1のケースを拾いそこねるからではなく、(1+LONG_LONG_MAX)/2 は負数になる(皆さんおわかりですよね?)ので負の領域を含めてぐるんぐるんと探索しに行くこと、しかもそれでもほとんどのテストケースが通るので気づきにくいが、場合によっては無限ループに陥ること。

ACへの編集距離1。SRMはドジっ子アピールの場。

Medium ("ColorfulBuilding", 600)

開いた
なんか数え上げないといけない系
ちゃんと考えれば出来そうだけど時間(スピード)が足りない

Challenge phase & System Test

Easyで3人の撃墜ミスを誘う(たぶん答えが1になるケースを投げてくれたんだと思う→やっぱりそうだった
{1}{1}{1}は通るんだよね(これはsubmit後に自分で確かめてる)

でもまあそりゃ通らないケースもあるわけでFailed System Test

x-- 0点
黄1562→青1452\青の皆さんこんにちは/

Easy提出コード(あかんやつ)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>

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; //// ←1LLを0LLにすれば万事OK
    while (true) {
      if (lo+1 == hi) {
        return hi;
      }
      ll mi = (lo + hi)/2;
      if (po(mi)) hi = mi;
      else        lo = mi;
    }
  }
};

↑具体的には、

magicalGirlStrength: {5, 6, 10, 1, 1, 2, 2, 1, 10, 4, 9, 5, 6, 7, 3}
enemyStrength: {6}
enemyCount: {20LL}

で無限ループするのでTLEが出ます。(ちなみに欲しい答えは4LL)

詳しくは別エントリで!