Hatena::Grouptopcoder

hotpepsiの練習帳

2011-10-25

SRM 521 Div2

22:38

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

Easy (250) RedAndGreen

問題

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

方針

Medium (500) MissingParentheses

問題

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

方針

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の意味がやっとわかった。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20111025