- 2次元平面の原点にかえるがいる。i回目は距離L[i%N]だけ任意の方向に移動できる。(x, 0) に移動するための最小回数を求めよ。無理なら -1 を返す.
- 1≦|L|=N≦50, 1≦|L[i]|≦10^9, |x|≦10^9
- 任意の方向に移動できるってやばそう. √2 とかどうすんだよ
- 考察考察
- i回目までの距離の和 < |x| なら無理
- |x|≦A なる A が 2 回現れればそこまでで必ず (x, 0) に行ける. ( (0,0) → (x/2, sqrt(A^2-(x/2)^2)) → (x, 0) と行けばいい)
- これらは解の範囲を制限するものであるがまったくもって十分ではない。はて.....
- i回目が終わった時に可能性としてありうる点の原点からの距離 in [lo, hi] を管理したら筋が良さそう
- 0回目は [0, 0], 1回目は [ L[0], L[0] ]
- 前回の [lo, hi] と今回の距離 L[i] があったら基本的には lo±L[i], hi±L[i] とかになりそう。ただし距離なので絶対値をとる
- lo-L[i] と hi-L[i]の符号が異なる or lo+L[i] と hi+L[i] の符号が異なるときは lo ← 0 になる
- (追記) lo+L[i] と hi+L[i] はどちらも正なのでこの条件はなくていいですね。根本的には ?-L[i]==0 となる ? in [lo, hi] があればよいので同値な (lo-L[i])(hi-L[i]) ≦ 0 をチェックすれば良いということですね。
- ここまでで小さい x については OK
- lo はそのうち 0 になるかも
- ひとたび lo==0 になったらそれ以降は lo==0 である. そしたら hi だけ伸びてくので規則性がありそう.
- (追記) 一般的には lo==0 のときにすげー大きい数が来たら lo > 0 になりますね。周期性があるからいつか lo==0になるわけですね。
- lo==0 になったところで L を一巡移動したときの hi の増分を覚えておいて |x|-hi を割ってその回数*Nだけ答えに加えればよさげ
- 現実的な回数で lo==0 になるのか？ →同じ数が2回ずつ現れれば必ず lo==0 になるので、最大２巡で lo==0 になる。これで良さそう。
- 提出
- いつか必ず lo==0 になるということは、hi は増える一方なので -1 が答えになることはない。
- x=1, {2,5} でチャレンジ１コ成功. (正解は 3 回)
class PeriodicJumping {
public:
int minimalTime(int x, vector <int> L) {
if(x==0) return 0;
int N=L.size();
double lo=0, hi=0;
ll ans = 0;
REP(loop, 100000) {
double start=-1;
if(lo==0) start=hi;
REP(i, N) {
double lolo = lo-L[i];
double lohi = lo+L[i];
double hilo = hi-L[i];
double hihi = hi+L[i];
lo = min(abs(lolo), abs(hilo));
hi = max(abs(hilo), abs(hihi));
if(lolo * hilo < 0 || lohi * hihi < 0) lo=0;
ans++;
if(lo-1e-9<=abs(x) && abs(x)<=hi+1e-9) return ans;
}
if(start >= 0) {
double d = hi - start;
ll loop = floor((abs(x) - hi) / d);
if(loop > 10000) {
loop-=4;
ans += loop*N;
hi += d * loop;
}
}
}
return -1;
}
};
