286.1

SRM

JavaのStringは遅いけど、StringBufferを使えばいいってもんじゃないよ、というセット。...違うか。

250

特定の模様を作ると点数がもらえるビンゴで、現在の状況が与えられるので、次の数字によって得られる点数の期待値を求めよ、という問題。


現在の状態から次の一個で作れるやつは、残りの弾数分の1の確率でできる。これを合計するだけ。

600

N枚のカードがあって、Gというカードならそのまま次のプレイヤーに、Rというカードならば逆順で次のプレイヤーに、Bというカードなら自分が抜けて次のプレイヤーに、ということをカードがなくなるまでやる。自分の番でカードがなくなっているプレイヤーの勝ちとする。カードの中身が分かっていて順番だけ分からないとき、勝つ確率が一番高いのはどのプレイヤーか答えよ、という問題。


状況をそのままDPするだけ。現在のプレイヤーは0番目として、残っているカードの分類とプレイヤーの数がステート。同じ確率のときに微妙な誤差が出ることがあるので、ちゃんとイプシロンを計算するのを忘れないようにしないといけないのが100点分だろうか？

1000

二次元の文字配列の原点から等間隔で無限に文字を選択する。間隔は、原点を除くKxKからgcdが1になるように選んぶ。このような選択のうち、特定の文字列が出現するものは何通りあるか答えよ、という問題。


目標の文字列長は2500文字程度でその半分くらいの個数がある。その中から文字列のマッチングをするだけ。文字列でやると思いので、文字の配列を作って、一番出現頻度の少ない文字を起点にしてマッチングをやるようにしたらギリギリ間に合った。気合い定数倍最適化...。


普通に賢い文字列マッチングアルゴリズムを作成すればいいんだと思う。そもそももっと簡単なのかも知れないけれども...。