またもEasyをしょうもないミスで落とし、５連続レート減…。
幸い1Challengeとったのと、0点の人が多く減少幅はわずかで済んだ。
http://community.topcoder.com/stat?c=problem_statement&pm=13234
問題
２次元座標上(0,0)から(x,0)に移動したい。
この際、１回で移動できる距離のリストJ[i]が与えられ、j回目のジャンプでは任意の方向にJ[j%N]だけ移動できる(N=リストの要素数)。
(x,0)に移動する最短ジャンプ回数を応えよ。
解法
最初に長さxの辺があり、そこにJ[j%N]の辺をどんどん加えて多角形を作れるか、と考えると良い。
多角形ができる条件は、最長の辺が総辺長の半分以下であることである。
よって、
- xがJ[i]の総和より大きいなら、単純にJ[j%N]の合計がxを超えるまで足せばよい。xが極端に大きいならJ[i]１周分の長さで割り算すれば処理を短くできる。
- J[i]の中にxより長いのがある場合、J[i]を２周する間には条件を満たすjが登場するのでそれを応えればよい。(J[i]にどんなに長い辺があっても、その辺が２つあれば片方で総辺長の半分を超えることはない)
class PeriodicJumping {
public:
int minimalTime(int x, vector
int N=jumpLengths.size(),i;
x=abs(x);
ll tot=0,ma=x;
if(x==0) return 0;
FOR(i,2*N) {
tot+=jumpLengths[i%N];
ma=max(ma,(ll)jumpLengths[i%N]);
if(ma*2<=tot+x) return i+1;
}
tot/=2;
ll ret=x/tot*N;
x%=tot;
FOR(i,N) {
if(x<=0) return ret;
x-=jumpLengths[i];
ret++;
}
return ret;
}
}
|
まとめ
考え方がわかれば簡単…。
