差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2020:0725_m_solutions2020 [2020/07/31] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0725_m_solutions2020 [2020/07/31] – [解法] ikatakos | ||
|---|---|---|---|
| 行 36: | 行 36: | ||
| 恣意的なテストケースでは、株価が '' | 恣意的なテストケースでは、株価が '' | ||
| - | つまり、80日間で $2^{40} \times 1000 \simeq 10^{15}$ で1000兆円にもなる！（数兆株の株式を発行できる会社とは一体） | + | つまり、80日間で $2^{40} \times 1000 \simeq 10^{15}$ で1000兆円にもなる！（アメリカの国家予算の約2倍、ベゾスの約75倍） |
| 逆に言うと、$DP[i日目][j株所持] = 所持現金の最大値$ というようなDPを作ってしまうと、爆発的に $j$ が増え、TLEする。（制約が小さいので騙されがち） | 逆に言うと、$DP[i日目][j株所持] = 所持現金の最大値$ というようなDPを作ってしまうと、爆発的に $j$ が増え、TLEする。（制約が小さいので騙されがち） | ||
| 行 148: | 行 148: | ||
| * [[https:// | * [[https:// | ||
| - | 以下の例では、$b$ を鉄道を敷設する街全体のbit集合、$v$ を縦に敷く街のbit集合、$h$ を横に敷く街のbit集合として、$v$ が $b$ で立っているbitの全部分集合を全探索している。$v$ と $b$ のXORを取ることで、補集合 $h$ が得られる。 | + | 以下の例では、$b$ を鉄道を敷設する街全体のbit集合、$v$ を縦に敷く街のbit集合、$h$ を横に敷く街のbit集合として、 |
| + | $b$ で立っているbitの部分集合を | ||
| b = 0b001101101 | b = 0b001101101 | ||
