差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/12] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/14] – [解法] ikatakos | ||
|---|---|---|---|
| 行 22: | 行 22: | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| - | 解説pdfの確率を利用する方法がよりスマートだが、一応自力解法をメモしておく。 | + | 解説pdfの確率を利用する方法がよりスマート。自分は別の考え方で解いて、複雑なだけで特に優れている点は無いが、一応メモしておく。 |
| - | 求められる値は（期待値×パターン数）だが、スライムを選ぶ順番が $(N-1)!$ 通り、その全てにおいての移動距離の総和を求めればよい。 | + | 出力すべき値はややこしい書き方をされているが、要はスライムを選ぶ順番が全部で |
| + | この「全ての選び順における移動距離の総和」を「総実現値」と呼ぶことにする。 | ||
| - | 1回の選び方ごとに総和を計算するのは難しいので、各隣接スライム間の距離を「区間」として、その区間が何回足されることになるかを計算する。 | + | 1回の選び方ごとに移動距離を計算するのは難しいので、各隣接スライム間の距離を「区間」として、その区間が総実現値に何回足されることになるかを計算する。 |
| スライム $i～i+1$ の区間を $d_i$ と表す。 | スライム $i～i+1$ の区間を $d_i$ と表す。 | ||
| 行 34: | 行 35: | ||
| ------------------------ | ------------------------ | ||
| x 1 | x 1 | ||
| - | d 2 | + | d 2 |
| ===区間より左のスライムの考察=== | ===区間より左のスライムの考察=== | ||
| - | 区間 $d_i$ を通る可能性のあるスライムは、$1～i$ に限られる。まずはこの $i$ 個のみの、全ての選び順における通過数の総和を考える。 | + | 区間 $d_i$ を通る可能性のあるスライムは、$1～i$ に限られる。まずはこの $i$ 個のみの、全ての選び順における通過回数を考える。 |
| スライム $i$ が選択された時に、はじめて $d_i$ を1匹のスライムが通過する。 | スライム $i$ が選択された時に、はじめて $d_i$ を1匹のスライムが通過する。 | ||
| 行 45: | 行 46: | ||
| その時に区間の左側に残ったスライムの数を $k$ とすると、先ほどの1回に加え、あといくつのスライムが $d_i$ を通るか？ | その時に区間の左側に残ったスライムの数を $k$ とすると、先ほどの1回に加え、あといくつのスライムが $d_i$ を通るか？ | ||
| - | これは $k$ が等しければ（$i$ など他の値に依らず）同じになり、初期状態から区間 $k$ を通過するスライムの数と一致する。（ただし $k=0$ のとき 0） | + | これは $k$ にのみ依存し、初期状態から区間 $k$ を通過するスライムの数と一致する。（ただし $k=0$ のとき 0） |
| 😄 😄 | 😄 😄 | ||
| + | | ||
| 初手で選ばれたとき | 初手で選ばれたとき | ||
| 😄 😄 | 😄 😄 | ||
| + | ↓ | ||
| + | 😄 😄 | ||
| + | | ||
| いくつか合成されてから選ばれたとき | いくつか合成されてから選ばれたとき | ||
| ・ | ・ | ||
| + | ↓ | ||
| + | 😄< | ||
| - | よって、$i$ が小さい方からその区間を通るパターン数を計算して、その結果を $R_i$ として記録しておくことで、動的計画法的に計算できる。 | + | よって $i$ が小さい方から、$d_i$ の総実現値への寄与回数を計算して、その結果を $R_i$ として記録しておくことで、動的計画法的に計算できる。 |
| ==kを固定== | ==kを固定== | ||
| - | スライムを選ばれた順に並べると、 | + | スライムを左から選ばれた順に並べ、スライム $i$ が選ばれたときに左に $k$ 個残っている場合に、$d_i$ が何回通過されるか（総実現値への $d_i$ の寄与回数）を考える。 |
| |-------------------| | |-------------------| | ||
| 行 64: | 行 71: | ||
| | | ||
| - | スライム $i$ 以外の $i-1$ 個の左右への振り分け方は ${}_{i-1}C_k$ | + | スライム $i$ 以外の $i-1$ 個の左右への振り分け方は ${}_{i-1}C_k$ |
| - | 先に選ばれたスライムの並び順は $(i-k+1)!$ | + | 左側の（先に選ばれた）スライムの並び順は $(i-k+1)!$ |
| - | この時の通過数は、残る $k$ 個の通過数に加え、$k$ 個の選び順のパターンの数だけ" | + | 右側のパターン数は |
| + | 区間 | ||
| これらを掛け合わせて、$\displaystyle {}_{i-1}C_k(i-k+1)!(R_k+k!) = \frac{(i-1)!}{k!}(R_k+k!)$ となる。（あくまで $d_i$ より左のスライムのみに限定した場合） | これらを掛け合わせて、$\displaystyle {}_{i-1}C_k(i-k+1)!(R_k+k!) = \frac{(i-1)!}{k!}(R_k+k!)$ となる。（あくまで $d_i$ より左のスライムのみに限定した場合） | ||
| 行 74: | 行 82: | ||
| ==kの総和== | ==kの総和== | ||
| - | $k=0～i-1$ までの値を取るので、この総和を取ったものが $d_i$ の総通過数となる。（あくまで $d_i$ より左の…以下略） | + | 今までは $k$ を固定して考えていたが、$k=0～i-1$ までの値を取るので、この総和を取ったものが $d_i$ の寄与回数となる。（あくまで $d_i$ より左のみ） |
| - | $\displaystyle \sum_{k=0}^{i-1}\frac{(i-1)!}{k!}(R_k+k!)$ | + | $\displaystyle \sum_{k=0}^{i-1}\frac{(i-1)!}{k!}(R_k+k!) |
| - | これは、新しい $R_i$ が求められるたびに $\displaystyle \frac{R_i+i!}{i!}$ を加算していけば、毎回 | + | これをこのまま計算すると各 $i$ の中で $k$ のループが回るので $O(N^2)$ だが、$\sum$ 内は $k$ のみに依存するので、 |
| + | 新しい $R_i$ が求められるたびに $\displaystyle \frac{R_i+i!}{i!}$ を加算していけば、毎回ループを回さなくても計算できる。 | ||
| ===区間より右のスライム=== | ===区間より右のスライム=== | ||
| - | さて、これまでで、区間より左のスライムの選び順が決まった。 | + | さて、これまでで区間より左に限定したスライムの寄与回数が決まったが、ここに区間より右のスライムの選び方を乗じる必要がある。 |
| 区間より右の $N-i$ 個のスライムは、いつ選ばれようと、区間 $d_i$ の加算数に影響することは無い。 | 区間より右の $N-i$ 個のスライムは、いつ選ばれようと、区間 $d_i$ の加算数に影響することは無い。 | ||
| - | つまり、区間より左 $i$ 個の既に固定された選び順の、$i+1$ 箇所の好きな位置に、どのような順番で挟み込んでもよい。 | + | つまり、区間より左 $i$ 個の選び順の、$i+1$ 箇所の好きな位置に、どのような順番で挟み込んでもよい。 |
| v v v v v | v v v v v | ||
| 行 97: | 行 106: | ||
| $R_0=0$ として、$\displaystyle dp[i]=\sum_{k=0}^{i}\frac{R_k+k!}{k!}$、つまり $dp[0]=1$ とする。 | $R_0=0$ として、$\displaystyle dp[i]=\sum_{k=0}^{i}\frac{R_k+k!}{k!}$、つまり $dp[0]=1$ とする。 | ||
| - | 左の区間から、通過総数を計算していく。 | + | 左の区間から、その区間の総実現値を計算していく。 |
| - | 区間 $d_i$ の答えへの加算は、$d_i \times (i-1)! dp[i-1] \times \frac{N!}{i!}$ となる。 | + | 区間 $d_i$ の総実現値への寄与は $\displaystyle |
| - | $dp[i]=dp[i-1]+\frac{(i-1)! dp[i-1] + i!}{i!}$ として次の区間の計算に備える。 | + | 同時に |
| <sxh python> | <sxh python> | ||
