差分
このページの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倍、ベゾスの約75倍） | + | つまり、80日間で $2^{40} \times 1000 \simeq 10^{15}$ で1000兆円にもなる！（アメリカの国家予算の約2倍、ベゾスの約63倍） |
| 逆に言うと、$DP[i日目][j株所持] = 所持現金の最大値$ というようなDPを作ってしまうと、爆発的に $j$ が増え、TLEする。（制約が小さいので騙されがち） | 逆に言うと、$DP[i日目][j株所持] = 所持現金の最大値$ というようなDPを作ってしまうと、爆発的に $j$ が増え、TLEする。（制約が小さいので騙されがち） | ||
