SRM397

賞金付きで人が多かったせいか、サーバの不調で20分遅く始まる。

250

高々長さが8の配列に対して、k個の連続する区間を反転させるという操作を繰り返したとき、最短何回でソートされた状態にできるかを返せという問題。
状態空間が8!=40320しかないことに気づけばあとは幅優先するだけの問題。

500

mod 1000000007を求めよという問題。ただしkは50以下でnは10^9以下。
を二項展開して辺々足すとS(n,k)をS(n,k-1)からS(n,1)で表せるので、式に従って計算するだけ、途中割り算が入るのが面倒かと思ったけど10^9 * (10^9)^50 = 10^459でBigIntegerで計算しても数が500桁程度しか行かないので全部BigIntegerで計算した。

1000

青色と赤色の二種類のレーダがそれぞれn,m個(n,m <=50)平面上にある。今レーダの有効範囲をR(<=1000)以下のr以下に自由に設定できるとき、レーダの有効範囲(複数のレーダで重複する場合でも面積を重複して数える)の最大面積を求めよという問題。ただしレーダは起動するかしないかを自由に選べ、また違う色のレーダの有効範囲が重なることは許さない。
rを固定したとき、距離が2r以下の異なる色のレーダ対は両方つけることができない。両方つけれない時にエッジがあると思うと二部グラフの最大独立集合を求める問題になる。また、つけれる個数が同じならばrはできるだけ大きくした方がよく、その境界部分はn*m個ぐらいしかなくすべての境界部分について調べればよい。250と500に時間をかなり割いてしまったので、二部グラフマッチングのコードどこだっけとか思っているうちに終わった。