差分
このページの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日間で 240×1000≃1015240×1000≃1015 で1000兆円にもなる！（数兆株の株式を発行できる会社とは一体） | + | つまり、80日間で 240×1000≃1015 で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 | ||
