roiti46's blog

主に競プロ問題の解説を載せてます

Codeforces #Pi Div2 D: One-Dimensional Battle Ships

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

問題はこちら

問題

1次元バトルシップをする。アリスは大きさ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;
}

まとめ

バトルシップが隣接するのもダメだったのを見落としてバグらせてた。

注目点に左右の情報をもたせるといろいろと効率よくやれそう。

広告を非表示にする