521.1

250と1000が簡単でがっかりされたセット。

250

括弧からなる文字列が与えられるので、整合性が取れるように括弧を追加する最小の個数を答えよ、という問題。

ありがち。やるだけ。開いた数だけ閉じているかチェックして、余分に閉じたら開いておいて。

500

点集合が与えられるので、軸平行な正方形で、切り取ることができる点集合の部分集合は何通りあるか答えよという問題。正方形の大きさとして可能な範囲が指定される。

問題を今理解した。

(追記)登場する座標を考えると、点の数だけしか各軸に出現しない。これらから各軸について二つ選んで長方形を作り、その隣にはみ出さないような正方形の可能な大きさの範囲を求める。これが指定された正方形に合致するならば、その長方形内に含まれる点のみを切り取ることが可能になる。(ちなみに外側は無限に取れるので、遥か遠めに点を追加してもいいし、例外処理をしてもいい。)これ以外の方法で切り取れるものは存在しないので、後はこれらをハッシュにでも突っ込んでおけば、全部でいくつか分かる。0個の点を切り取るということはできないので、それだけ除去すること。

1000

レンガを4つ真ん中に穴が開くように並べて1段作り、それを反転させた形で次の段を作っていく。下の二つがないと上に積めないとして、N段レンガを積むときに積む方法は何通りあるか答えよ、という問題。

状態遷移をうまく圧縮して行列乗算するだけ。基本的には積みかけのレンガは6個までで、新たに積んだら一番下の段が完成してしまうので、残りを状態と思う、といったような感じで行列を書きあげるだけ。状態数は10個あれば十分だけれど、最終的には2個とかにもできるらしい。