249.1

350

長さNのテーブルに団体客が連続した領域になるように着席する。団体の大きさと確率が与えられ、それに応じて客が訪れる。客は着席可能な任意の場所に等確率で着席する。このとき、最初に座れない団体が発生したときの、テーブル占有数の期待値を求めよ、という問題。

すべての着席状態がどれくらいの確率で発生するかをDPで求め、その状況でどれくらいの率で座れなくなるかを計算すればおしまい。

500

チャットに同時にログインしたN人について、ユーザAがユーザBからのメッセージを何回読んだかが与えられる。このとき、可能なログアウト順の中で、辞書順で最初のものを答えよ、という問題。

あるユーザのメッセージを読んだ数が、そのままログアウト順になる。これが競合しているならば、どの順番もあり得ない。そうでなければ、最小なユーザから順にログアウトしたはずなので、それを答えればおしまい。

850

凸包の面積を求めよ、という問題。