hotpepsiの練習帳

SRM 522 Div2

01:21

Easy (250) PointErasingTwo

問題

• y座標の配列が与えられる。
• 2点間を選んだとき、その内部に含まれる最大の個数を求める。

方針

• 範囲をミスらないようにする。
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_522/PointErasingTwo.cpp

Medium (550) RowAndManyCoins

問題

• AliceとBobが交互にコインを置く。
• コインは1つ以上の連続するマスに置ける。
• 全ての場所を埋める置き方はできない。
• 残りのマスが1つになったとき、マスに書いてある文字で勝者が決まる。
• 最適戦略で勝つほうを答える。

方針

• 終了条件を覚えておいて、メモ化再帰
• 両端のどちらかがAのときAlice、その他はBobらしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_522/RowAndManyCoins.cpp

Hard (900) CorrectMultiplicationTwo

問題

• a * b = cという形の式があるが、正しくない。
• 値を加算または減算してA * B = Cに値を変更する。
• |A - a| + |B - b| + |C - c|の最小値を求める。

方針

• 範囲をaとbの前後で動かしていったらsystem test failed
• 単純な全探索で、積が巨大なとき打ち切りにすればよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_522/CorrectMultiplicationTwo.cpp

結果

oox 239.43+328.24=567.67 rating 1194 -> 1146

ぼちぼち青くなれるかなーと思ったが甘かった。

ここ5回はmediumまで通っているのでまあ解けるようにはなってきたかと思う。