差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/14] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/14] – [解法] ikatakos | ||
---|---|---|---|
行 22: | 行 22: | ||
==== 解法 ==== | ==== 解法 ==== | ||
- | 解説pdfの確率を利用する方法がよりスマートだが、一応自力解法をメモしておく。 | + | 解説pdfの確率を利用する方法がよりスマート。自分は別の考え方で解いて、複雑なだけで特に優れている点は無いが、一応メモしておく。 |
出力すべき値はややこしい書き方をされているが、要はスライムを選ぶ順番が全部で $(N-1)!$ 通りあり全て等確率なので、全ての選び順においての移動距離の総和を求めればよい。 | 出力すべき値はややこしい書き方をされているが、要はスライムを選ぶ順番が全部で $(N-1)!$ 通りあり全て等確率なので、全ての選び順においての移動距離の総和を求めればよい。 | ||
行 35: | 行 35: | ||
------------------------ | ------------------------ | ||
x 1 | x 1 | ||
- | d 2 | + | d 2 |
===区間より左のスライムの考察=== | ===区間より左のスライムの考察=== | ||
行 84: | 行 84: | ||
今までは $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!}$ を加算していけば、毎回ループを回さなくても計算できる。 | ||
===区間より右のスライム=== | ===区間より右のスライム=== |