hotpepsiの練習帳

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時間くらいかかってしまった。