hotpepsiの練習帳

SRM 521 Div2

22:38

やっと復習が追いついた。

Easy (250) RedAndGreen

問題

• RとGのどちらかで塗られたパネルが1列に並んでいる。
• RをGに、または、GをRに塗る操作により、Gの右側にRがない状態にしたい。
• RをGに、またはGをRにする操作の最小回数を求める。

方針

• R->GとG->Rのどちらが最適かわからない
• ちょっと考えてわからなかったので、メモ化再帰した
• 最終的な配置をR=0個からR=N個まで仮定して、ループでまわせばよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_521/RedAndGreen.cpp

Medium (500) MissingParentheses

問題

• 開き括弧 ( か 閉じ括弧 ) のいずれかからなる文字列がある。
• 括弧が正しく閉じていない個数を求める。

方針

• 左から一個ずつ見ていく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_521/MissingParentheses.cpp

Hard (1000) SquaredSubsets

問題

• XY平面上に点集合Pがある。
• 整数nが与えられる。
• 大きさnの正方形に収まるPの空でない部分集合がいくつあるかを答える。
• 正方形を動かしてみて、Pの含まれ方が何通りあるかということらしい。

方針

• 本番中には問題文の意味がつかめなかった
• 正方形を点の座標の右下、左上、右上、左下それぞれに、含む場合と含まない場合とで配置してみる
• 整数でループして回すだけだとサンプルが通らない
• 点の中間に配置するパターンがあるので、座標とnを2倍しておく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_521/SquaredSubsets.cpp

結果

oo- 167.36+474.46=641.82 rating 1169 -> 1194

easyに20分もかかったが、まあ通ったのでよしとする。チャレンジケースを作るまでには至らなかった。システムテストでeasyは部屋内で半分以下しか通っておらず、全体の順位も200位以上あがった。ひっかかりやすい問題だったっぽい。

mediumは、ひっかけがあるんだろうなあと思いながら素朴なコードを書いたがそのまま通った。

hardはAnalysisを参考にしつつも、理解できてないので、単純なループで書いた。なかなか通らず、0.5の意味がやっとわかった。