2015-02-02から1日間の記事一覧
問題 整数N,Kが与えられる。 次の条件を満たす文字列が作れる場合、そのような文字列の一つを返す。なければ空文字を返す。 ・文字長はN ・各文字はAまたはBのどちらか ・i 考え方 memo[i][j][k]:=文字長iで、Bをj個含み、(i,j)のペア数がk個になっている文…
問題 N人いて、a番の人よりb番の人の方が順位が高い、という情報がM個与えられる。 1番の人の考えられる最高順位は? 考え方 ハッシュに1を入れておいて、aの情報にハッシュに入っている番号が該当すれば、bをハッシュに追加。 これで、ハッシュは1よりも順…
問題 N人とK席があり、各人は順番に以下のルールによって席に座る。 ・i番目の人はp[i]の確率で「空いていれば座る」、(1-p[i])の確率で「両隣に人がいなければ座る」 ・どちらも満たせない場合は、座らない 空いている席数の期待値を求める。 考え方 空いて…