差分
このページの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 |
| ===区間より左のスライムの考察=== | ===区間より左のスライムの考察=== | ||
| 行 49: | 行 49: | ||
| 😄 😄 | 😄 😄 | ||
| + | | ||
| 初手で選ばれたとき | 初手で選ばれたとき | ||
| 😄 😄 | 😄 😄 | ||
| + | ↓ | ||
| + | 😄 😄 | ||
| + | | ||
| いくつか合成されてから選ばれたとき | いくつか合成されてから選ばれたとき | ||
| ・ | ・ | ||
| + | ↓ | ||
| + | 😄< | ||
| よって $i$ が小さい方から、$d_i$ の総実現値への寄与回数を計算して、その結果を $R_i$ として記録しておくことで、動的計画法的に計算できる。 | よって $i$ が小さい方から、$d_i$ の総実現値への寄与回数を計算して、その結果を $R_i$ として記録しておくことで、動的計画法的に計算できる。 | ||
