280.1

250

'['と']'からなる文字列が入力として与えられるので、それらが対応を取れるように、先頭に'['を追加し、末尾に']'を追加せよ、という問題。

取り敢えず先頭から見ていって、']'が多いようなら先頭に'['を入れ、最後に余った'['の数だけ']'を入れればおしまい。入れ子構造のある文字列をparseしたことがある人なら問題ないと思う。

500

W*Hの矩形の紙が与えられるので、面積Nの領域を切り取る際に、切断する長さの最小値を答えよ、という問題。

取り敢えず半分以上の領域を切る場合には、W*H-Nを切り取るようにしても同じ。切り取る領域が0なら切らない。WがHが1ならば1切るだけになる。

それ以外のケースについて、できるだけWをすべて使うかできるだけHをすべて使うように切ることを考えると、切る長さは高々W+1かH+1になる。(WとHを両方すべて使うような切り方は切り取る面積が半分以下になるように修正したので得をしない。)どちらも使い切らないケースでは、w*hの矩形の内部に入るように切るとき、高々w+hであることを利用して、すべての可能なwとhの値についてw*hが十分大きくなるもので、w+hが最小のものを求める。以上の値のうちで最小になるものが、最小の切り方である。

こういうのはうまく書ける気がしない。

1100

平面グラフが与えられるので、すべての点が格子点上に並ぶような平面配置について、そのグラフを含む矩形の面積の最小値を答えよ、という問題。

現実的な解法は何も浮かばない。仮に浮かんだとしてもそれが実装できる気がしない。魅力的な問題でもない...。

多分、点数NについてNxNの矩形の内部に入るようなレイアウトが可能なはずで、開始点と終了点のペアで辺を整理するとして、二辺の間で交差があるかどうかをメモしておいて、後はすべての点を開始点として位置を決めて、適当な順番で点を並べて、置けたら面積を計算して、みたいな探索を効率良くやればいいんじゃないだろうか。(もの凄く適当。最適化の段階で力尽きる。)