Ruteのプログラミング日記

競技プログラミング(AtCoder)の問題の解説や、過去問を解いた感想、また解けない過去問について共有したいと思ってます。

yukicoder 問題　"乱数サイ"

A問題のWriterをしておりました、Ruteです。

今回はA問題の作問を担当させて頂きました。

それでは早速問題から振り返っていきましょう。

問題文:

一般的に乱数サイとは

0から9までの数字がちょうど2回ずつ現れるようになっているサイコロのことをいいます。
今回は、 $0$ から $N$ までの整数がちょうど $K$ 回ずつ現れるようになっているサイコロを考えます。
(ただし、それぞれの整数が等確率で出るものとします)

このサイコロの出目の期待値を求めて下さい。

この問題の解法は２つあります。

解法１：

ans = 0とします

(0,N)で以下のループを回します。(変数をiとします)

ここで、ansに $\frac{i}{N+1}$ を足し続けます。

本来は $K$ 回足すので分子が $K$ 倍、さらに分母も $(N+1)×K$ となる必要がありますが、分子分母の $K$ の部分が消えるので、事実上は上の式を足し続ければよいです。

計算量は $O(N)$ でしょう。

Python3のコードです:

N,K = map(int,input().split())
ans = 0
for i in range(0,N+1):
ans += i/(N+1)
print(ans)

解法２：

$N = 3$ で、Kの数を増やしたとき期待値がどのようになるかを考えてみましょう。

(解法2の計算式では分子が $0$ のものは考えないことにします)

$K = 1$

$\frac{1}{4}+\frac{2}{4}+\frac{3}{4}$ = $\frac{6}{4}$ = $\frac{3}{2}$

$K = 2$

$\frac{1}{8}+\frac{1}{8}+\frac{2}{8}+\frac{2}{8}+\frac{3}{8}+\frac{3}{8}$ = $\frac{12}{8}$ = $\frac{3}{2}$

$K = 3$

$\frac{1}{12}+\frac{1}{12}+\frac{1}{12}+\frac{2}{12}+\frac{2}{12}+\frac{2}{12}+\frac{3}{12}+\frac{3}{12}+\frac{3}{12}$ = $\frac{18}{12}$ = $\frac{3}{2}$

既に気づいた方もいるかも知れませんが $K$ を変更しても期待値の総和は変化していないのです。

では次に、 $K = 3$ で、Nの数を増やしたとき期待値がどのようになるかを考えてみましょう。

$N = 1$

$\frac{1}{6}+\frac{1}{6}+\frac{1}{6}$ = $\frac{3}{6}$ = $\frac{1}{2}$

$N = 2$

$\frac{1}{9}+\frac{1}{9}+\frac{1}{9}+\frac{2}{9}+\frac{2}{9}+\frac{2}{9}$ = $\frac{9}{9}$ = $1$

$N = 3$

$\frac{1}{12}+\frac{1}{12}+\frac{1}{12}+\frac{2}{12}+\frac{2}{12}+\frac{2}{12}+\frac{3}{12}+\frac{3}{12}+\frac{3}{12}$ = $\frac{18}{12}$ = $\frac{3}{2}$

実は、答えは任意の $N$ に対して $K$ の値にかかわらず一意に定まることがわかります。よって答えは $N/2$ となり、計算量 $O(1)$ で計算することが可能です！

Python3のコードです:

N,K = map(int,input().split())
print(N/2)

(帰着させると $0$ から $N$ までのサイコロを1個振ったときの期待値を求めることになります)

(この解法を思いついた方は果たして何人いるのでしょうか....)

以上、A問題の解説でした。

難易度について、また問題の感想についてコメントなどでぜひ教えて下さい！

(コメントの一部を、Twitterで匿名で紹介するかもしれません。)