Approach ビームサーチを使いました。
- 幅 : 5000
- 評価 : スコア + 乱数
- 乱数は親の乱数に足していって、スコアに影響するようにすると、よくなった。
- 左につめる
- 高さの差は最大10
- ある高さの色は、全色試さず、最初に置いたモノスの色で決め打ち
- 実行速度とスコアの両方よくなった。
source code
import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.Random; import java.util.Scanner; public class Main { private int N; private int W; private int K; private int V; private byte[] c; private byte[] v; private int[] solution; private static final int candiateHeight = 10; static final Watch watch = new Watch(); static final XorShift rng = new XorShift(System.nanoTime()); public static void main(String[] args) { new Main().run(); } private void run() { read(); init(); solve(); write(); } private void init() { solution = new int[N]; } private void read() { try (Scanner sc = new Scanner(System.in)) { N = sc.nextInt(); W = sc.nextInt(); K = sc.nextInt(); V = sc.nextInt(); c = new byte[N]; v = new byte[N]; for (int i = 0; i < N; i++) { c[i] = sc.nextByte(); v[i] = sc.nextByte(); } } catch (Exception e) { e.printStackTrace(); } } private void write() { for (int i = 0; i < N; ++i) { System.out.println(solution[i]); } System.out.flush(); } private void solve() { ArrayListres = beamsearch(N, 5000); for (int i = 0; i < res.size(); i++) { solution[i] = res.get(i).w; } Utils.debug("time", watch.getSecondString()); } private ArrayList beamsearch(int maxDepth, int maxWidth) { Comparator comparator = new Comparator () { @Override public int compare(State o1, State o2) { if ((o1.score << 16) + o1.random > (o2.score << 16) + o2.random) { return -1; } if ((o1.score << 16) + o1.random < (o2.score << 16) + o2.random) { return 1; } return 0; } }; ArrayList currents = new ArrayList<>(); ArrayList nexts = new ArrayList<>(); { State e = new State(null, -1, 0, 0); e.heights = new byte[W]; Arrays.fill(e.heights, (byte) 124); e.heightToColors = new byte[candiateHeight]; Arrays.fill(e.heightToColors, (byte) -1); e.heightToSumValues = new byte[candiateHeight]; currents.add(e); } for (int depth = 0; depth < maxDepth; depth++) { int beamWidth = Math.min(maxWidth, currents.size()); CollectionsUtils.select(currents, 0, currents.size(), beamWidth, comparator); for (int width = 0; width < beamWidth; width++) { State currentState = currents.get(width); if (depth - 1 >= 0) { int w = currentState.w; currentState.heights = new byte[W]; for (int w2 = 0; w2 < W; w2++) { currentState.heights[w2] = currentState.parent.heights[w2]; } int maxH = currentState.heights[W - 1]; int height = currentState.heights[w] - (maxH - (candiateHeight - 1)); currentState.heightToSumValues = new byte[candiateHeight]; if (w == W - 1) { for (int h = 0; h < candiateHeight; h++) { currentState.heightToSumValues[h] = h - 1 < 0 ? 0 : currentState.parent.heightToSumValues[h - 1]; } } else { for (int h = 0; h < candiateHeight; h++) { currentState.heightToSumValues[h] = currentState.parent.heightToSumValues[h]; } if (c[depth - 1] == currentState.parent.heightToColors[height] || -1 == currentState.parent.heightToColors[height]) { currentState.heightToSumValues[height] += v[depth - 1]; } } currentState.heightToColors = new byte[candiateHeight]; if (w == W - 1) { for (int h = 0; h < candiateHeight; h++) { currentState.heightToColors[h] = h - 1 < 0 ? -1 : currentState.parent.heightToColors[h - 1]; } } else { for (int h = 0; h < candiateHeight; h++) { currentState.heightToColors[h] = currentState.parent.heightToColors[h]; } if (currentState.heightToColors[height] == -1) { currentState.heightToColors[height] = c[depth - 1]; } } currentState.heights[w]--; } int maxH = currentState.heights[W - 1]; for (int w = W - 1; w >= 0; w--) { if (w - 1 >= 0 && currentState.heights[w - 1] == currentState.heights[w]) { continue; } int height = currentState.heights[w]; if (height < 0) { continue; } if (height < maxH - (candiateHeight - 1)) { continue; } height = currentState.heights[w] - (maxH - (candiateHeight - 1)); int deltaScore = 0; if (currentState.heightToColors[height] == c[depth] || currentState.heightToColors[height] == -1) { deltaScore = v[depth]; } nexts.add(new State(currentState, w, currentState.score + deltaScore, currentState.random + (int) ((1 << 16) * rng.nextDouble()))); } } { ArrayList swap = currents; currents = nexts; nexts = swap; } nexts.clear(); } State best = null; if (currents.size() > 0) { CollectionsUtils.select(currents, 0, currents.size(), 0); best = currents.get(0); } if (best == null) { return null; } Utils.debug("score", best.score); return reverse2(toList(best)); } private ArrayList reverse2(ArrayList list) { for (int l = 0, r = list.size() - 1; l < r; l++, r--) { list.set(r, list.set(l, list.get(r))); } return list; } private static final ArrayList res = new ArrayList<>(1 << 10); private ArrayList toList(State state0) { res.clear(); for (State current = state0; current.parent != null; current = current.parent) { res.add(current); } return res; } } class State implements Comparable { State parent; int w; int score; int random; byte[] heights; byte[] heightToSumValues; byte[] heightToColors; public State(State parent, int w, int score, int random) { super(); this.parent = parent; this.w = w; this.score = score; this.random = random; } @Override public int compareTo(State o) { if (score > o.score) { return -1; } if (score < o.score) { return 1; } return 0; } } final class Utils { private Utils() { } public static final void debug(Object... o) { System.err.println(toString(o)); } public static final String toString(Object... o) { return Arrays.deepToString(o); } } class Watch { private long start; public Watch() { init(); } public double getSecond() { return (System.nanoTime() - start) * 1e-9; } public void init() { init(System.nanoTime()); } private void init(long start) { this.start = start; } public String getSecondString() { return toString(getSecond()); } public static final String toString(double second) { if (second < 60) { return String.format("%5.2fs", second); } else if (second < 60 * 60) { int minute = (int) (second / 60); return String.format("%2dm%2ds", minute, (int) (second % 60)); } else { int hour = (int) (second / (60 * 60)); int minute = (int) (second / 60); return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60)); } } } class XorShift { private int w = 88675123; private int x = 123456789; private int y = 362436069; private int z = 521288629; public XorShift(long l) { x = (int) l; } public int nextInt() { final int t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >>> 19) ^ (t ^ (t >>> 8)); return w; } public double nextDouble() { return (nextInt() >>> 1) * 4.6566128730773926E-10; } public int nextInt(int n) { return (int) (n * nextDouble()); } public long nextLong() { long a = nextInt(); long b = nextInt(); return (a << 32) ^ b; } } class CollectionsUtils { private CollectionsUtils() { } public static final void shuffle(ArrayList list, Random rng) { for (int i = list.size() - 1; i >= 0; i--) { int j = (int) ((i + 1) * rng.nextDouble()); CollectionsUtils.swap(list, i, j); } } public static final void shuffle(ArrayList list, XorShift rng) { for (int i = list.size() - 1; i >= 0; i--) { int j = (int) ((i + 1) * rng.nextDouble()); CollectionsUtils.swap(list, i, j); } } public static final void select0(ArrayList a, int l, int r, int k, Comparator comparator) { while (l < r) { int i = CollectionsUtils.partition3(a, l, r, comparator); if (i >= k) r = i - 1; if (i <= k) l = i + 1; } } public static final void select(ArrayList a, int startInclusive, int endExclusive, int k, Comparator comparator) { select0(a, startInclusive, endExclusive - 1, k, comparator); } public static final > void select0(ArrayList a, int l, int r, int k) { while (l < r) { int i = CollectionsUtils.partition3(a, l, r); if (i >= k) r = i - 1; if (i <= k) l = i + 1; } } public static final > void select(ArrayList a, int startInclusive, int endExclusive, int k) { select0(a, startInclusive, endExclusive - 1, k); } public static final void swap(ArrayList a, int i, int j) { T swap = a.set(i, a.get(j)); a.set(j, swap); } public static final void sort3(ArrayList a, int i, int j, int k, Comparator comparator) { if (comparator.compare(a.get(i), a.get(j)) > 0) { swap(a, i, j); } if (comparator.compare(a.get(i), a.get(k)) > 0) { swap(a, i, k); } if (comparator.compare(a.get(j), a.get(k)) > 0) { swap(a, j, k); } } public static final > void sort3(ArrayList a, int i, int j, int k) { if (a.get(i).compareTo(a.get(j)) > 0) { swap(a, i, j); } if (a.get(i).compareTo(a.get(k)) > 0) { swap(a, i, k); } if (a.get(j).compareTo(a.get(k)) > 0) { swap(a, j, k); } } public static final int partition3(ArrayList a, int l, int r, Comparator comparator) { int center = (l + r) >>> 1; sort3(a, l, center, r, comparator); swap(a, center, r - 1); if (r - l < 3) { return l; } int r1 = r - 1; T v = a.get(r1); int i = l - 1; int j = r1; for (;;) { for (; comparator.compare(a.get(++i), v) < 0;) { } for (; comparator.compare(a.get(--j), v) > 0;) { } if (i >= j) { break; } swap(a, i, j); } swap(a, i, r1); return i; } public static final > int partition3(ArrayList a, int l, int r) { int center = (l + r) >>> 1; sort3(a, l, center, r); swap(a, center, r - 1); if (r - l < 3) { return l; } int r1 = r - 1; T v = a.get(r1); int i = l - 1; int j = r1; for (;;) { for (; a.get(++i).compareTo(v) < 0;) { } for (; a.get(--j).compareTo(v) > 0;) { } if (i >= j) { break; } swap(a, i, j); } swap(a, i, r1); return i; } public static final > int partition(ArrayList a, int l, int r) { int i = l - 1, j = r; T v = a.get(r); for (;;) { while (a.get(++i).compareTo(v) < 0) ; while (v.compareTo(a.get(--j)) < 0) if (j == l) break; if (i >= j) break; swap(a, i, j); } swap(a, i, r); return i; } public static final void sort(ArrayList a, int lInclusive, int rInclusive, Comparator comparator) { if (lInclusive >= rInclusive) { return; } int k = partition3(a, lInclusive, rInclusive, comparator); sort(a, lInclusive, k - 1, comparator); sort(a, k + 1, rInclusive, comparator); } public static final > void sort(ArrayList a, int lInclusive, int rInclusive) { if (lInclusive >= rInclusive) { return; } int k = partition3(a, lInclusive, rInclusive); sort(a, lInclusive, k - 1); sort(a, k + 1, rInclusive); } public static final ArrayList reverse(ArrayList list) { for (int l = 0, r = list.size() - 1; l < r; l++, r--) { list.set(r, list.set(l, list.get(r))); } return list; } public static final ArrayList newReverse(ArrayList list) { ArrayList res = new ArrayList<>(); for (int i = list.size() - 1; i >= 0; i--) { res.add(list.get(i)); } return res; } }
コメント