競プロTweetPocketchokudai先生(@chokudai)の固定ツイートに記述されているネタが古い問題の解法解説記事が無いっぽいので、書いてみます。前回に引き続き確率の問題ですね。自分も解けているのか自信が無いので、ここの解法はおかしいとか、別の解法を思いついたという方は@furuya1223までリプライくれると嬉しいです。問題は以下の通りです。「「入れ替わってるー!?」」ぼく「このように、N個の要素から二つを選びswapする、という行為をM回繰り返した時、元々あった場所に存在する要素の個数の期待値を出力せよ。出力の相対誤差は10^-6までは許容される。N,M≦10^12面倒だから誤差は出ないものとして良い。O(M)等の線形オーダーが間に合いません。聞かれているのは、「元の位置にある要素の個数の期待値」です。これは、各要素について「最終的に元の位置にあれば1、そうでなければ0」となるような確率変数X_iを考えると、元の位置にある要素がk個の場合に$$\sum_{i=1}^NX_i=k$$となります。期待値には線形性が成り立つので、和は外に出せます。和の期待値は期待値の和。期待値の線形性は、確率変数が独立でない場合にも成立します。今、全てのX_iは特に振る舞いに違いが無い(どの位置の要素も対等にswapされうる)ので、E[X_i]は全てのiで等しいです。ここで、X_iは、「要素iが最終的に元の位置にあれば1、そうでなければ0」となる確率変数なので、その期待値はすなわち「要素iが最終的に元の位置にある確率」になるはずです。X_iは{0,1}のみを取り、E[X_i]=1*P(X_i=1)+0*P(X_i=0)=P(X_i=1)となるからです。その確率を求めましょう。要素1つを固定して考えるので、以降は要素に対してiという添字を使いません。先頭要素でも末尾要素でも何でもいいですが、1つのみを考えます。n回swapを行った後に、注目要素が元の位置にある確率をp_nとおきます。p_nに関する漸化式を考えます。注目要素が1回のswapに選ばれる確率は、N_C_2通りの組合せのうちN-1通りなので、(N-1)/N_C_2=2/Nです。n回時点で要素が元の位置にある場合、swapに選ばれると確実に別の位置に移動します(確率2/N)。選ばれなければ、元の位置のままです(確率1-2/N)。n回時点で要素が元の位置にない場合、swapで{現在位置,元の位置}の組合せが選ばれたときのみ、元の位置に戻ります(確率1/N_C_2=2/(N(N-1)))。状態遷移イメージ従って、以下の漸化式が成り立ちます。)}$$これを解きます。)^n$$となります。)^n$$が得られます。)^M$$となります。この値は、M乗の計算にO(logM)で計算できる高速な累乗法(名称あるのかな?)を用いることで、全体でO(logM)で解けるので、満点制約でも十分間に合いますね。漸化式を解きたくない場合は、適当なタイミングで行列累乗を用いることでもO(logM)で解けますね。0\end{pmatrix}$$の第1要素として得られます。A^Mを高速な累乗計算で計算すれば、O(logM)です。1\end{pmatrix}$$として、上記と同じように行列累乗で解くことができます。N<10^12なので、行列累乗だと極端に小さい値2/(N(N-1))があって誤差がきつそうですね。)^M$$をよく見ると、M→∞で期待値が1個になるようですね。これは、ぐちゃぐちゃに混ぜると、ある要素が配置される位置がN通り全て同様に確からしくなるので、p_∞=1/Nになることから理解できますね。M=0の場合に、Nによらず期待値がNになることが分かります(ただし0^0=1)。swapする前には全要素が元の位置にあります。N=3のとき、(M>0のとき)期待値が常に1になっていますね。...}となるようです。面白いと思ったけどそうでもなさそう。N=2のときは、右の項が負数の累乗になるので、正負がMに応じて入れ替わるようになりますね。期待値は2,0,2,0,...を繰り返します。2要素だと毎回swapが同じ組になるので、明らかですね。コードは実装していません。オンラインジャッジがあれば実装したいですね。間違いとか別解とかがあれば教えてください。Codefor...記事を読む怠惰でもできる精進こんばんは、ふるやん(@furuya1223)です。●「先輩いきなりですね。■「え、そんなことないよ。F「リボンたたみ」黒魔術解法こんにちは。ICPC国内予選参加記で書いた通り、F問題の自分の解法を書きます。本戦E「ショートコーディング」こんばんは。DDCCの予選通過のメールも無事に届き、2週連続で東京に行くことになりました。●「...記事を読むABC133の初見実況動画を投稿しましたこんばんは、ふるやん(@furuya1223)です。参加したとき...記事を読む競技プログラミングの始め方こんにちは、ふるやん(@furuya1223)です。コメントをキャンセルメールアドレスが公開されることはありません。*サイト次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。クリエイティヴなブログ.当サイトでは利便性向上や閲覧の追跡のためにGoogle・他連携サービスによるCookieが使用されています。サイトの閲覧を続けた場合Cookieの使用に同意したことになります。information.。