Codeforces #Pi Div2 D: One-Dimensional Battle Ships

久しぶりのブログだけどのんびりやっていこう。

問題

１次元バトルシップをする。アリスは大きさaのバトルシップをk個おき、ボブはm回の攻撃を行う。しかしアリスは攻撃があたってもすべて"miss"と嘘をつく。ボブは何回目の攻撃でアリスが嘘をついていると突き止められるか答えよ。

解法

ある点を攻撃した時、その左と右で最も近いすでに攻撃済みの点(l, r)を効率よく探す必要がある。そこでボブの攻撃を巻き戻すことを考える。まず各攻撃点に(l, r)の情報をもたせる。そこから巻き戻すたびにl点、r点の(l, r)情報を更新しながらフィールドに存在しうるバトルシップの数を計算していく。バトルシップがk個以内に収まった時のループ回数が答えるべき値となる。

int n, k, a, m;
int x[200005], y[200005];

int main(void) {
  cin >> n >> k >> a;
  cin >> m;
  rep(i, m) cin >> x[i], y[i] = x[i];

  //番兵
  y[m] = 0;
  y[m + 1] = n + 1;
  sort(y, y + m + 2);
  map<int, pair<int, int>> lr;
  lr[0] = make_pair(0, y[1]);
  REP(i, 1, m + 1) lr[y[i]] = make_pair(y[i - 1], y[i + 1]);
  lr[n + 1] = make_pair(y[m], n + 1);
  
  ll ship = 0; 
  rep(i, m + 1) ship += (lr[y[i]].second - y[i]) / (a + 1);
  
  if (ship >= k) {
    cout << -1 << endl;
    return 0;
  }

  for (int i = m - 1; i > -1; i--) {
    int l, r;
    l = lr[x[i]].first;
    r = lr[x[i]].second;
    int bef = (x[i] - l) / (a + 1) + (r - x[i]) / (a + 1);
    int aft = (r - l) / (a + 1);
    lr[l].second = r;
    lr[r].first  = l;
    ship += aft - bef;
    if (ship >= k) {
      cout << i + 1 << endl;
      break;
    }
  }

  return 0;
}