差分

このページの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:
 これをシミュレートすると通る。 これをシミュレートすると通る。
  
-意的なテストケースでは、株価が ''100, 200, 100, 200, ...'' を繰り返したとき、2日で所持金を2倍にできる。+的なテストケースでは、株価が ''100, 200, 100, 200, ...'' を繰り返したとき、2日で所持金を2倍にできる。
 つまり、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,D,L,R\}$ であり、$x-y$ が $v$ である飛行機の $x$ 座標のリスト   * $PLANES[u][2][v]=$ 方向が $u=\{U,D,L,R\}$ であり、$x-y$ が $v$ である飛行機の $x$ 座標のリスト
  
-そして、方向の組み合わせ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})$
programming_algorithm/contest_history/atcoder/2020/0725_m_solutions2020.1596161062.txt.gz · 最終更新: 2020/07/31 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0