読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 524 Div1 Medium: LongestSequence

コード

import java.util.ArrayDeque;

public class LongestSequence {
	private int[] C;
	private final int MAX_C = 1000;

	public int maxLength(int[] C) {
		this.C = C;
		if (!isLoop(MAX_C * 2)) {
			// 無限に続く場合
			return -1;
		}

		// Dの和がループしないような最大の要素数を求める
		int low = 0, high = MAX_C * 2;
		while (high - low > 1) {
			int mid = (low + high) / 2;
			if (isLoop(mid)) {
				high = mid;
			} else {
				low = mid;
			}
		}
		return low;

	}

	// ceil以下の中でDの和がループしているかどうかを調べる
	private boolean isLoop(int ceil) {
		boolean[] visit = new boolean[ceil + 1];

		ArrayDeque<Integer> deque = new ArrayDeque<>();
		visit[0] = true;
		deque.push(0);
		while (!deque.isEmpty()) {
			int poll = deque.poll();

			for (int c : C) {
				int next = poll + c;

				// 0に戻るならループしている
				if (next == 0) {
					return true;
				}

				if (next > 0 && next <= ceil && !visit[next]) {
					visit[next] = true;
					deque.push(next);
				}
			}
		}

		return false;
	}

}