結果

問題 No.2528 pop_(backfront or not)
ユーザー SSRSSSRS
提出日時 2023-11-04 03:08:23
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 1,631 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 5,332 KB
実行使用メモリ 4,368 KB
最終ジャッジ日時 2023-11-04 03:08:25
合計ジャッジ時間 1,280 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

k の左にある個数と右にある個数しか見なくてよいので、dp[i][j]=(目標の要素の左に i 個、右に j 個ある状態から目標の要素だけ残す操作列の個数) とすると、
初期値: dp[0][0]=1
遷移:
dp[i][j] += dp[i-2][j]*(i-1)(i-2)/2
dp[i][j] += dp[i][j-2]*(j-1)(j-2)/2
dp[i][j] += dp[i-1][j-1]*((i-1)(j-1)+1)
答え: dp[k][2N-k]

x>0 のとき dp[0][x]=dp[x][0]=0 なので、dp[0][_], dp[_][0] を無視して dp[1][1]=1 から始めることにする。
dp’[i][j]:=dp[i][j]/((i-1)!(j-1)!) と定める。遷移の両辺を (i-1)!(j-1)! で割り、dp’ に言い換えると以下のようになる:
初期値: dp’[1][1]=1
遷移:
dp’[i][j] += dp’[i-2][j]/2
dp’[i][j] += dp’[i][j-2]/2
dp’[i][j] += dp’[i-1][j-1]
dp’[i][j] += dp’[i-1][j-1]/((i-1)(j-1))
答え: dp’[k][2N-k]*(k-1)!(2N-1-k)!
(i,j) をグリッド上に置き、i が増える方向を「下」、j が増える方向を「右」と呼ぶ。遷移を上から順に a,b,c,d と呼ぶ。
ある点から「遷移 a,b,c のいずれかを選んで行う」ことは、
「以下の 2 つのうち 1 つを選ぶことを 2 連続で行う:
下に 1 進み、1/√2 倍する。
右に 1 進み、1/√2 倍する。
」
と同等になるので、この 2 つと遷移 d を行えると言い換える。ただし、これら 2 つを連続で行わせるため、遷移 d は i+j が偶数のときしか行えないとする。DP の遷移は以下のようになる。
dp’[i][j] += dp’[i-1][j]/√2
dp’[i][j] += dp’[i][j-1]/√2
dp’[i][j] += dp’[i-1][j-1]/((i-1)(j-1)) (i+j は偶数)
0