2008年02月10日
TCO08 Qual 2
- 2008-02-10 (Sun)
- 一般
500点問題にバグを埋め込んだ．青くなってしまった．だめだこりゃ．
250点問題：ある点から右にある最も近いインターバルの始点を求めて最小のやつを取るのみ．間違えられない．
500点問題：DP．辞書順最小のための優先順を間違った．
1000点問題：長方形の演算を繰り返して最後に足し合わせる．プログラム書き終わらなかった．
追記：1000点問題書き終わったのをPracticeに投げたら通った．例外処理が面倒なので，とりあえず入力されうる長方形の最大サイズの真っ白な長方形を用意．そのうえで，入力された長方形の四辺の直線で下にある長方形を全部切断し，切断された長方形のタイリング（2x2ブロックの塗りわけ16種類）を更新していく．細分化に最適化を入れないと間に合わないかと思ったけどナイーブな実装で間に合った．まあ，細分化された長方形の最大数が10000程度なので問題なかったと．もう少しアルゴリズムの確定が速ければ間に合ったかもなぁ．
- Comments: 0
- TrackBack (Close): -