409.1

難易度が異常に高かった気がしたが、簡単な問題に手を出していなかっただけな気もする...。

250

ある文字列群を含む文字列のうち、文字列群のi番目が存在する位置Piがj番目が存在する位置Pjと比べて、i

600

nCk通りのテストをちょうど均等に分割できるm人以下の最大人数を答えよ、という問題。

nCkを割り切る最大のm以下の数を求めるわけなので、m以下の数を取り敢えず順に素因数分解してみる。必要な素数の回数が余っているかどうかをnCkについて計算すれば良い。アルゴリズムは簡単だけれど、実装が煩雑というか、真面目に素数を数えないと時間がかかり過ぎてしまうという問題。

900

長方形の領域について、任意の二点を選び、その二点で指定される矩形の中に色を塗る。この作業をk回繰り返す時に、塗られるマスの数の期待値を求めよ、という問題。

各マスの塗られる確率を求めて合計すればおしまい。各マスが塗られる確率は、二点で行が指定され、かつ列も指定される確率Pを求めて、1-(1-P)^kだそうです。