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() {
        ArrayList res = 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;
    }

}