386.1

SRM

手袋買ったので慣らし運転。

250

文字列集合が与えられる。文字列の特定の位置を比較することで全部の文字列を区別することを考える。比較する位置は必要十分でなくてはならない。このとき、比較する最小の文字数と最大の文字数を答えよ、という問題。


文字位置の集合を状態として、区別可能かどうかを調べる。部分集合で可能ならば常に可能だが、必要十分ではないので除外する。後は適当に全部計算してやるだけ。

500

二次元平面状にいくつか点がある。これらを多角形で囲んでやりたい。できるだけ面積最小にせよ、という問題。


多角形といいつつ三角形なので、適当な三点を選んで三角形を作って足していく。既に取り込んだ点を状態としてDPしてやるだけ。三角形の面積は外積でも使ってやれば出てくる。

1000

ある地点から別の地点に行きたいとき、他に二地点間を移動しようとしている人達とぶつからないように移動することを考える。最短距離を移動するが、どう通るかはランダムであるとして、その都度できるだけ回避したときの衝突確率を答えよ、という問題。


愚直にシミュレーションすれば通るらしい。(というか通ってたコードがあったのでやる気失せた。)