TopCoder SRM 521 (Div 1) - simezi

249.07 / Opened / Unopened
0チャレンジ

132位 1999 -> 2027
500解けないのはなんだかなあorz
というか最近問題セットが酷い気が。

'('または')'からなる文字列が与えられる。
括弧の対応が正しくなるように'('または')'を補うとき、補う最小の文字の数を求めよ。

一文字ずつ見ていって、'('がきたら深さ+1,')'がきたら深さ-1
深さ0で')'がきたらその手前に'('をgreedyに補ってやる。

Div2 Easyより簡単じゃないのかこれ。
サンプル合った。提出。

n個の点の集合Pが与えられる。
このPの部分集合Aのうち、次の条件を満たすものの個数を求めよ。

Aの点が全て、辺がXY軸に平行で長さがnの正方形の内部に含まれ、かつP-Aの点は全て正方形に含まれないような正方形が存在する。ただしnlow≦n≦nhighを満たす必要がある。

最初問題文が意味不明で15分くらい悩む。もっとか。
サンプルからなんとか理解しようとするも詰まる。

途中でclarが来た。
そのころにようやく意味をつかむ。

んでどうやるのか。
答えの型がlong longで、n≦40だから半分全列挙とか結構怪しいんだけど……
そういう方針でしばらく考える。

上手く行かない。
なんか3次元のSegment Treeを使う？とか意味のわからないことを考え始める。

だめっぽい。

……ていうか、集合ってかなり限定されるよなこれ。
正方形の左下と右上の範囲を（点と点の間に）適当に決めうちして、正方形が書けるかをチェックして、あと点が正方形に入ってるかを見るだけでいいのでは。

座標圧縮とかして書いてみる。
時間足りない。intermission中にコンパイル、サンプル実行。
なんかふつうに間違っている。

チャレンジ中に2回も鯖から落ちた。回線クソすぎてストレスが溜まる。
しかもその間に二人おとされとる。
落とせそうなのもなく、みんなのコードを眺めて終了。

250通った。けど流石に問題も酷いし自分も酷い。
最近練習頑張ってる割に成果でなくてつまらないなあ。