TopCoder SRM 633 Div1 Easy: PeriodicJumping (幾何)

解法

na-o-s.hateblo.jp

幾何だ!難しそう!ってなってしまうの良くないなぁ……

コード

public class PeriodicJumping {

	public int minimalTime(int x, int[] jumpLengths) {
		x = Math.abs(x);
		if (x == 0) {
			return 0;
		}
		long sum = 0;
		for (int i = 0; i < jumpLengths.length; i++) {
			sum += jumpLengths[i];
		}

		int ans = 0;
		if (x >= sum) {
			// xが最大辺
			ans += x / sum * jumpLengths.length;
			x %= sum;
			for (int i = 0; x > 0 && i < jumpLengths.length; i++) {
				x -= jumpLengths[i];
				ans++;
			}
		} else {
			int max = x;
			long subsum = x;
			int cur = 0;
			while (max > subsum - max) {
				subsum += jumpLengths[cur];
				ans++;
				max = Math.max(max, jumpLengths[cur]);

				cur++;
				cur %= jumpLengths.length;
			}
		}

		return ans;
	}

}