288.1

確率は全然分からない...。

250

3次元上にあるいくつかの点から三つ選んで、特定の条件を満たす三角形の面積の最大値を答えよ、という問題。

外積を使って面積を計算しましょう。

450

ある整数Nを、f(K)=(1からKまでの和)としてg(X)=(f(1)からf(X)までの和)とするとき、最小何個のgの和で表現することができるか答えよ、という問題。

Nを表現するのにM[N]個必要だとすると、N+g(i)を表現するにはM[N]+1個、というDPをするだけ。文章読むだけの問題。

1000

ある国が隣国を順次攻めていって、敵国をすべて制圧できる確率の最大値を求めよ、という問題。兵力Aの状態で兵力Bの国を攻める場合、(A*A)/(A*A+A*B+B*B)の確率で敵国の兵力を1減らし、そうでない場合自国の兵力が1減るとする。隣接している国の関係と、倒す必要のある国の情報、各国の兵力が与えられる。

単純に考えると、自国の残存兵力と、制圧済みの国を状態としてDPすれば良さそう。状態が合流する可能性があるときにどちらを取るのかが不明。ダイクストラで、終了状態まで回してやるのが正解なのかとも思ったけれど、それをすると都合のいい結果を優先的に選択しそうな気がしてダメそう。(結局制圧状況を考えると、残存数に応じた確率のベクトルが状態になるので、二つの状態のどちらがいいのかが単純には比較できないという問題がある。ベクトルにならないように計算すればいいらしいが...。)