差分
このページの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/21] (現在) – ikatakos | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======Educational DP Contest I, | + | ======Educational DP Contest I,J, |
| [[https:// | [[https:// | ||
| 行 61: | 行 61: | ||
| ===== J - Sushi ===== | ===== J - Sushi ===== | ||
| - | [[https:// | + | [[https:// |
| ==== 問題 ==== | ==== 問題 ==== | ||
| 行 105: | 行 105: | ||
| &+& \frac{j}{N} DP[i+1][j-1][k] \\ | &+& \frac{j}{N} DP[i+1][j-1][k] \\ | ||
| &+& \frac{k}{N} DP[i][j+1][k-1] \\ | &+& \frac{k}{N} DP[i][j+1][k-1] \\ | ||
| - | &+& 1 \\ | + | &+& 1 |
| + | \end{eqnarray} | ||
| + | \begin{eqnarray} | ||
| DP[i][j][k] &=& \frac{N}{i+j+k}(\frac{i}{N} DP[i-1][j][k] \\ | DP[i][j][k] &=& \frac{N}{i+j+k}(\frac{i}{N} DP[i-1][j][k] \\ | ||
| &+& \frac{j}{N} DP[i+1][j-1][k] \\ | &+& \frac{j}{N} DP[i+1][j-1][k] \\ | ||
| &+& \frac{k}{N} DP[i][j+1][k-1] \\ | &+& \frac{k}{N} DP[i][j+1][k-1] \\ | ||
| &+& 1) \\ | &+& 1) \\ | ||
| - | DP[i][j][k] | + | |
| \end{eqnarray} | \end{eqnarray} | ||
| 行 117: | 行 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 | ||
| 行 129: | 行 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): | ||
| 行 156: | 行 167: | ||
| * $K$ 個の石が積まれた山があり、2人が交互に取っていく | * $K$ 個の石が積まれた山があり、2人が交互に取っていく | ||
| - | * 一度に取れる石の数は、数列 | + | * 一度に取る石の数は、$a_1, |
| * これ以上操作を行えない状態で渡された方の負け | * これ以上操作を行えない状態で渡された方の負け | ||
| * 先手と後手、どちらが必勝か | * 先手と後手、どちらが必勝か | ||
| 行 162: | 行 173: | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| - | 必敗パターンというか、「山がある個数で渡されたら、どう取ろうと、その後相手が適切に取ることでまた必敗パターンが渡されることが繰り返され、最終的に負ける」状態がある。 | + | 必敗パターンがある。必敗パターンというのは、「山がある個数で渡されたら、どう取ろうと、（その後相手が適切に取ることで）また必敗パターンが渡され続け、最終的に負ける」状態を指す。 |
| + | |||
| + | 例えば0個はこれ以上操作できないので必敗パターンである。 | ||
| 初期状態で必敗パターンなら後手必勝、それ以外は先手必勝である。 | 初期状態で必敗パターンなら後手必勝、それ以外は先手必勝である。 | ||
| 行 175: | 行 188: | ||
| === 遷移 === | === 遷移 === | ||
| - | 山が $i$ 個の状態から、$a_1, | + | 必敗かどうかは、相手に必敗パターンを渡すことが可能かどうかで決まる。 |
| + | |||
| + | * 山が $i$ 個の状態から、$a_1, | ||
| + | * どの取り方をしても「必敗パターンでは無い状態」にしか出来なければ、必敗パターン | ||
| 言い換えると、$DP[i-a_1], | 言い換えると、$DP[i-a_1], | ||
| 行 181: | 行 197: | ||
| K=20, A={3, 4, 10} | K=20, A={3, 4, 10} | ||
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | ||
| - | | + | |
| + | (x: 必敗 | ||
| 20は必敗パターンでは無いので、先手必勝 | 20は必敗パターンでは無いので、先手必勝 | ||
| - | * 13は、4個取って残り9個にしたら、相手が[3 or 4]個取って[6 or 5]個で渡されても、次に4個取ることで必ず勝てる | + | * 一度に3個、4個、10個のいずれかの個数取れる |
| - | * 16は、取れる選択肢(13, | + | * 12は、4個取って残り8個にして相手に渡せば、相手が[3 or 4]個取って[5 |
| + | * 16は、取れる選択肢(13, | ||
| + | * どう取っても、上記のように相手が必ず勝てる手がある | ||
| <sxh python> | <sxh python> | ||
| 行 241: | 行 260: | ||
| $DP[l][r]$ があった時、先頭と末尾のどちらを取るかは、以下の大きい方となる。 | $DP[l][r]$ があった時、先頭と末尾のどちらを取るかは、以下の大きい方となる。 | ||
| - | * $-DP[l-1][r]+a_l$ | + | * $-DP[l+1][r]+a_l$ |
| * $-DP[l][r-1]+a_{r-1}$ | * $-DP[l][r-1]+a_{r-1}$ | ||
