確か12位か13位。


Approach beam search を使いました。

  • beam width 800 で9秒
  • ある状態から生成する子の状態は、最大100(カメレオン10 * 色最大10)有る内の3つだけに絞った。カメレオンは後ろの方の3匹だけ。色はカメレオンごとに最も前に移動できる色を選ぶ。
評価関数

  • カメレオンの位置の和
    • この評価関数では、beam width を2000〜3000にしてもスコアは40000にぎりぎり届くくらいだった。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;

public class Main {

    private int numStripePatterns;
    private int backpackColors;
    private int numColors;
    private int handColors;
    private int numChameleons;
    private int[] stripPattern;
    private int[] backpack;
    private int[] distances;
    private int[] hand;
    private String[] solution;

    private Watch watch = new Watch();
    private XorShift rng = new XorShift(System.nanoTime());
    private long[] hashes;
    private InitializedBooleanArray position;
    private int[][] nextPosition;

    private String[] run(int N, int S, int C, int H, int U, String stripPattern, String backpack) {
        init(N, S, C, H, U, stripPattern, backpack);
        solve();
        return makeSolution();
    }

    private void init(int N, int S, int C, int H, int U, String stripPattern, String backpack) {
        this.numStripePatterns = N;
        this.backpackColors = S;
        this.numColors = C;
        this.handColors = H;
        this.numChameleons = U;

        this.stripPattern = new int[numStripePatterns];
        for (int i = 0; i < numStripePatterns; i++) {
            this.stripPattern[i] = stripPattern.charAt(i) - 'A';
        }
        this.hand = new int[handColors];
        for (int i = 0; i < H; i++) {
            this.hand[i] = backpack.charAt(i) - 'A';
        }
        this.backpack = new int[backpackColors + 1];
        for (int i = 0; i < backpackColors; i++) {
            this.backpack[i] = backpack.charAt(handColors + i) - 'A';
        }

        this.distances = new int[numChameleons];
        for (int i = 0; i < numChameleons; i++) {
            distances[i] = i;
        }

        this.solution = new String[backpackColors];
        hashes = new long[numStripePatterns];
        for (int i = 0; i < numStripePatterns; i++) {
            hashes[i] = rng.nextLong();
        }
        position = new InitializedBooleanArray();
        position.init(false, numStripePatterns);

        nextPosition = new int[numColors][numStripePatterns];
        for (int color = 0; color < numColors; color++) {
            int next = -1;
            for (int distance = numStripePatterns - 1; distance >= 0; distance--) {
                nextPosition[color][distance] = next;
                if (this.stripPattern[distance] == color) {
                    next = distance;
                }
            }
        }
    }

    private void solve() {
        ArrayList beamsearch = beamsearch(backpackColors, 800);
        for (int i = 0; i < beamsearch.size(); i++) {
            updateState(i, beamsearch.get(i).chameleonIndex, beamsearch.get(i).hi);
        }
    }

    private ArrayList distanceAndIndexPairs = new ArrayList<>();

    private ArrayList beamsearch(int maxDepth, int maxBeamWidth) {
        int K = 3;
        int[] index = new int[K];

        InitializedBooleanArray usedColors = new InitializedBooleanArray();
        usedColors.init(false, numColors);

        int size = 1 << 15;

        for (int i = 0; i < numChameleons; i++) {
            distanceAndIndexPairs.add(new PairIntInt(0, 0));
        }

        ArrayList currents = new ArrayList<>();
        ArrayList nexts = new ArrayList<>();
        RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4 used = new RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4(16, 1 << 16);
        setCurrent(currents);

        double startTime = watch.getSecond();
        for (int depth = 0; depth < maxDepth; depth++) {
            used.clear();
            int beamWidth = Math.min(maxBeamWidth, currents.size());
            CollectionsUtils.select(currents, 0, currents.size(), beamWidth);
            for (int width = 0; width < beamWidth; width++) {
                State currentState = currents.get(width);
                if (depth % 1000 == 999) {
                    if (width == 0) {
                        if (currentState != null) {
                            Utils.debug(depth, currentState.score(), (int) (currentState.score() * 10000 / (depth + 1)), "exp time", (int) ((watch.getSecond() - startTime) * 10000 / (depth + 1)));
                        }
                    }
                }
                position.clear();
                for (int i = 0; i < numChameleons; i++) {
                    position.set(currentState.getDistance(i), true);
                }
                int min1 = (int) 1e9;
                int min2 = (int) 1e9;
                int min3 = (int) 1e9;
                for (int i = 0; i < numChameleons; i++) {
                    int v = currentState.getDistance(i);
                    if (v < min1) {
                        min3 = min2;
                        min2 = min1;
                        min1 = v;
                        index[2] = index[1];
                        index[1] = index[0];
                        index[0] = i;
                    } else if (v < min2) {
                        min3 = min2;
                        min2 = v;
                        index[2] = index[1];
                        index[1] = i;
                    } else if (v < min3) {
                        min3 = v;
                        index[2] = i;
                    }
                }
                for (int k = 0; k < K; k++) {
                    int chameleonIndex = index[k];
                    int bestHi = -1;
                    int maxDistance = -1;
                    usedColors.clear();
                    for (int hi = 0; hi < handColors; hi++) {
                        int hand2 = currentState.getHand(hi);
                        if (usedColors.get(hand2)) {
                            continue;
                        }
                        usedColors.set(hand2, true);
                        int distance = distance(chameleonIndex, hand2, currentState);
                        if (distance > maxDistance) {
                            maxDistance = distance;
                            bestHi = hi;
                        }
                    }
                    int hi = bestHi;
                    int distance = maxDistance;
                    {
                        long nextHash = currentState.hash;
                        nextHash ^= hashes[currentState.getDistance(chameleonIndex)];
                        nextHash ^= hashes[distance];
                        nextHash ^= hashes[currentState.getHand(hi)];
                        nextHash ^= hashes[backpack[currentState.turn]];
                        boolean add = used.add(nextHash);
                        if (!add) {
                            continue;
                        }
                        State next = new State();
                        next.parent = currentState;
                        next.turn = currentState.turn + 1;
                        next.distances[0] = currentState.distances[0];
                        next.distances[1] = currentState.distances[1];
                        next.distances[2] = currentState.distances[2];
                        next.setDistance(chameleonIndex, distance);

                        next.hand = currentState.hand;
                        next.setHand(hi, backpack[currentState.turn]);
                        next.sum = currentState.sum;
                        next.sum -= currentState.getDistance(chameleonIndex);
                        next.sum += distance;
                        next.hash = nextHash;

                        next.chameleonIndex = chameleonIndex;

                        next.hi = hi;
                        nexts.add(next);
                    }

                }
            }
            {
                ArrayList swap = currents;
                currents = nexts;
                nexts = swap;
            }
            nexts.clear();
        }
        Collections.sort(currents);
        State best = currents.get(0);

        Utils.debug("time", watch.getSecondString(), "score", best.score());

        return reverse(toList(best));
    }

    private void setCurrent(ArrayList currents) {
        boolean setCurrent = !true;
        if (setCurrent) {

        } else {
            State s = new State();
            s.parent = null;
            s.hi = -1;
            s.chameleonIndex = -1;
            s.sum = 45;
            s.turn = 0;
            s.hash = 0L;
            for (int i = 0; i < numChameleons; i++) {
                s.setDistance(i, i);
            }
            for (int i = 0; i < handColors; i++) {
                s.setHand(i, hand[i]);
            }
            currents.add(s);
        }
    }

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

    private ArrayList toList(State state2) {
        ArrayList res = new ArrayList<>();
        for (State current = state2; current.parent != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

    private void updateState(int s, int di, int hi) {
        distances[di] = distance(di, hand[hi]);
        solution[s] = "" + di + " " + (char) ('A' + hand[hi]);
        hand[hi] = backpack[s];
    }

    private int distance(int chameleonIndex, int color) {
        for (int i = nextPosition[color][distances[chameleonIndex]];; i = nextPosition[color][i]) {
            if (isThereAChameleon(i)) {
                continue;
            }

            return i;
        }
    }

    private int distance(int chameleonIndex, int color, State state) {
        for (int i = nextPosition[color][state.getDistance(chameleonIndex)];; i = nextPosition[color][i]) {
            assert stripPattern[i % stripPattern.length] == color;
            if (isThereAChameleon(i, state)) {
                continue;
            }

            return i;
        }
    }

    private boolean isThereAChameleon(int distance) {
        for (int i = 0; i < distances.length; i++) {
            if (distances[i] == distance) {
                return true;
            }
        }
        return false;
    }

    private boolean isThereAChameleon(int distance, State state) {
        return position.get(distance);
    }

    private String[] makeSolution() {
        return solution;
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            String[] split = br.readLine().trim().split(" ");
            int N = Integer.parseInt(split[0]);
            int S = Integer.parseInt(split[1]);
            int C = Integer.parseInt(split[2]);
            int H = Integer.parseInt(split[3]);
            int U = Integer.parseInt(split[4]);

            String stripPattern = br.readLine();
            String backpack = br.readLine();

            Main main = new Main();
            String[] res = main.run(N, S, C, H, U, stripPattern, backpack);
            for (int i = 0; i < res.length; ++i) {
                System.out.println(res[i]);
            }
            System.out.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

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

}

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 long nextLong() {
        return ((long) nextInt() << 32) ^ (long) nextInt();
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

}

class Pair, S> implements Comparable> {
    public T first;
    public S second;

    public Pair(T t, S s) {
        this.first = t;
        this.second = s;
    }

    private int hash = 0;

    @Override
    public int hashCode() {
        if (hash == 0) {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((first == null) ? 0 : first.hashCode());
            result = prime * result + ((second == null) ? 0 : second.hashCode());
            hash = result;
        }
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Pair other = (Pair) obj;
        if (first == null) {
            if (other.first != null)
                return false;
        } else if (!first.equals(other.first))
            return false;
        if (second == null) {
            if (other.second != null)
                return false;
        } else if (!second.equals(other.second))
            return false;
        return true;
    }

    @Override
    public int compareTo(Pair o) {
        return first.compareTo(o.first);
    }
}

class PairIntInt implements Comparable {
    public int first;
    public int second;

    public PairIntInt(int t, int s) {
        this.first = t;
        this.second = s;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + first;
        result = prime * result + second;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        PairIntInt other = (PairIntInt) obj;
        if (first != other.first)
            return false;
        if (second != other.second)
            return false;
        return true;
    }

    @Override
    public int compareTo(PairIntInt o) {
        return Integer.compare(first, o.first);
    }
}

class InitializedBooleanArray {
    private boolean[] values;
    private boolean[] initial_values;
    private int[] epoch;
    private int current_epoch;

    public void init(boolean[] initial_values) {
        current_epoch = 0;
        this.initial_values = Arrays.copyOf(initial_values, initial_values.length);
        values = Arrays.copyOf(initial_values, initial_values.length);
        epoch = new int[values.length];
    }

    public void init(boolean initial_value, int size) {
        current_epoch = 0;
        initial_values = new boolean[size];
        Arrays.fill(initial_values, initial_value);

        this.values = Arrays.copyOf(initial_values, initial_values.length);
        epoch = new int[values.length];
    }

    public void clear() {
        current_epoch++;
    }

    public boolean get(int at) {
        assert (at < values.length);
        if (epoch[at] != current_epoch) {
            epoch[at] = current_epoch;
            values[at] = initial_values[at];
        }
        return values[at];
    }

    public void set(int at, boolean value) {
        assert (at < values.length);
        epoch[at] = current_epoch;
        values[at] = value;
    }
}

class RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4 {
    private long mask;
    private long[] used;
    private IntArray indexes;
    private long mask2 = ((1L << 16) - 1L) << 48;

    public RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4(int numBits, int capacity) {
        mask = (1L << numBits) - 1L;
        used = new long[1 << numBits];
        indexes = new IntArray(capacity);
    }

    public boolean add(long hash) {
        int index = (int) (hash & mask);
        long value = hash & mask2;

        if ((used[index] & mask2) == value) {
            return false;
        }
        if (((used[index] << 16) & mask2) == value) {
            return false;
        }
        if (((used[index] << 32) & mask2) == value) {
            return false;
        }
        if (((used[index] << 48) & mask2) == value) {
            return false;
        }

        used[index] = (used[index] >>> 16) | value;
        indexes.add(index);

        return true;
    }

    public void clear() {
        for (int i = 0; i < indexes.length; i++) {
            used[indexes.values[i]] = 0;
        }
        indexes.clear();
    }
}

class IntArray {
    public int[] values;
    public int length;

    public IntArray() {
        this(new int[4], 0);
    }

    public IntArray(int capacity) {
        this(new int[capacity], 0);
    }

    public IntArray(int[] values) {
        this(values, values.length);
    }

    public IntArray(int[] values, int length) {
        this.values = values;
        this.length = length;
    }

    public void add(int value) {
        if (length == values.length) {
            values = Arrays.copyOf(values, values.length << 1);
        }
        values[length++] = value;
    }

    public int remove() {
        return values[--length];
    }

    public boolean contains(int value) {
        for (int i = 0; i < length; i++) {
            if (values[i] == value) {
                return true;
            }
        }
        return false;
    }

    public void clear() {
        length = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (int i = 0; i < length; i++) {
            sb.append(values[i] + ",");
        }
        sb.append("}");
        return sb.toString();
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public int remove(int index) {
        if (index >= length) {
            throw new AssertionError();
        }

        if (index == length - 1) {
            return remove();
        }

        int res = values[index];
        System.arraycopy(values, index + 1, values, index, length - (index + 1));
        length--;

        return res;
    }

    public void set(int index, int value) {
        if (index == length) {
            add(value);
            return;
        }

        if (index >= length) {
            throw new AssertionError();
        }

        if (length >= values.length - 1) {
            values = Arrays.copyOf(values, values.length << 1);
        }
        System.arraycopy(values, index, values, index + 1, length - index);
        length++;

        values[index] = value;
    }

    public IntArray copy() {
        return new IntArray(Arrays.copyOf(values, length), length);
    }

    public int[] toArray() {
        return Arrays.copyOf(values, length);
    }

}

class State implements Comparable {

    public State parent;
    public int hi;
    public int chameleonIndex;
    public int sum;
    public int turn;
    public long hash;
    public long[] distances = new long[3];
    public long hand;

    public int getHand(int handIndex) {
        return (int) ((hand >>> (handIndex << 2)) & 15);
    }

    public void setHand(int handIndex, long value) {
        hand &= -1L ^ (15L << (handIndex << 2));
        hand |= (value << (handIndex << 2));
    }

    public int getDistance(int index) {
        int arrayIndex = index >>> 2;
        int c = index & 3;
        return (int) ((distances[arrayIndex] >>> (c << 4)) & ((1 << 16) - 1));
    }

    public void setDistance(int index, long value) {
        int arrayIndex = index >>> 2;
        int c = index & 3;
        distances[arrayIndex] &= -1L ^ (((1L << 16) - 1) << (c << 4));
        distances[arrayIndex] |= (value << (c << 4));
    }

    public int score() {
        int min = (int) 1e9;
        for (int i = 0; i < 10; i++) {
            min = Math.min(min, getDistance(i));
        }
        return min;
    }

    @Override
    public int compareTo(State o) {

        if (sum > o.sum) {
            return -1;
        }
        if (sum < o.sum) {
            return 1;
        }

        return 0;
    }

}