差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:contest_history:atcoder:2020:0725_m_solutions2020 [2020/07/31] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0725_m_solutions2020 [2020/08/05] (現在) – [解法] ikatakos | ||
---|---|---|---|
行 35: | 行 35: | ||
これをシミュレートすると通る。 | これをシミュレートすると通る。 | ||
- | 恣意的なテストケースでは、株価が '' | + | 意図的なテストケースでは、株価が '' |
つまり、80日間で $2^{40} \times 1000 \simeq 10^{15}$ で1000兆円にもなる!(アメリカの国家予算の約2倍、ベゾスの約63倍) | つまり、80日間で $2^{40} \times 1000 \simeq 10^{15}$ で1000兆円にもなる!(アメリカの国家予算の約2倍、ベゾスの約63倍) | ||
行 288: | 行 288: | ||
* $PLANES[u][2][v]=$ 方向が $u=\{U, | * $PLANES[u][2][v]=$ 方向が $u=\{U, | ||
- | そして、方向の組み合わせ6組に対して、衝突する全ての飛行機の時間を算出していく。 \\ | + | そして、方向の組み合わせ6組に対して、衝突しうる全ての飛行機の衝突までの時間を算出していく。 \\ |
- | たとえば →と↓ の組なら、$x-y$ が同じになるので、$PLANES[R][2]$ と $PLANES[D][2]$ を使う。 | + | たとえば →と↓ の組なら、$x-y$ が同じになるものが衝突するので、$PLANES[R][2]$ と $PLANES[D][2]$ を使う。 |
両者に共通する $v$ があれば、そのリスト内の飛行機は衝突の可能性がある。 | 両者に共通する $v$ があれば、そのリスト内の飛行機は衝突の可能性がある。 | ||
行 316: | 行 316: | ||
- | 計算量は、PLANES内に情報が分散するものの、 | + | 計算量は、$N$ 機の飛行機の情報がPLANES内に分散するものの、 |
* ソートする必要のあるリストの要素数の総計...$O(N)$ → 計算量 $O(N \log{N})$ | * ソートする必要のあるリストの要素数の総計...$O(N)$ → 計算量 $O(N \log{N})$ |