333.1

めんどいセット。

250

日付文字列がチェックサムつきで与えられるので、正しいかどうか判定せよ、という問題。

やるだけ。

500

0と1からなる文字列AとBが与えられる。S(i)を1000000個のAの後にi個のBがならる文字列として、S(1)S(2)...なる無限文字列に0がK個並ぶ最初の位置を答えよ、という問題。

AとBがどちらも1を含まないなら、先頭が該当。Aが1を含まないなら、1000000個のAの後にBをつけて足りるなら先頭、Bの後に1000000個のAの後にBを付けて足りるなら、S(2)のちょっと手前、それ以外は無理。

AAの中に入るなら最初のAの途中、ABAの中に入るなら1000000個目のAの途中。以降Bが1を含まない場合だけ、可能性があり、Bがいくつあれば足りるかを計算してやる。BがN個必要なら、AはN*1000000-1個目の途中からで、それまでにBはN*(N-1)/2個登場する。この位置を答えれば良い。

1000

バスを乗り継いでいくことを考える。バス停にバスが来るまでの時間が指定されていて、バスがそれぞれ指定された時間以内に均等な確率で到着するとして、全待ち時間が指定された値以下になる確率を求めよ、という問題。バスは高々3つ。

バスの待ち時間をA,B,Cとすると、可能な待ち時間の分布は、各辺がA,B,Cの直方体に合致する。このうち、原点からの距離が全待ち時間以内の領域に含まれる部分の体積を計算すれば良い。基本的には三角錐を足したり引いたりしてやれば面積が出るので、後は全体の体積で割るだけ。バスの台数が少ない場合は、それに合わせて次元を落とせば良い。