SRM560 Easy "TomekPhone"
■時間
10分ほど
■試した解き方
Greedyに、多く使われる文字順に、今与えられる一番低い位置を与えていくだけ。
1st submit：
OK
■editorial
→同じ感じ。もうちょっとすっきりした書き方。
■反省
Greedyで出来るかどうか、一瞬躊躇ってしまった。
これぐらいの問題は2,3分で解きたい。
SRM560 Medium "DrawingPointsDivOne"
■時間
2時間ぐらい・・・
■試した解き方
1回目：
与えられた点群の一つ一つの点を広げていった時に、他の点から発生した四角形とぶつかったらアウトになる。そのため、間に点が存在しない点ペア間の最小マンハッタン距離を計算すればいい、と勘違い。
→testも通らなかった
Editorialの解説だけ確認：
まず、1ステップを行うというのは、四角形を左下方向に1単位だけ縮小させる動作、というふうに考えられる。
あるkステップ戻った時に、元の点群に存在しないようなk×kの正方形ができてしまったら、kは駄目ということが分かる。
なので、kを1から順番に試していけば、最小のkが分かる、はずだがこれだと遅いので、さらにkをbinary searchする。
1st submit：
timeoutするケースが存在
あるkの時のボードの塗り方が少し無駄な実装になっていたので、これを修正
2nd submit:
OK
■反省
・1ステップの動作を「左下への縮小」と考えるのは、その気になれば思いついたはず。別の表現方法に固執したため見落とした。
