Processing math: 100%

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

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