AGC002 Box and Ball

所見

知識はいらないから100%思いついてね、という問題だとほかに持ち出せる知見が無いので解けてもおいしくない。

問題概要

N個の箱があり、1-Nの番号が振られており、1番の箱には赤玉が入っている。2-N番目の箱には白玉が入っている。
操作(xi, yi)を以下のように定義する。
・xiの箱からyiの箱へ玉をランダムに一つ移動する。
(x1, y1)から(xM, yM)のM個の玉操作を終えたとき、赤玉が入っている可能性のある箱の個数を求めよ。

取った方針

赤玉が入っている可能性のある箱から玉を移動させると移動先に赤玉が入る可能性がある。一度でも赤玉が入った箱は最後に赤玉が入っている可能性がある。
ただし、一度赤玉が入った後箱の中の玉の数が0個になってしまうとその箱に赤玉が入っている可能性はない。
よって、箱に入っている玉の数と赤玉が入っているかどうかを持ってシミュレーションすればO(M)で解ける。

正しい方針(解説の方針)

同上

得られた知見

・特になし

解くのに必要な要素

・一度赤玉が入った箱は最後まで赤玉が入っている可能性がある
・一度赤玉が入ってもその後にその箱の玉が0個になってしまうと赤玉が入っている可能性はなくなる(当然その後入る可能性はある)

周辺調査によって得られた知見

なし