徘徊迷路yukicoderyukicoderはとても久しぶりに解きました。最近競プロの進捗を全く生やせていないので、「3月中に毎日1問解いて黄色になろう!」キャンペーンを始めます。ことで毎日こちらの更新を目指しますが、次の水木金とサークルの大会があるので無理です。問題概要ランダムウォークするので、Tターン後に丁度ゴールにいる確率を求めよ。yukicoder解説ネックは完全にTで、1ターンずつシミュレーションは無理です。こいつが2nの形だった時を考えると、nxt[i][j][a][b]:(i,j)→(a,b)に移動する確率とか置いておくと、こいつが2nターン後の遷移状態を示しているとき(最初はn=0で、通常のシミュレーションと同じ)、nxt[i][j][a][b]=nxt[i][j][x][y]*nxt[x][y][a][b]とかすると2n+1ターン後の状態が分かるわけです。これを使うと、1回のループでTの一番上のビットをO(R3C3logT)で消せます。これをTのビットが立っている個数≦logT回繰り返すので、全体としてO(R3C3(logT)2)で解けます。最大ケースを当てはめるとこれで間に合いますね。まあnxtは前計算出来て、それでlogTが一つ落とせるんですが、どうでもいいので残してます。これで解けるはずなんですが、この計算ではものすごく浮動小数点の計算を行っているので、誤差がエグイです。いう訳で適切にepsを突っ込む必要があるんですが、これが難しい。足す位置をnxt←nxt2とret←tmp、つまり更新後の配列を移動させるタイミングに指定します(これは完全に適当)。このタイミングだと最大T回epsを足していると考えられるので、許容範囲をepsだけで超えないように10-6×10-8より小さい10-15で計算をしています。ここで考えたのは2点で、epsがあまりにも小さくなり過ぎないことそれなりにepsを足していることです。doubleを使いましょう。0;}感想アルゴリズム自体は簡単だったので、自分にとっては完全な誤差ゲーでしたね...もう1、2問★3をやってみて、簡単そうなら★3.5に行こうと思います。...「3月中に毎日1問解いて黄色になろう!」キャンペーン11問目。...「3月中に毎日1問解いて黄色になろう!」キャンペーン8問目。Bernoulli「3月中に毎日1問解いて黄色になろう!」キャンペーン5問目。日)ネットの海に生息するらしいバーチャルグソクムシ。競プロとCTFをメインに、たまにEsolangを混ぜます。(7)月別アーカイブリンクGitHubはてなブログをはじめよう!Hyogaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。