226.1

落ち着いて英語を読む練習。この頃の問題は簡単な気がしてならない。

250

ある点からある直線までのマンハッタン距離を求めよ、という問題。

目的の直線にはx軸ないしy軸に沿ってしか近付けない。どちらかの軸に沿って少し近づいた場合、元の問題を縮小した形になる。このことから、問題をある程度縮小する形にするまでの最短路が分かれば、それと同じことを繰り返すことで最短路が得られる。突き詰めると、常にx軸ないしy軸に沿って行動するのが最短である、ということになる。(進む軸を変える間もなく問題は縮小される、という状況を考えれば良い。)

500

スロットマシンで、固定のスコアの目と、可変スコアの目が一つ与えられる。スロットの各列が独立で、問う確率に発生するとき、可変スコアが何点以上であれば期待値は1を超えるか答えよ、という問題。可変スコアの目が実現できないときは-1を返しておく。

まず固定スコアからの期待値を計算する。固定スコアの期待値が1を超えているならば、可変スコアは実現できる必要はない。そうでなければ、可変スコアの確率を求めて、残りの期待値を実現させれば良い。

800

N問の問題のそれぞれの正答率が与えれるので、K問正解した人のスコアを、平均点のときには1000、標準偏差だけずれているときは300、という形で正規化して答えよ、という問題。

N問のうちC問正解の人の割合をDPして求める。後はそれから平均と標準偏差を求めて、1000+300*(スコア-平均)/標準偏差、を返すだけの問題。