差分
このページの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})$ | ||
