2014年04月27日02時36分25秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．
$N$ 文字のアルファベッド小文字のみからなる文字列 $S$ が与えられる．
$S$ の中に $2$ 回以上出てくる文字について，$1$ 回目以外を全部削除する問題．
最初から見ていって，出てきた文字を覚えておいて，まだ出てきていない文字のみを連結していく．
ある整数 $k$ を言う時，
$k$ が $3$ の倍数で $5$ の倍数でないならその数を言う代わりに $\verb|Fizz|$ と，
$k$ が $5$ の倍数で $3$ の倍数でないならその数を言う代わりに $\verb|Buzz|$ と，
$k$ が $3$ の倍数かつ $5$ の倍数ならその数を言う代わりに $\verb|FizzBuzz|$ と言う．
$A$ 以上 $B$ 以下の整数を順番に言っていく時，$\verb|Fizz|$，$\verb|Buzz|$，$\verb|FizzBuzz|$ はそれぞれ何回言われるかを求める問題．
$1$ から $B$ までに言われる数から，$1$ から $A-1$ までに言われる数を引けば良い．
$1$ から $X$ までに言われる $\verb|FizzBuzz|$ の数は $\lfloor X/15 \rfloor$ だし，
$\verb|Fizz|$，$\verb|Buzz|$ はそれぞれ $\lfloor X/3 \rfloor$，$\lfloor X/5 \rfloor$ から $\verb|FizzBuzz|$ の数 $\lfloor X/15 \rfloor$ を引けば良い．
無限に長い一直線上に配置されたマスのある場所にロボットがいる．
このロボットが $N$ ステップだけ動く．
各ステップでは，左右等確率に選び，そっちに $1$ マス移動する．
ロボットが訪れるマス（初期位置も含む）の期待値を求める問題．
DPする．
状態を（現在何ステップ行ったか，ロボットが訪れた区間の幅，今ロボットはその区間の左から何マス目にいるか）と取り，その確率を計算していく．
計算時間量は $O(N^3)$．現在何ステップ行ったかは前のステップだけ覚えておけば良いので，空間計算量は $O(N^2)$ で良い．
もっと早い方法もあるが，これで十分間に合う．
Current time: 2024年05月03日18時18分12秒
Last modified: 2014年04月27日02時36分25秒 (by laycrs)
Tags: no_tags
トップページに戻る
Logged in as: unknown user (not login)