SRM538 Div1 450

とぷこだ 過去問

問題

ロボットがあり、「right X」「left X」「forward X」「backward X」の命令がいくつか与えられる。
rightとleftの時はXに角度、forwardとbackwardの時はXに距離が与えられる。backwardは向いている向きに対して(向きを変えずに)反対方向へ移動する。

命令セットを並び替えて、ユークリッド距離で初期位置から最大距離になるようにし、その時の距離を返す。

考え方

DPぽいけど、ポジションと角度は組み合わせで順番によって全然違ってしまうので、うまく状態を保持できなさそう。

貪欲法的に考えると、「forwardできるだけして、うまく角度調節してbackward、使わなかった角度変更を実行」、が一番遠くに行けるのがわかる。
この「うまく角度調節して」の部分は、180度が作れればベスト。それ以外はちょっとまがって進むので、距離が短くなる。
全ての角度関係の命令について、作れる角度をDPですべて求める。
　dp[i][j] := 命令iまでで、角度jが作れるかどうか
で、iとjで回して、i-1のとき作れるなら、命令iを使う場合と使わない場合を更新する。

あとは、距離だけど、余弦定理から、
　距離^2 = (forwardの合計距離)^2 + (backwardの合計距離)^2 - 2 * (forwardの合計距離) * (backwardの合計距離) * cos(角度)
になるので、180度に一番近いときの距離を返せばよい。

(けど、一番近いのを求めるようにするより、すべての角度で、距離を計算させ、一番大きいものを返した方が書きやすい。)

反省

  • backwardのとき、「The angle minus 180 degrees」とか書いてあったので、向きを変えるとばかり思ってた。。。。
  • 角度関係の命令がない場合の処理を忘れた(ang.size()-1とかした)