Problem A
Dock to the Future
Y. Sugawara
T. Muranushi
出典

オリジナル

問題作成 : 村主
Overview

減速スラスターを切り替えて、宇宙船を停泊
させよう
概要2

停泊できなかったら?
戻ってやり直す
 戻れなかったらぶつかる(不可抗力)

運動方程式

ある時間t=t0からt=t0+1までの間
加速度 a=-a
(一定)
速度
v=v(t0) - a(t-t0)
位置
x=x(t0) +v(t-t0) +a(t-t0)2/2
分数はここだけ
→位置を二倍に
すれば全部整数
x
解法
(2x,v)を点として扱う
 (2x,v)から(2x+2v0-ai,v-ai)への辺を、各スラ
スター出力aiに対応して張る
 初期状態から(2x,0)への到達可能性を判定


具体的なアルゴリズム
普通にダイクストラ
 vは減る一方なので、DPやMemoなど

解法(cont.)

到達できなかったら・・・・


crashかtry againを判定
こんなケースにご注意
t=0
a = 20
a = 20
a = 20
v = 10
v=0
v = -10
x=1
t = 0.5
x = -1.5
t=1
x=1
解法(cont.)

crashedの判定は、次の式で求められる。


2 aMAX x > v2
ならcrashしない
証明はいろいろあるけど、aを重力加速度gと
見て、
運動エネルギー mv2/2 と
位置エネルギー mgh とを比較する、と楽

Problem H