差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:contest_history:atcoder:2020:0725_m_solutions2020 [2020/07/31] – [解法] ikatakosprogramming_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倍、ベゾスの約75倍)+つまり、80日間で $2^{40} \times 1000 \simeq 10^{15}$ で1000兆円にもなる!(アメリカの国家予算の約2倍、ベゾスの約63倍)
  
 逆に言うと、$DP[i日目][j株所持] = 所持現金の最大値$ というようなDPを作ってしまうと、爆発的に $j$ が増え、TLEする。(制約が小さいので騙されがち) 逆に言うと、$DP[i日目][j株所持] = 所持現金の最大値$ というようなDPを作ってしまうと、爆発的に $j$ が増え、TLEする。(制約が小さいので騙されがち)
行 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.txt · 最終更新: 2020/08/05 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0