Hatena::Grouptopcoder

hotpepsiの練習帳

2011-05-10

SRM 505 Div2

01:17

Easy (250) SentenceCapitalizerInator 先頭の大文字化

問題

  • 小文字の英字で、スペースとピリオドで区切られているフレーズの、先頭だけ大文字にする。

実装した内容

https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_505/SentenceCapitalizerInator.cpp

Medium (500) PerfectSequences 完全な数列

問題

  • 1つ変更することで和と積が一致するperfectな数列になるかどうかを答える

はまりポイント

  • すでにperfectな場合に、Noとしてよいのか確信が持てない
  • 積がゼロの場合に特別扱いするかどうか

実装した内容

  • (product * x) == (sum + x) であるため、x = sum / (product - 1) として求める

https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_505/PerfectSequences.cpp

Hard (900) RectangleArea 格子の数を求める

わからんのでスキップ→解き直し

問題

  • 大きさW×Hの四角形がある。
  • 四角形はN個の水平位置X[n]と、M個の垂直位置Y[m]で区切られている。
  • 位置X[i]Y[j]のサイズが既知であるかどうかが与えられる。
  • 四角形全体のサイズを既知とするための最小の質問回数を求める。

方針

  • 既知が全くなければ、縦幅+横幅-1が答え
  • YYYNNとNNYYYのような行は既知と既知をつなげてYYYYYと見なせる
  • YYYNNとNNNYYは、1回聞けば既知をつなげられる
  • というのはunion find木でいける
  • とりあえず水平方向についてそれで求める
  • 縦方向については、一つでも既知の桁があれば既知となるので、未知の行だけカウントを加算する

実装した内容

https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_505/RectangleArea.cpp

感想

ox- 232.27+255.56*0 932 -> 864

EasyとMedium/Hardの難しさがアンバランスすぎる気が。

Easyのみ通過でratingが灰色になってしまった。

Mediumのシステムテストを通すのに、終わってから2時間くらいかかってしまった。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20110510