TCO2012 2B

参加記録

華麗に0完

300:
0〜N-1と1〜Nを間違えた。

550:
開いてない

900:
開いてない



300

class BlurredDartboard {
public:
  int minThrows(vector <int> ps, int P)
  {
    const int z = count(ps.begin(), ps.end(), 0);
    const int mx = *max_element(ps.begin(), ps.end());

    set<int> visible;
    for (int i = 0; i < (int)ps.size(); ++i) {
      if (ps[i]) visible.insert(ps[i]);
    }

    vector<int> u;
    for (int i = 1; i <= (int)ps.size(); ++i) {
      if (visible.count(i)) continue;
      u.push_back(i);
    }
    int sum = accumulate(u.begin(), u.end(), 0);

    const lli inf = 1LL << 59;
    lli a = inf;
    lli b = inf;
    lli c = inf;

    if (mx) {
      a = (P / mx) + (bool)(P % mx);
    }

    if (z) {
      int Q = P;
      b = (Q / sum) * z;
      Q %= sum;
      for (int i = 0; 0 < Q; i = (i + 1) % u.size()) {
        Q -= u[i];
        ++b;
      }
    }

    if (z && mx) {
      if (mx * z < sum) {
        c = (P / sum) * z;
        P %= sum;
      } else {
        c = P / mx;
        P %= mx;
      }

      int x = (P / mx) + (bool)(P % mx);
      int y = 0;
      for (int i = 0; 0 < P; i = (i + 1) % u.size()) {
        P -= u[i];
        ++y;
      }
      c += min(x, y);
    }

    return min(a, min(b, c));
  }
};