SRM280 に挑戦．今年，最後の SRM になります．思えば今年の後半は，TopCoder で楽しませてもらいました．いまや，2 週間に一度ほどの「趣味」です．

CompletingBrackets (code)

250 点問題． " ]][][]][ "のように閉じ括弧・開き括弧のみを含んだ文字列が与えられます．この文字列の最初・または最後に，できるだけ最小限の" ] "または " [ " を与えて，ちょうど括弧が対応するように文字列を完成させその文字列を返す問題です．例の場合は， 最初に " [ "を 3 個，最後に" ] "を 1 個加えた，" [[[]][][]][] "が正解になります．

これまでは 250 点問題は，何も考えずにただ実装ということが多かったいのですが，今回は一瞬，どうしたらよいかわかりませんでした．「まずい」と思いましたが，力任せに「うまくいくであろう」方法でなんとか仕上げました．はっきりいって根拠なしでしたが，手元で試した限りでは，あらゆるケースで問題がなかったので，そのまま Submit しました．

GridCut (code)

500 点問題． 幅 (width) cm x 高さ (height) cm の紙 があります．紙には，方眼紙のように 1cm 間隔で格子状に線が引いてあるとします．この紙をはさみを使って，n セルだけ面積を残して切り取りたいとします．最低，何 cm はさみで紙を切る必要があるでしょうか？という問題です．はさみは格子状の線に沿ってしか使用できません．ななめにきってはだめです．

図のような，5 x 10 の紙の場合，

• 10 セルだけ残すときは，左の赤のラインが最小の長さです．答えは 5
• 18 セルだけ残すときは，左の緑のラインが最小の長さです．答えは 6

アルゴリズムの知識というよりは，論理的思考力を問われる問題です．いわゆる小学生でもその気になれば解ける問題です．散々，悩んだあげく，とりあえず提出しました．

．．ですが，Level 3 問題があまりに手がでなかったのであきらめて，Level2 問題を見直していたところ，バグにきずいて，再提出しました．再提出するとポイントは 30%のペナルティが与えられます．

「n」 セル残す というのは，「 width * height - n 」セル残すということと同じことなんですね．．．それをまったく考慮していなかったため，それに対応させました．

DrawPlanar

1100 点問題．いつもの「1000 点」じゃなくて，「1100 点」ってだけで，もう恐ろしさ満点です．まったくお手上げでした． さすがに，正解できた人は，Division1 304 人中 3 人だけでした． (Problem Detail)

結果

今回は，チャレンジタイムでは，GridCut の問題で，(100, 100, 9001) という入力でチャレンジしまくりました．自分がミスっていたところは，きっと他人もミスっているに違いないと勝手に思い込んで．手当たり次第，チャレンジして，12 チャレンジ，8 個撃墜しました．

System Test の結果です． ( Room Statistics )

チャレンジしまくった結果です．自分も同じ問題を，チャレンジされ撃墜されたというオチまでついています． square * (square-1) のケースを考慮していませんでした．．

レーティングは 1520 -> 1630 と上昇しました．