Approach ビームサーチを使いました。

  • ビーム幅:100に固定
  • 評価関数:Σ使ってない石 (進める方向の数/2)

感想
  • 最適解がでやすかった。



Source Code 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;
import java.util.Scanner;

class Solver {
    private static final int[] dr = { -1, 0, 0, 1, };
    private static final int[] dc = { 0, -1, 1, 0, };

    private final int N;

    private final XorShift rng = new XorShift(System.nanoTime());

    private int[] r;
    private int[] c;
    private int[][] rxcToIndex;

    private ArrayList[][] adjacentIndexes;

    private int minC;
    private int maxC;
    private int minR;
    private int maxR;

    public Solver(int N, int[] x, int[] y) {
        this.N = N;
        this.r = y;
        this.c = x;

        used = new boolean[N];

        minR = (int) 1e9;
        maxR = (int) -1e9;
        minC = (int) 1e9;
        maxC = (int) -1e9;
        for (int i = 0; i < N; i++) {
            minR = Math.min(minR, r[i]);
            maxR = Math.max(maxR, r[i]);
            minC = Math.min(minC, c[i]);
            maxC = Math.max(maxC, c[i]);
        }

        rxcToIndex = new int[maxR + 1][maxC + 1];
        for (int i = 0; i < rxcToIndex.length; i++) {
            Arrays.fill(rxcToIndex[i], -1);
        }
        for (int i = 0; i < N; i++) {
            rxcToIndex[r[i]][c[i]] = i;
        }

        adjacentIndexes = new ArrayList[N][dr.length];
        for (int i = 0; i < N; i++) {
            for (int d = 0; d < dr.length; d++) {
                adjacentIndexes[i][d] = new ArrayList();
            }
        }

        for (int i = 0; i < N; i++) {
            for (int d = 0; d < dr.length; d++) {
                for (int length = 1; length < 1000; length++) {
                    int nr = r[i] + dr[d] * length;
                    int nc = c[i] + dc[d] * length;

                    if (!isValid(nr, minR, maxR) || !isValid(nc, minC, maxC)) {
                        break;
                    }

                    if (rxcToIndex[nr][nc] != -1) {
                        adjacentIndexes[i][d].add(rxcToIndex[nr][nc]);
                    }
                }
            }
        }

        Utils.debug("N", N);
    }

    private boolean isValid(int v, int min, int max) {
        return v >= min && v <= max;
    }

    ArrayList moves;

    private Comparator comparatorEven = new Comparator() {
        @Override
        public int compare(State o1, State o2) {
            if (o1.length > o2.length) {
                return -1;
            }
            if (o1.length < o2.length) {
                return 1;
            }

            if (o1.numEvens > o2.numEvens) {
                return -1;
            }
            if (o1.numEvens < o2.numEvens) {
                return 1;
            }

            if (o1.random < o2.random) {
                return -1;
            }
            if (o1.random > o2.random) {
                return 1;
            }
            return 0;
        }
    };

    public void solve() {
        moves = beamsearch(N, 100);
    }

    public int[] makeSolution() {
        int[] res = new int[moves.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = moves.get(i).i;
        }
        return res;
    }

    private ArrayList beamsearch(int maxDepth, int maxWidth) {
        final int baseDepth = moveHistory.size();

        ArrayList[] states = new ArrayList[1 << 1];
        for (int i = 0; i < states.length; i++) {
            states[i] = new ArrayList();
        }

        State best = null;
        {
            for (int i = 0; i < N; i++) {
                int link = 0;
                for (int d = 0; d < dr.length; d++) {
                    for (int i2 = 0; i2 < adjacentIndexes[i][d].size(); i2++) {
                        int index = adjacentIndexes[i][d].get(i2).intValue();
                        if (used[index]) {
                            continue;
                        }
                        link++;
                    }
                }
                if (link == 0) {
                    continue;
                }
                next(i);
                int score = calculateScore();
                previous();
                states[0].add(new State(null, i, 1, score));

            }
        }
        for (int depth = 0; depth < maxDepth; depth++) {
            int beamWidth = Math.min(maxWidth, states[0].size());
            CollectionsUtils.select(states[0], 0, states[0].size(), beamWidth, comparatorEven);

            for (int width = 0; width < beamWidth; width++) {
                State currentState = states[0].get(width);

                if (best == null || comparatorEven.compare(currentState, best) < 0) {
                    best = currentState;
                }

                set(reverse2(toList(currentState)), baseDepth);

                int parentI = currentState.parent == null ? -1 : currentState.parent.i;
                int parentD = parentI == -1 ? -1 : (r[parentI] != r[currentState.i] ? (r[parentI] < r[currentState.i] ? 3 : 0) : (c[parentI] < c[currentState.i] ? 2 : 1));
                int reverseD = 3 - parentD;
                for (int d = 0; d < dr.length; d++) {
                    if (d == reverseD) {
                        continue;
                    }
                    for (int i = 0; i < adjacentIndexes[currentState.i][d].size(); i++) {
                        int index = adjacentIndexes[currentState.i][d].get(i).intValue();
                        if (used[index]) {
                            continue;
                        }

                        next(index);
                        int score = calculateScore();
                        previous();

                        states[1].add(new State(currentState, index, currentState.length + 1, score));
                        break;
                    }
                }

            }
            {
                ArrayList swap = states[0];
                for (int i = 1; i < states.length; i++) {
                    states[i - 1] = states[i];
                }
                states[states.length - 1] = swap;
                states[states.length - 1].clear();
            }
        }

        for (; moveHistory.size() > baseDepth;) {
            previous();
        }

        if (states[0].size() > 0) {
            Collections.sort(states[0], comparatorEven);
            if (best == null || comparatorEven.compare(states[0].get(0), best) < 0) {
                best = states[0].get(0);
            }
        }
        ArrayList list = reverse2(toList(best));
        return list;
    }

    private int calculateScore() {
        int even = 0;
        for (int i = 0; i < N; i++) {
            if (used[i]) {
                continue;
            }
            int link = 0;
            for (int d = 0; d < dr.length; d++) {
                for (int i2 = 0; i2 < adjacentIndexes[i][d].size(); i2++) {
                    int index3 = adjacentIndexes[i][d].get(i2).intValue();
                    if (used[index3]) {
                        continue;
                    }
                    link++;
                    break;
                }
            }
            even += link / 2;
        }
        return even;
    }

    public void set(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;
        for (int i = 0; i < list.size() && startIndex + i < moveHistory.size(); i++) {
            if (!isSameMove(moveHistory.get(startIndex + i), list.get(i))) {
                break;
            }
            startIndexMinus1 = startIndex + i;
        }
        for (; moveHistory.size() > startIndexMinus1 + 1;) {
            previous();
        }
        for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
            State state2 = list.get(i);
            next(state2.i);
        }
    }

    private boolean isSameMove(Integer move, State state) {
        if (state.i != move.intValue()) {
            return false;
        }
        return true;
    }

    private ArrayList moveHistory = new ArrayList<>();
    private boolean[] used;

    public void next(int i) {
        moveHistory.add(i);
        used[i] = true;
    }

    public void previous() {
        int i = moveHistory.remove(moveHistory.size() - 1).intValue();
        used[i] = false;
    }

    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 ArrayList toList(State state0) {
        ArrayList res = new ArrayList<>();
        for (State current = state0; current != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

    class State {

        State parent;
        int i;
        int length;
        int numEvens;
        int random;

        public State(State parent, int i, int length) {
            super();
            this.parent = parent;
            this.i = i;
            this.length = length;
            random = rng.nextInt();
        }

        public State(State parent, int i, int length, int numEvens) {
            super();
            this.parent = parent;
            this.i = i;
            this.length = length;
            this.numEvens = numEvens;
            random = rng.nextInt();
        }

    }

}

public class Main {

    public int[] findSolution(int N, int[] x, int[] y) {
        Solver solver = new Solver(N, x, y);
        solver.solve();
        return solver.makeSolution();
    }

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {

            int N = sc.nextInt();
            int x[] = new int[N];
            int y[] = new int[N];
            for (int i = 0; i < N; i++) {
                x[i] = sc.nextInt();
                y[i] = sc.nextInt();
            }

            int[] ret = new Main().findSolution(N, x, y);

            System.out.println(ret.length);
            for (int i = 0; i < ret.length; ++i) {
                System.out.println(ret[i]);
            }
            System.out.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

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

}

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

}