Approach 複数の点の位置を決める問題なので、SAでOKでしょう(TCO13 MM R3 2nd place, MM86 1st place, MM92 上位ほぼ全員, TCO17 MM R1 上位ほぼ全員, EducationWeek 上位ほぼ全員, Hokkaido Univ.& Hitachi 1st 上位ほぼ全員)。


submission1 SA
submission2 辺がある頂点だけ計算してスコアの計算を高速化 + 計算したポイントごとのスコアをおぼえて高速化
submission3 hakomoさんに習って、最大化して遊ぶ。
submission4 多スタートSA(numRestart=4)
submission5 多スタートSA(numRestart=16) + tomerun さんのSAの枝刈りで高速化
submission6 リスタートするごとに初期解をランダムシャッフルして精度を上げる + 割り算する回数を減らして高速化
submission7 SAの温度のパラメータを変える
submission8 SAの温度のパラメータを変える


submission5 以降はほぼ同じスコア。





source code

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

public class PointsOnTheCircle {
static final Watch watch = new Watch();
static final XorShift rng = new XorShift(System.nanoTime());

private int N;
private boolean[][] hasEdge;
private int[] pointToVertex;
private int[] vertexToPoint;
private double score;
private double[][] distance;
private SAState sa = new SAState();
private double bestScore;
private double[] scores;
private int[][] linkedVertexes;
private int[] bestPointToVertex;

public int[] permute(int[] matrix) {
init(matrix);
solve();
Utils.debug("time", watch.getSecondString());
Utils.debug("score", score);

for (int i = 0; i < N; i++) {
for (int j = 0; j < N - 1; j++) {
int swap = pointToVertex[j];
pointToVertex[j] = pointToVertex[j + 1];
pointToVertex[j + 1] = swap;
}

score = calculateScore();
if (score < bestScore) {
bestScore = score;
for (int j = 0; j < N; j++) {
bestPointToVertex[j] = pointToVertex[j];
}
}
}

score = bestScore;
for (int j = 0; j < N; j++) {
pointToVertex[j] = bestPointToVertex[j];
}

Utils.debug("score", score);

return makeSolution();

}

private void init(int[] matrix0) {
N = (int) Math.sqrt(matrix0.length + 1e-9);
hasEdge = new boolean[N][N];
int numEdges = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
hasEdge[i][j] = matrix0[i * N + j] == 1;
if (hasEdge[i][j]) {
numEdges++;
}
}
}

for (int i = 0; i < N; i++) {
assert !hasEdge[i][i];
for (int j = 0; j < N; j++) {
assert hasEdge[i][j] == hasEdge[j][i];
}
}

linkedVertexes = new int[N][];
for (int i = 0; i < N; i++) {
ArrayList<Integer> vs = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (hasEdge[i][j]) {
vs.add(j);
}
}
linkedVertexes[i] = new int[vs.size()];
for (int j = 0; j < vs.size(); j++) {
linkedVertexes[i][j] = vs.get(j);
}
}

pointToVertex = new int[N];

bestPointToVertex = new int[N];

vertexToPoint = new int[N];

distance = new double[N][N];
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
double alpha = Math.PI / N * (j - i);
distance[i][j] = 2 * Math.sin(alpha);
distance[j][i] = distance[i][j];
}
}

scores = new double[N];

bestScore = 1e9;

Utils.debug("N", N, "rate", (double) numEdges / (N * N));
}

private void solve() {

int numRestart = 16;
double endTime = 9.5;
double startTime = watch.getSecond();
double remainTime = endTime - startTime;
for (double restart = 0; restart < numRestart; restart++) {
sa.startTime = startTime + remainTime * restart / numRestart;
sa.endTime = startTime + remainTime * (restart + 1) / numRestart;
greedy();
SA();
}

score = bestScore;
for (int i = 0; i < N; i++) {
pointToVertex[i] = bestPointToVertex[i];
}

}

private void greedy() {
for (int i = 0; i < N; i++) {
pointToVertex[i] = i;
}
shuffle(pointToVertex, rng);
for (int i = 0; i < N; i++) {
vertexToPoint[pointToVertex[i]] = i;
}

score = calculateScore2();
for (int i = 0; i < N; i++) {
scores[i] = calculatePartScore(i);
}
}

public static final void shuffle(int[] a, XorShift rng) {
for (int i = a.length - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
swap(a, i, j);
}
}

public static final void swap(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}

private double calculateScore() {
double score = 0;
for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
if (hasEdge[pointToVertex[i]][pointToVertex[j]]) {
double alpha = Math.PI / N * (j - i);
score += 2 * Math.sin(alpha);
}
return score;
}

private double calculateScore2() {
double score = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < linkedVertexes[pointToVertex[i]].length; j++) {
int v = linkedVertexes[pointToVertex[i]][j];
score += distance[i][vertexToPoint[v]];
}
}
return 0.5 * score;
}

private double calculatePartScore(int i) {
double score = 0;
for (int j = 0; j < linkedVertexes[pointToVertex[i]].length; j++) {
int v = linkedVertexes[pointToVertex[i]][j];
score += distance[i][vertexToPoint[v]];
}
return score;
}

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

sa.startRange = N;
sa.endRange = 1;
sa.init();
for (;; sa.loop++) {
if ((sa.loop & mask) == 0) {
sa.updateTime();

if (sa.isTLE()) {

Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%5f", score), String.format("%5f", bestScore), String.format("%.6f", sa.inverseTemperature), String.format("%.6f", sa.lastAcceptTemperature));
break;
}

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

change();
}
}

private void change() {
swap();
}

private void swap() {

int index = (int) (N * rng.nextDouble());
int index2 = 1 + (int) (sa.range * rng.nextDouble());
index2 += index;
if (index2 >= N) {
index2 %= N;
}

double before = scores[index];
double before2 = scores[index2];

{
int swap = pointToVertex[index];
pointToVertex[index] = pointToVertex[index2];
pointToVertex[index2] = swap;

vertexToPoint[pointToVertex[index]] = index;
vertexToPoint[pointToVertex[index2]] = index2;
}

double after = calculatePartScore(index);
double after2 = calculatePartScore(index2);

double newScore = score + after + after2 - before - before2;

sa.countChange++;
if (newScore <= score || sa.acceptUsingTomerunsPruning(newScore, score)) {
sa.countAccept++;
if (!(newScore <= score)) {
sa.lastAcceptTemperature = sa.inverseTemperature;
}

score = newScore;

if (score < bestScore) {
bestScore = score;
for (int i = 0; i < N; i++) {
bestPointToVertex[i] = pointToVertex[i];
}
}

scores[index] = after;
scores[index2] = after2;

for (int i = 0; i < linkedVertexes[pointToVertex[index]].length; i++) {
int v = linkedVertexes[pointToVertex[index]][i];
int p = vertexToPoint[v];
if (p == index || p == index2) {
continue;
}
scores[p] += -distance[index2][p] + distance[index][p];
}
for (int i = 0; i < linkedVertexes[pointToVertex[index2]].length; i++) {
int v = linkedVertexes[pointToVertex[index2]][i];
int p = vertexToPoint[v];
if (p == index || p == index2) {
continue;
}
scores[p] += -distance[index][p] + distance[index2][p];
}

} else {
int swap = pointToVertex[index];
pointToVertex[index] = pointToVertex[index2];
pointToVertex[index2] = swap;

vertexToPoint[pointToVertex[index]] = index;
vertexToPoint[pointToVertex[index2]] = index2;
}

}

private int[] makeSolution() {
return pointToVertex;
}

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

int M = Integer.parseInt(br.readLine());
int[] matrix = new int[M];
for (int i = 0; i < M; ++i) {
matrix[i] = Integer.parseInt(br.readLine());
}

PointsOnTheCircle pc = new PointsOnTheCircle();
int[] ret = pc.permute(matrix);

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.9;
public double endTemperature = 0;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 1 << 20;
public double endRange = 1 << 20;
public double range = startRange;

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

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

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

public void updateTemperature() {
inverseTemperature = 1.0 / (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 ? PointsOnTheCircle.watch.getSecond() : loop;
}

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

public boolean accept(double newScore, double currentScore) {
assert newScore - currentScore > 0;
assert 1.0 / inverseTemperature >= 0;
return PointsOnTheCircle.rng.nextDouble() < Math.exp(-(newScore - currentScore) * (inverseTemperature));
}

public boolean acceptUsingTomerunsPruning(double newScore, double currentScore) {
assert newScore - currentScore > 0;
assert 1.0 / inverseTemperature >= 0;
return (-newScore + currentScore) * (inverseTemperature) > -10 && PointsOnTheCircle.rng.nextDouble() < Math.exp(-(newScore - currentScore) * (inverseTemperature));
}

public boolean acceptUsingTomerunsPruningAndEvb(double newScore, double currentScore) {
assert newScore - currentScore > 0;
assert 1.0 / inverseTemperature >= 0;
return (-newScore + currentScore) * (inverseTemperature) > -10 && (PointsOnTheCircle.rng.nextInt() & 2147483647) < 1 << (int) (31.5 + (-newScore + currentScore) * (inverseTemperature));
}

}

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

}

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

}