hotpepsiの練習帳

SRM 538

01:15

Div1 Easy (250) EvenRoute

問題

• N個の点が与えられる。
• 初期位置が(0,0)で、N個の点の全部を1回だけ経由するものとする。
• 位置のパリティがwantedParityと一致するかどうかを求める。

方針

• サンプルを読まずに適当に解く
• 死亡
• 解きなおし
• パリティは途中経路に関わらず、始点と終点との関係で決まる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_538/EvenRoute.cpp

Div1 Medium (450) TurtleSpy

問題

• 左右の回転と前後の移動が可能なスパイロボットがある。
• N個のコマンド列が与えられ、それぞれを1回ずつ実行する。
• 最も遠くに移動できるような順番で実行したときの距離を求める。

方針

• 前進と後退それぞれをまとめた方が良さそう
• なるべく遠ざかるように角度を決めればよいのでは
• 180度に近づけるためにDPすればいけそう
• 角度で使わないやつは最初か最後に浪費させればよい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_538/TurtleSpy.cpp

Div2 Easy (300) LeftOrRight

問題

• LかRからなるコマンド列が実行可能な機械がある。
• Lは左に、Rは右に一歩進む。
• コマンド列の一部が破損して?になっている。
• 破損したコマンドをLかRに補ったとき、初期位置から最遠点の距離を求める。

方針

• うしろからやるのかな...失敗
• 全ての?をLとRのどちらかに置換したときが最大
• 単純に、?が全部Lなのと全部Rなのの両方試せば良さそう
• 配列で持つ必要なかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_538/LeftOrRight.cpp

Div2 Hard (1050) SkewedPerspectives

問題

• 3色のブロックと、1x2の大きさの黒いブロックがある
• 幅w以内で縦に積む
• 横から見たときの図が与えられる
• その図になるように積めるかどうかを求める

方針

• analysisとkusanoさんのを読む
• 黒いブロックが偶数のときはただ積むだけ。奇数の場合に色々やればよい
• 奇数の黒いブロックは、横に積んで一つ隠す
• 一番下を1つだけ黒にすることはできないので、はじく
• 途中で黒が奇数のときは、今積んでいる列をやめて、うしろに今の位置-1個を積んでから、黒を積む
• ただし一番下が黒かつ奇数のときは、まず黒を積み、うしろに1個積んでから黒を積む
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_538/SkewedPerspectives.cpp

結果

xx- 237.62*0 + 187.57*0 - 25 = -25 rating 1516 -> 1322

落ち着きと集中力を欠いた。しかし良い練習になった。

easyは基礎なのだが苦手。引数名の通り、パリティを求める問題。

mediumは提出したコードに二箇所バグがあった。具体的にはDPで同じ配列に代入していたので、最長になっていなかった。初歩だがいったん書くと発見しづらいので、計算量に余裕があるなら冗長でも丁寧に書くべき。しかし方針は合っていたようなので、前回（通ったが実装自体は単純）よりも、できた感じがした。

div2easyは珍しく300点。再帰で書くと2^50回呼ばれるから死亡。なるほど。

div1残留があぶなくなったので、次回は慎重にeasyを通すようにしたい。それとTCO楽しみ。