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; } }