Hatena::Grouptopcoder

hotpepsiの練習帳

2012-03-22

SRM 538

01:15

Div1 Easy (250) EvenRoute

問題

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

方針

Div1 Medium (450) TurtleSpy

問題

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

方針

Div2 Easy (300) LeftOrRight

問題

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

方針

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楽しみ。

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