差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/16] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/17] – ikatakos | ||
---|---|---|---|
行 119: | 行 119: | ||
$i+j+k$ が小さい方からループを回せばボトムアップでもできるし、このように+1、-1が入り交じってどの値から先に埋めれば良いか混乱する場合は、メモ化再帰でもよい。 | $i+j+k$ が小さい方からループを回せばボトムアップでもできるし、このように+1、-1が入り交じってどの値から先に埋めれば良いか混乱する場合は、メモ化再帰でもよい。 | ||
- | リスト参照が多いため、Python, | + | === 言語事情 === |
+ | リスト参照が多いため、Pythonだと制限時間が厳しい。 | ||
+ | |||
+ | 普段あまり意識しないが、Pythonでも変数のデータ型の概念はしっかりとある。 | ||
+ | 変数を扱うたびに「この変数の型はなんぞや」のチェックから入るのが、Pythonが便利な反面、遅い一因となっている。 | ||
+ | |||
+ | PyPyでは、事前の型推論によりチェックを一部省略することで高速化を図っている部分があるが、処理の中でintもfloatも取り得る変数にしてしまうとその推論が上手く働かない。 | ||
+ | |||
+ | 今回のように小数が入るとわかっている場合は、初期化する値も小数にしておけば、よりPyPyの恩恵を享受できる、とのこと。 | ||
+ | |||
+ | * [[https:// | ||
<sxh python> | <sxh python> | ||
- | # TLE | ||
from collections import Counter | from collections import Counter | ||
行 131: | 行 140: | ||
total = c1 + 2 * c2 + 3 * c3 | total = c1 + 2 * c2 + 3 * c3 | ||
c23 = c2 + c3 | c23 = c2 + c3 | ||
- | dp = [[[0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)] | + | dp = [[[0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)] # ←ここを0で初期化するとTLE |
for k in range(1, n + 1): | for k in range(1, n + 1): |