SRM347 Div2 500

ひどい解き方をしたので。記録。

問題

2つの飛行機がある距離以下まで接近したとき、ニアミスしたという。
この距離Rとそれぞれの飛行機の現在の(3次元)座標と速度が与えられる。飛行機はこの速度で等速直線運動するとき、現在以降、ニアミスする可能性があるか。あるならばYES、ないならばNOを返す。

考え方

数学的に解く方法。
ある時刻tでの飛行機間の距離は、それぞれ位置差p[0-2]と速度差v[0-2]とすると、
sqrt( (p[0]+t*v[0])^2 + (p[1]+t*v[1])^2 + (p[2]+t*v[2])^2) )
とであるので、これがR以下であればいい。
2乗して考えると、式は
(p[0]+t*v[0])^2 + (p[1]+t*v[1])^2 + (p[2]+t*v[2])^2) <= R^2
を考えればいい。tについて整理すると、
(v[0]^2+v[1]^2+v[2]^2)*t^2 + 2*(p[0]*v[0]+p[1]*v[1]+p[2]*v[2])*t + (p[0]^2+p[1]^2+p[2]^2) <= R^2
となる。左辺はtについての二次関数なので、
A = (v[0]^2+v[1]^2+v[2]^2)
B = 2*(p[0]*v[0]+p[1]*v[1]+p[2]*v[2])
C = (p[0]^2+p[1]^2+p[2]^2)
判別式D = B^2 - 4*A*(C-R^2)が解をもてばよい(D>=0)。

■t=0の時(現時刻)
C<=R^2ならばニアミスする。それ以外は未来に依る。
■t!=0の時(未来)
A=0の時、距離の差は変わらないので、現時刻でニアミスしていなければ将来もニアミスしない。
B>=0の時、AもCも非負なので、解をもたないことになるので、ニアミスしない。
D>=0の時、解をもつので、ニアミスする。そうでなければニアミスしない。

ひどい考え方

t=0以降の距離差の最小値を求めればいいのはわかったけど、ちゃんと考えずに、その距離差が二次関数的に変化することがわかってなかった。(下に凸なので、通常3分探索で。)

ということで、血迷った結果、距離差の最小値を求めるのに粒子群最適化(Particle Swarm Optimization, PSO)を使ってみることに。
といっても、これは各粒子に、変数t、その変化量v、現在までで一番適合度の高かったtを保持させるだけ。適合度はここでは、距離差。距離差の小さいほうが適合度が高くなるようにする。
粒子数 : 100
粒子の初期t : 0,1,2,3,4...と均等配置
計算ステップ数 : 20000
パラメータw,c1,c2 : 0.8, 0.95, 0.95
でやってみたら、SYSTEMTEST通ってしまった。これは内部で乱数使ってたりして、あくまで近似値なのでかなーり怪しいけど、結局二次関数なので、局所解もないし。きちんと見つけられるみたい。