339.1

実装ゲー多めセット。

250

バスの路線がいくつか与えられるので、貪欲にバスに乗り、一駅で降りる、という処理を繰り返して、開始点に戻りたい。いつ戻るか答えよ、という問題。

やるだけ。タイムアウトが凄く早いのでどう実装しても通りそうな感じ...。

450

賭け金を1からはじめて、負けるたびに倍にしていくという処理をお金があるだけ繰り返すとき、初期金額と目的金額、ゲームの最大回数と勝つ可能性が与えられるので、目的金額に到達する確率を求めよ、という問題。

DPするだけ。目的金額と初期金額の差分から、何回勝てば良いかが分かる。今までのゲームの回数と、勝った回数を状態にする。(中途半端に負けている状態については考慮したくないので、ループを回してしまう。)目的金額に到達したらゲームをしないのに注意。

1000

2^N人のプレイヤーがトーナメントを行う。各プレイヤーには順番でシードが指定されていて、自分のシードをSとするとS-(S*C)^(1/2)の以上シードのプレイヤーには勝つ可能性があるとする。このとき優勝し得るプレイヤーのシード値の最大値を答えよ、という問題。

あるプレイヤーが優勝可能なら、それよりもシードが低いプレイヤーも優勝可能なので、バイナリサーチが可能。ということでせいぜいN人について判定すれば良い。判定方法は、自分一人からはじめて、勝てる一番低いシードの人を追加する。(これを決勝戦と思うことにする。)これら二人について、勝てる一番低いシードの人を追加する。(これを準決勝と思うことにする。)というのを繰り返し、全員が入ればそういうトーナメントが可能なので優勝可能。

このとき、勝てる一番低いシードの人を効率良く求めるようにするために、各プレイヤーについて、次にまだ登場していないプレイヤーのシード値を覚えておいて、それを適宜更新するようなデータ構造を用意してしまえばおしまい。(もしかするといらないかも。)