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

TopCoder SRM 510 Div1 Medium: TheLuckyGameDivOne

解法

lucky number の総数は大したことないので全列挙しておく。あとは全ての lucky number についてそれぞれの戦略を考えれば良い。

コード

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;

public class TheLuckyGameDivOne {
	private long bLen;
	private ArrayList<Long> luckyList;

	public int find(long a, long b, long jLen, long bLen) {
		this.bLen = bLen;

		ArrayDeque<Long> deque = new ArrayDeque<>();
		luckyList = new ArrayList<>();
		deque.add(0L);

		while (!deque.isEmpty()) {
			long p = deque.poll();
			long p4 = p * 10 + 4;
			long p7 = p * 10 + 7;
			if (a <= p4 && p4 <= b) {
				luckyList.add(p4);
			}
			if (a <= p7 && p7 <= b) {
				luckyList.add(p7);
			}
			if (p4 <= b) {
				deque.add(p4);
			}
			if (p7 <= b) {
				deque.add(p7);
			}
		}
		Collections.sort(luckyList);

		int ans = 0;
		for (long x : luckyList) {
			long jMax = x + bLen - 1;
			long jMin = jMax - jLen + 1;
			ans = Math.max(ans, john(jMin, jMax, a, b));

			jMin = x - bLen + 1;
			jMax = jMin + jLen - 1;
			ans = Math.max(ans, john(jMin, jMax, a, b));
		}
		ans = Math.max(ans, john(a, a + jLen - 1, a, b));
		ans = Math.max(ans, john(b - jLen + 1, b, a, b));

		return ans;
	}

	private int john(long jMin, long jMax, long a, long b) {
		if (a <= jMin && jMax <= b) {
			int min = brus(jMin, jMax, jMin, jMin + bLen - 1);
			min = Math.min(min, brus(jMin, jMax, jMax - bLen + 1, jMax));
			for (long lucky : luckyList) {
				if (lucky < jMin || jMax < lucky) {
					continue;
				}

				long bMax = lucky - 1;
				long bMin = bMax - bLen + 1;
				min = Math.min(min, brus(jMin, jMax, bMin, bMax));

				bMin = lucky + 1;
				bMax = bMin + bLen - 1;
				min = Math.min(min, brus(jMin, jMax, bMin, bMax));
			}

			return min;
		}
		return 0;
	}

	private int brus(long jMin, long jMax, long bMin, long bMax) {
		if (jMin <= bMin && bMax <= jMax) {
			int posMin = Collections.binarySearch(luckyList, bMin);
			if (posMin < 0) {
				posMin = ~posMin;
			}
			int posMax = Collections.binarySearch(luckyList, bMax);
			if (posMax < 0) {
				posMax = ~posMax - 1;
			}

			int contains = posMax - posMin + 1;
			return contains;
		}
		return Integer.MAX_VALUE;
	}
}