No.1501 酔歩

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 :

遭難者 / テスター :

nok0

10 ProblemId : 6270 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-05-08 01:20:03

$1$ から $N$ までの番号がついた $N$ 個のマスと $1$ つの駒があります。始め、駒はマス $K$ に置かれています。

各マスに整数が書かれており、マス $i$ には $A_i$ が書かれています。

あなたは次の行動を駒がマス $1$ かマス $N$ に到達するまで繰り返します。

駒がいるマスを $j$ とする。空箱の中に $A_{j-1}$ 個の赤いボールと $A_{j+1}$ 個の青いボールを入れ、ボールをよくかき混ぜた後に無作為に $1$ つ取り出す。もし赤のボールが取り出されたなら駒をマス $j-1$ に、そうでないなら駒をマス $j+1$ に動かす。

最終的に駒がマス $N$ にある確率を求めてください。ただし、この確率は有理数になることが証明できます。

(21:40追記) 使われる箱は各行動ごとに空にします。

$1\le K\le N\le 10^5$

$1\le A_i\le 10\ (1\le i\le N)$

入力は全て整数

$N\ K$
$A_1\ A_2\ \ldots\ A_N$

求める確率は互いに素な整数 $p,q$ $(0\le p,0< q)$ を使って $\displaystyle\frac pq$ と表すことができます(この $p,q$ は一意に定まります)。この $p$ と $q$ を / で区切って出力してください。

ただし、確率が $0$ の時は 0 とのみ出力してください。

3 2
1 1 2

2/3

$\displaystyle\frac13$ の確率でマス $1$ に行き、 $\displaystyle\frac23$ の確率でマス $3$ に行きます。

どちらに行ってもマス $1$ かマス $N=3$ に到達するため、答えは $\displaystyle\frac23$ です。

5 1
1 2 3 4 5

既にマス $1$ に到達しています。

7 3
1 1 2 2 1 2 2

1/2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。