386.1

時間が後5分あればなぁ...。

250

データベースのprimary keyの集合となりうるもので、最小のサイズと最大のサイズを答えよという問題。各要素はcharである。

全ての組み合わせを、部分集合がprimary keyにならないように計算するだけ。

500

与えられた点集合から凸方を任意個作り、全ての点を包含するようにした時にできる凸方の面積の和の最小値を答えよという問題。

実は全て三角形の和になるので、うまいこと作成した後、DPで和を計算すれば良いらしい。

1000

エージェントが数名いる迷路を、エージェントにつかまらないように抜ける。エージェントは目的地まで最短路のパスを全て同じ確率で移動する。こちらは、エージェントが一番いないであろう場所を毎ターンごと選びながら進む。このときにエージェントにつかまる確率を答えよ、という問題。

取り敢えず全てのエージェントについて、最短遷移パスを全て列挙する。自分が次に行きたい場所のうち、エージェントにつかまる確率が最小の場所を選ぶ。移動する時に、エージェントのパスのうち、つかまるパターンを除去したうえで、次の場所を選ぶ。これを目的地に到達するまで繰り返す。

いわゆる実装系で、終わった後にコンパイル通るように修正して、コンストラクタでフィールド初期化の時にうっかり型名つけてしまって別変数になっている部分を修正したら通った。残念...。