Approach

wleiteさん, nikaさん, yowaさん のアプローチを参考にしたSA。

wleiteさんの
permutation[order[i]] = i;
は使い方が分からなかった。


source code

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

public class ConstrainedPermutation {

    static final Watch watch = new Watch();
    static final XorShift rng = new XorShift(System.nanoTime());

    private SAState sa = new SAState();

    private int score;
    private int bestScore;

    private double[] provisionalPerm;
    private double[] bestProvisionalPerm;
    private int[] perm;

    private int N;
    private int K;
    private int[][] constraints;
    private int[][] lessIndexes;
    private int[][] greaterIndexes;

    public int[] permute(int N, String[] constraints) {
        init(N, constraints);

        solve();

        makeSolution();

        Utils.debug("time", watch.getSecondString(), "score", (double) score / K, "sa.loop * K / N", sa.loop * (double) K / (double) N, "countSorted", countSorted, (double) countSorted / sa.loop);

        return perm;
    }

    private void makeSolution() {

        ArrayList> numberAndIndexPairs = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            numberAndIndexPairs.add(new Pair(provisionalPerm[i], i));
        }
        Collections.sort(numberAndIndexPairs);
        perm = new int[N];
        for (int i = 0; i < N; i++) {
            perm[numberAndIndexPairs.get(i).second.intValue()] = i;
        }

    }

    private void init(int N, String[] constraints) {
        this.N = N;
        K = constraints.length;
        this.constraints = new int[K][2];

        int[] sizeless = new int[N];
        int[][] less = new int[N][N];
        int[] sizegreater = new int[N];
        int[][] greater = new int[N][N];

        for (int k = 0; k < K; k++) {
            String[] split = constraints[k].split(" ");
            int i = Integer.parseInt(split[0]);
            int j = Integer.parseInt(split[1]);
            this.constraints[k][0] = i;
            this.constraints[k][1] = j;
            greater[i][sizegreater[i]++] = j;
            less[j][sizeless[j]++] = i;
        }

        lessIndexes = new int[N][];
        greaterIndexes = new int[N][];
        for (int n = 0; n < N; n++) {
            lessIndexes[n] = Arrays.copyOf(less[n], sizeless[n]);
            greaterIndexes[n] = Arrays.copyOf(greater[n], sizegreater[n]);
        }

        provisionalPerm = new double[N];
        for (int i = 0; i < N; i++) {
            provisionalPerm[i] = i;
        }

        reassign();

        splitValues = new double[N + 2][N + 2];
        scores = new int[N + 2][N + 2];
        isGreater = new boolean[N + 2][N + 2];
        size = new int[N + 2];
        isSorted = new boolean[N + 2];

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

    private void solve() {

        score = calculateScore();

        bestProvisionalPerm = Arrays.copyOf(provisionalPerm, provisionalPerm.length);
        bestScore = score;

        if (K / N < 35) {
            SA2();
        } else {
            SA();
        }
    }

    private void SA() {
        double second = 1;
        int mask = (1 << 10) - 1;

        sa.startTemperature = 0.5;

        sa.startRange = 1e9;
        sa.endRange = 1e9 / N;

        sa.init();

        for (;; sa.loop++) {

            if ((sa.loop & mask) == 0) {
                sa.updateTime();

                if (sa.isTLE()) {
                    saveBest();
                    loadBest();
                    Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", (double) score), String.format("%.6f", sa.temperature), String.format("%.6f", sa.lastUpdatedTemperature));
                    break;
                }

                sa.updateTemperature();
                sa.updateRange();

                if (sa.time > second) {
                    second++;
                    Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", (double) score), String.format("%.6f", sa.temperature), String.format("%.6f", sa.lastUpdatedTemperature));
                }

                reassign();

            }

            changeRandom();

        }
    }

    private void reassign() {
        ArrayList> numberAndIndexPairs = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            numberAndIndexPairs.add(new Pair(provisionalPerm[i], i));
        }
        Collections.sort(numberAndIndexPairs);
        for (int i = 0; i < N; i++) {
            provisionalPerm[numberAndIndexPairs.get(i).second.intValue()] = (1e9 / N) * (i + 0.5);
        }
    }

    private void changeRandom() {
        int currentIndex = (int) (N * rng.nextDouble());

        int currentCount = 0;
        for (int index : greaterIndexes[currentIndex]) {
            if (provisionalPerm[currentIndex] < provisionalPerm[index]) {
                currentCount++;
            }
        }
        for (int index : lessIndexes[currentIndex]) {
            if (provisionalPerm[index] < provisionalPerm[currentIndex]) {
                currentCount++;
            }
        }

        double value = provisionalPerm[currentIndex] + (rng.nextDouble() < 0.5 ? -1 : 1) * sa.range * rng.nextDouble();

        int count = 0;
        for (int index : greaterIndexes[currentIndex]) {
            if (value < provisionalPerm[index]) {
                count++;
            }
        }
        for (int index : lessIndexes[currentIndex]) {
            if (provisionalPerm[index] < value) {
                count++;
            }
        }

        int newScore = score + (count - currentCount);
        sa.countChange++;
        if (newScore >= score || sa.accept(newScore, score)) {
            sa.countAccept++;
            if (!(newScore >= score)) {
                sa.lastUpdatedTemperature = sa.temperature;
            }

            score = newScore;
            provisionalPerm[currentIndex] = value;

            saveBest();
        }

    }

    private void SA2() {
        double second = 1;
        int mask = (1 << 10) - 1;

        sa.startTemperature = 0.5;
        sa.endTemperature = 0.00;

        sa.init();

        for (;; sa.loop++) {

            if ((sa.loop & mask) == 0) {
                sa.updateTime();

                if (sa.isTLE()) {
                    saveBest();
                    loadBest();
                    Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", (double) score), String.format("%.6f", sa.temperature), String.format("%.6f", sa.lastUpdatedTemperature));
                    break;
                }

                sa.updateTemperature();

                if (sa.time > second) {
                    second++;
                    Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%.4f", (double) score), String.format("%.6f", sa.temperature), String.format("%.6f", sa.lastUpdatedTemperature));
                }

                // reassign();

            }

            changeRandom2();

        }
    }

    private double[][] splitValues;
    private int[][] scores;
    private boolean[][] isGreater;
    private int[] size;
    private boolean[] isSorted;
    private int countSorted;

    private static final void insertionSort(double[] a, boolean[] b, int startInclusive, int endInclusive) {
        if (endInclusive < startInclusive) {
            return;
        }

        int mini = startInclusive;
        for (int i = startInclusive; i <= endInclusive; i++) {
            if (a[i] < a[mini]) {
                mini = i;
            }
        }
        {
            double swap = a[startInclusive];
            a[startInclusive] = a[mini];
            a[mini] = swap;
        }
        {
            boolean swap = b[startInclusive];
            b[startInclusive] = b[mini];
            b[mini] = swap;
        }
        for (int i = startInclusive + 2; i <= endInclusive; i++) {
            double v = a[i];
            boolean vb = b[i];
            int j = i;
            while (a[j - 1] > v) {
                a[j] = a[j - 1];
                b[j] = b[j - 1];
                j--;
            }
            a[j] = v;
            b[j] = vb;
        }
    }

    private void insertionSort(int[] indexes, int startInclusive, int endInclusive) {

        if (endInclusive < startInclusive) {
            return;
        }

        int mini = startInclusive;
        for (int i = startInclusive; i <= endInclusive; i++) {
            if (provisionalPerm[indexes[i]] < provisionalPerm[indexes[mini]]) {
                mini = i;
            }
        }
        {
            int swap = indexes[startInclusive];
            indexes[startInclusive] = indexes[mini];
            indexes[mini] = swap;
        }

        for (int i = startInclusive + 2; i <= endInclusive; i++) {
            int v = indexes[i];

            int j = i;
            while (provisionalPerm[indexes[j - 1]] > provisionalPerm[v]) {
                indexes[j] = indexes[j - 1];
                j--;
            }
            indexes[j] = v;

        }
    }

    private void changeRandom2() {
        int currentIndex = (int) (N * rng.nextDouble());

        double currentValue = provisionalPerm[currentIndex];

        if (isSorted[currentIndex]) {
            countSorted++;
        }

        if (!isSorted[currentIndex]) {
            size[currentIndex] = 0;
            for (int index : lessIndexes[currentIndex]) {
                splitValues[currentIndex][size[currentIndex]] = provisionalPerm[index];
                isGreater[currentIndex][size[currentIndex]++] = !true;
            }
            for (int index : greaterIndexes[currentIndex]) {
                splitValues[currentIndex][size[currentIndex]] = provisionalPerm[index];
                isGreater[currentIndex][size[currentIndex]++] = true;
            }
            insertionSort(splitValues[currentIndex], isGreater[currentIndex], 0, size[currentIndex] - 1);
            scores[currentIndex][0] = greaterIndexes[currentIndex].length;
            for (int j = 0; j < size[currentIndex]; j++) {

                if (isGreater[currentIndex][j]) {
                    scores[currentIndex][j + 1] = -1 + scores[currentIndex][j];
                } else {
                    scores[currentIndex][j + 1] = 1 + scores[currentIndex][j];
                }

            }
            isSorted[currentIndex] = true;
        }

        int binarySearch = Arrays.binarySearch(splitValues[currentIndex], 0, size[currentIndex], currentValue);
        int currentIndex2 = binarySearch < 0 ? (-binarySearch - 1) : binarySearch;
        int currentCount = scores[currentIndex][currentIndex2];

        int index2 = (int) ((size[currentIndex] + 1) * rng.nextDouble());
        int count = scores[currentIndex][index2];

        int newScore = score + (count - currentCount);

        sa.countChange++;
        if (newScore >= score || sa.accept(newScore, score)) {
            sa.countAccept++;
            if (!(newScore >= score)) {
                sa.lastUpdatedTemperature = sa.temperature;
            }

            score = newScore;

            double value = 0;
            if (index2 == 0) {
                value = 0 + rng.nextDouble() * (splitValues[currentIndex][index2] - 0);
            } else if (index2 == size[currentIndex]) {
                value = splitValues[currentIndex][index2 - 1] + rng.nextDouble() * (1e9 - splitValues[currentIndex][index2 - 1]);
            } else {
                value = splitValues[currentIndex][index2 - 1] + rng.nextDouble() * (splitValues[currentIndex][index2] - splitValues[currentIndex][index2 - 1]);
            }

            provisionalPerm[currentIndex] = value;

            saveBest();

            for (int index : lessIndexes[currentIndex]) {
                isSorted[index] = false;
            }
            for (int index : greaterIndexes[currentIndex]) {
                isSorted[index] = false;
            }

            insertionSort(lessIndexes[currentIndex], 0, lessIndexes[currentIndex].length - 1);
            insertionSort(greaterIndexes[currentIndex], 0, greaterIndexes[currentIndex].length - 1);
        }

    }

    private int calculateScore() {
        int count = 0;
        for (int k = 0; k < K; k++) {
            int i = constraints[k][0];
            int j = constraints[k][1];
            if (provisionalPerm[i] < provisionalPerm[j]) {
                count++;
            }
        }
        return count;
    }

    private void loadBest() {
        score = bestScore;
        for (int i = 0; i < provisionalPerm.length; i++) {
            provisionalPerm[i] = bestProvisionalPerm[i];
        }
    }

    private void saveBest() {
        if (score > bestScore) {
            bestScore = score;
            for (int i = 0; i < provisionalPerm.length; i++) {
                bestProvisionalPerm[i] = provisionalPerm[i];
            }
        }
    }

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

            int N = Integer.parseInt(br.readLine());
            int K = Integer.parseInt(br.readLine());
            String[] constraints = new String[K];
            for (int i = 0; i < K; ++i) {
                constraints[i] = br.readLine();
            }

            ConstrainedPermutation cp = new ConstrainedPermutation();
            int[] ret = cp.permute(N, constraints);

            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 SAState {

    public static final boolean useTime = true;

    public double startTime = 0;
    public double endTime = 9.5;
    public double time = startTime;

    public double startTemperature = 0.1e-3;
    public double endTemperature = 0;
    public double temperature = startTemperature;
    public double lastUpdatedTemperature = startTemperature;

    public double startRange = 1e9;
    public double endRange = 1e7;
    public double range = startRange;

    public int loop;
    public int countChange;
    public int countAccept;

    public void init() {
        loop = 0;
        countChange = 0;
        countAccept = 0;
        lastUpdatedTemperature = startTemperature;
        startTime = useTime ? ConstrainedPermutation.watch.getSecond() : loop;

        updateTime();
        updateTemperature();
        updateRange();
    }

    public void updateTemperature() {
        temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
    }

    public void updateRange() {
        range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
    }

    public void updateTime() {
        time = useTime ? ConstrainedPermutation.watch.getSecond() : loop;
    }

    public boolean isTLE() {
        return time >= endTime;
    }

    public boolean accept(double newScore, double currentScore) {
        assert newScore - currentScore < 0;
        assert temperature >= 0;
        return ConstrainedPermutation.rng.nextDouble() < StrictMath.exp((newScore - currentScore) / (temperature));
    }
}

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

}

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