206.1

SRM

昔やろうと思って放置していたのをちょっとばかり...。どうやら古いSRMはどんどん消えていく模様。最近のが残っていても一回見た問題ばかりなんだよなぁ...。

250

長文でグダグダ書いてありますが...。5枚のカードのうち3枚と4枚のカードのうち2枚を選択して、5枚のカードのうちでカードの中に重複がなくて8以下のカードからなるものを作る。複数ある場合には、大きい順に並べたときに、最初に異なるカードが小さいものを選択する。という問題。


長い文章に書いてある通りに実装してください。

500

長方形の中に壊れている場所がいくつか与えられるので、壊れていない長方形領域で最大のものを答えよという問題。


最初、計算量のオーダーを見積もってみたところO(N^5)になりそうだったので、さすがに無理だろうと思い、長方形領域として可能なものを全部覚えておいて、中に点が来たら4つに分割するという方針を選択。点の処理順序をいじってみたり、可能な領域の最大値の下限を見積もって、それ以下の長方形は捨てたりと最適化してみたものの、全然ダメだった。


実際には、すべての可能な長方形領域を計算して、その中に一つも破損している点がないものをチェックすれば良いという、最初のO(N^5)のアルゴリズムで良かったらしい。


sxは0と破損点のx座標+1。exは破損点のx座標と全体の幅。yについても同様。破損点がdpで与えられるとする。

for(int a : sx) {
  for(int b : ex) {
    if( b <= a ) { continue; }
    for(int c : sy) {
    CHECK:
      for(int d : ey) {
        if( d <= c ) { continue; }
        for(Point p : dp) {
          if( a <= p.x && p.x < b && c <= p.y && p.y < d ) { continue CHECK; }
          // ここで大きさなどをチェック
        }
      }
    }
  }
}

O(N^5)ではあるけれど100Mステップくらいの実行で終わるので、さほど苦にならない。実際にはsxとexおよびsyとeyをマージして、細かいことを気にしないで良さそうなルーチンにしたので、16倍くらい遅かったけれど、それでもギリギリ通った。


長方形の重なり合わせなどの、複数長方形を扱うケースにおいては、あり得るx座標とy座標の値について全部検査して、実際に起こらないものは除外、起こり得るものは詳細に評価、という方法が安全なのかも知れない。ただし長方形の数が50程度くらいなら。もっと多い場合はどうすればいいのだろう？

1000

時間切れで、やっていない。