Zenn
🕌

ABC223 C - Doukasen C++解答例

2021/10/18に公開
C++
競技プログラミング
AtCoder
競プロ
tech

AtCoder Beginner Conteset 223 C - DoukasenをC++で解きます。

問題

問題文をAtCoderのページより引用します。

問題文

N本の導火線を一直線に接着したものがあります。左からi本目の導火線は長さがA_{i}cmで、1秒あたりB_{i}cmの一定の速さで燃えます。

この導火線の左端と右端から同時に火を付ける時、2つの火がぶつかる場所が着火前の導火線の左端から何cmの地点か求めてください。

制約

  • 1 \leq N \leq 10^{5}
  • 1 \leq A_{i}, B_{i} \leq 1000
  • 入力はすべて整数

解答例

2つの火はいつ衝突する？

まず、2つの火がぶつかる時間を求めます。それぞれの導火線が燃える速さが既にわかっているので、2つの火がぶつかる時間さえ分かれば、その場所を計算することができるからです。

さて、導火線の両端から火を付けたとき、導火線が燃え尽きるのにかかる時間(これをSとおきます)は、どちらか一方の端から火を付けたときに導火線が燃え尽きる時間の丁度半分になります。

というわけで、まずはどちらか一端から火を付けたときに導火線が燃え尽きるのにかかる時間を求めましょう。これをTとおきます。
与えられた条件より、i本目の導火線が燃え尽きるのにかかる時間t_{i}は、t_{i} = A_{i} \div B_{i}となります。
従って、これらの総和がTになります。

T = \sum^{N}_{i = 1} t_{i} = \sum^{N}_{i = 1} (A_{i} \div B_{i})

Tが求まったので、両端から火を付けたときに火がぶつかるときの時刻S = \frac{T}{2}とすることができます。

火がぶつかったとき、どこにいるかを求める

次に、火を付けてからS = \frac{T}{2}秒後に左から付けた火がどこに入るのかを求めます。これがそのままこの問題の答えになります。

これを求めるにはいくつか方法がありますが、今回は制約がぬるい(N \leq 10^{5})ので貪欲に求める方法を用います。

今、火がぶつかる時刻Sがわかっていて、各導火線が燃えるのにかかる時間t_{i}がわかっています。
そのため、距離をA_{i}だけ増やしていきつつ\frac{T}{2}からt_{i}を引けるだけ引いていき、最後に余った端数時間とその時点でのB_{i}を掛けた値を距離に加算すれば答えを求めることができます。

実装例

文章だけで説明すると分かりづらいので実際のコードを示します。

c.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <cmath>
 
int main() {
  // 入力受け取り
  int64_t N;
  std::cin >> N;
  std::vector<int64_t> A(N);
  std::vector<int64_t> B(N);
  for (int64_t i = 0; i < N; i++) {
    std::cin >> A.at(i) >> B.at(i);
  }
 
  // 各導火線が燃え尽きる時間t_i
  std::vector<double> time(N);
  for (int64_t i = 0; i < N; i++) {
    time.at(i) = static_cast<double>(A.at(i)) / B.at(i);
  }
 
  // どちらか一端から火を付けたときに全ての導火線が燃え尽きる時間T
  double T = std::accumulate(time.begin(), time.end(), 0.0);
 
  // 2つの火がぶつかる時刻S
  double S = T / 2;
  // 火がぶつかったときの左端からの距離
  double distance = 0.0;
 
  // インデックスカウント変数
  int64_t i = 0;
  // Sから引けるだけtime.at(i)を引いていく
  // Sからtime.at(i)を引くことができるということは、
  // 導火線iは全て燃え尽きるということである
  while (S - time.at(i) > 0) {
    // Sからt_iを引く
    S -= time.at(i);
    // 距離を加算する
    distance += A.at(i);
    i++;
  }
  // 最後の導火線は余った時間だけ燃える
  distance += S * B.at(i);
 
  // 解答出力
  std::cout << std::fixed << std::setprecision(10) << distance << std::endl;
 
  return 0;
}

実際に提出したコードはこちら。

Discussion