229.1

マラソンマッチに手を出してみたのもの、何もしないで返すルーチンと同じ程度のスコアになったのでやる気なくした。

250

10分おきに出るバスが複数路線ある。バスが出る時刻と、バス停までの時間、バスの目的地までの時間、が与えられるので、目的地に目的の時刻までにつくために可能な出発時間として一番遅いものを答えよ、という問題。

すべてのバスに乗ってみて、出発時刻を計算するだけ。フォーマットをちゃんと整えて出力しましょうね、という問題なのかも知れない。

500

商品を作るコストと、売値、作成時間が与えられるので、現在の所持金から、目的の額に達するまでの最少時間を答えよ、という問題。現在の所持金よりコストの高いものは作れない。作った商品は即座に定価で売れる。商品は同時に一つしか作れないし、途中で切り替えることもできない。

作成時間が高々10で、目的の額が100000であることから、利益のある商品を作り続けるので、高々1000000ステップやれば良い。各ステップで、すべての商品を作ってみた結果、いつにどれだけの額を持っているかが計算できるので、後は最初に目的額を超えるステップ数を求めればおしまい。

1000

N個のK文字の文字列が与えられる。このうちのいずれかが伏せられている。任意のアルファベットを選択し、それがその文字列に含まれていると、該当する場所が開かれる。どこか開かれれば継続でき、失敗すれば次のプレイヤーに交代する。この状況で2人で交互に行うとき、先手のプレイヤーが文字列を正解する確率を求めよ、という問題。各プレイヤーは最適にプレイする。

最適なプレイとは、どのプレイヤーも可能なすべての単語に含まれないアルファベットを選択することはない(無限ループしない)と仮定してやるものらしい。すべてのターンにおいてある単語に決め打って行動できるので、現状維持は不利にしかならないため。

現時点で可能な単語集合についての確率をDPで求める。単語集合に対して26文字全部試して、開く場所が同じものでグループ化する。全部開かれない、もしくは全部同じ場所が開かれるような文字は無視する。同じグループについては、サブグループになるので、既に計算されているので確率が求まる。ただし、一文字も開けないグループについては、順番が交代するので、確率は逆転する。後は各文字のうち一番勝率の良いものを選んでいけば良く、可能な単語集合が最初の入力に一致した時点での結果を返せばおしまい。