EvbCFfp1XB

problem and my answer.



Approach テンプレートマッチングや機械学習を試したが、ベースラインソリューションの tesseract-ocr がよくできていた。
README.md には

Future improvements

  • Increase OCR matches maybe by removing grid lines and ability to recognize hand-written text (could take a lot of effort tuning train/test set)
と書いてあったので、他の参加者は試したのかな?



Approach

最初にSAを試したけど遅くて止めた。
円を一つづつ決める貪欲法を使いました。


円の中心の位置 ランダム
円の色  できるだけ givenImage に近づけるため、 givenImage = (x + drawnImage) / 2 を解いて、中心の位置の givenImage[r][c] * 2 - drawnImage[r][c] の色
円の半径 1づつ広げてスコアが最もよいもの

をこの円用の時間いっぱい繰り返して、最もよい円を選んで、

円の色を (半径の範囲の givenImage の中央値) * 2 - (半径の範囲の drawnImage の平均値)

に変更して、良い方を選ぶ。


勉強になったところ

sum squared error に対しては 平均が良くて、
sum absolute error に対しては中央値が良い。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Random;

public class CirclesMix {

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

private int H;
private int W;
private int N;

private int[][] givenImage;
private int[][] drawnImage;

private long score;
private long bestScore;

private Circle[] solution;
private Circle[] bestSolution;
private Point[] points;

public int[] drawImage(int H, int[] pixels, int N) {
init(H, pixels, N);

solve();

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

return makeSolution();

}

private void init(int h, int[] pixels, int n) {
H = h;
W = pixels.length / H;

givenImage = new int[H][W];
for (int r = 0; r < H; r++) {
for (int c = 0; c < W; c++) {
givenImage[r][c] = pixels[r * W + c];
}
}

drawnImage = new int[H][W];
for (int r = 0; r < H; ++r) {
Arrays.fill(drawnImage[r], 0);
}

N = n;

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

score = (long) 1e18;

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

bestScore = (long) 1e18;

// Utils.debug("time", watch.getSecondString());
initDrss2();
// Utils.debug("time", watch.getSecondString());

points = new Point[(H + 0) * (W + 0)];
for (int r = 0, i = 0; r < H; r++) {
for (int c = 0; c < W; c++, i++) {
points[i] = new Point(c, r);
}
}
ArraysUtils.shuffle(points, rng);
// Utils.debug("time", watch.getSecondString());

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

private static final int[] dr1 = new int[] { -1, 0, 0, 1, };
private static final int[] dc1 = new int[] { 0, -1, 1, 0, };
private IntArray[] drs = new IntArray[1001];
private IntArray[] dcs = new IntArray[1001];

private void initDrss2() {

int r0 = 0;
int c0 = 0;

for (int i = 0; i < drs.length; i++) {
drs[i] = new IntArray();
dcs[i] = new IntArray();
}

LinkedList<Integer> queue = new LinkedList<>();
boolean[][] used = new boolean[1 << 11][1 << 11];
{
used[(1 << 10) + r0][(1 << 10) + c0] = true;
queue.add(r0);
queue.add(c0);
}
for (; !queue.isEmpty();) {
int r = queue.poll().intValue();
int c = queue.poll().intValue();

int dr = r - r0;
int dc = c - c0;
int distance = (int) (Math.sqrt(dr * dr + dc * dc) + 1 - 1e-9);
if (distance > 1000) {
continue;
}

drs[distance].add(r);
dcs[distance].add(c);

for (int i = 0; i < dr1.length; i++) {
int nr = r + dr1[i];
int nc = c + dc1[i];
int ndistance = (int) (Math.sqrt(nr * nr + nc * nc) + 1e-9);
if (ndistance > 1000) {
continue;
}

if (used[(1 << 10) + nr][(1 << 10) + nc]) {
continue;
}
used[(1 << 10) + nr][(1 << 10) + nc] = true;
queue.add(nr);
queue.add(nc);
}

}

assert drs[0].length == 1;
assert drs[1].length == 4 : Utils.toString(drs[1].toArray());

}

private static final int getDiff(int c1, int c2) {
return Math.abs(((c1 >>> 16) & 255) - ((c2 >>> 16) & 255)) + Math.abs(((c1 >>> 8) & 255) - ((c2 >>> 8) & 255)) + Math.abs(((c1 >>> 0) & 255) - ((c2 >>> 0) & 255));
}

private static final int drawOver(int c1, int c2) {
return ((((c1 & 0xFF0000) + (c2 & 0xFF0000)) >>> 1) & 0xFF0000) | ((((c1 & 0x00FF00) + (c2 & 0x00FF00)) >>> 1) & 0x00FF00) | ((((c1 & 0x0000FF) + (c2 & 0x0000FF)) >>> 1) & 0x0000FF);
}

private int[] makeSolution() {
int[] res = new int[4 * N];
for (int i = 0; i < N; i++) {
res[4 * i + 0] = solution[i].r;
res[4 * i + 1] = solution[i].c;
res[4 * i + 2] = solution[i].radius;
res[4 * i + 3] = solution[i].color;
}
return res;
}

private void solve() {
greedy3();
}

class PairComparator implements Comparator<Pair<Long, Circle>> {
private Circle circle;

public void setCircle(Circle circle) {
this.circle = circle;
}

@Override
public int compare(Pair<Long, Circle> o1, Pair<Long, Circle> o2) {
boolean intersect1 = o1.second.intersect(circle);
boolean intersect2 = o2.second.intersect(circle);
if (intersect1) {
if (intersect2) {
} else {
return 1;
}
} else {
if (intersect2) {
return -1;
} else {

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

private void greedy3() {
Pair<Long, Circle>[] circles = new Pair[1 << 20];
for (int i = 0; i < circles.length; i++) {
circles[i] = new Pair<Long, Circle>(Long.MAX_VALUE, new Circle());
}
int circleIndex = 0;
int maxCircleIndex = 0;

// long currentScore = calculateScore(0, -1);
int step = 0;

boolean[][] used = new boolean[H][W];

PairComparator comparator = new PairComparator();

int mask = (1 << 4) - 1;

int pointIndex = -1;

double[] timelimits = new double[N];
double startTime = watch.getSecond();
double endTime = 9.5;
for (int i = 0; i < N; i++) {
timelimits[i] = startTime + (endTime - startTime) * (i + 1) / N;
}

for (int i = 0; i < N; i++) {

bestScore = (long) 1e18;

for (int loop = 0;; loop++, step++) {
if ((loop & mask) == mask) {
if (watch.getSecond() > timelimits[i]) {
break;
}
}

pointIndex++;
if (pointIndex >= points.length) {
pointIndex = 0;
}
solution[i].r = points[pointIndex].y;
solution[i].c = points[pointIndex].x;

if (used[solution[i].r][solution[i].c]) {
continue;
}
used[solution[i].r][solution[i].c] = true;

int colorR = solution[i].r;
int colorC = solution[i].c;

int givenRed = (givenImage[colorR][colorC] >>> 16) & 255;
int givenGreen = (givenImage[colorR][colorC] >>> 8) & 255;
int givenBlue = (givenImage[colorR][colorC] >>> 0) & 255;

int drawnRed = (drawnImage[colorR][colorC] >>> 16) & 255;
int drawnGreen = (drawnImage[colorR][colorC] >>> 8) & 255;
int drawnBlue = (drawnImage[colorR][colorC] >>> 0) & 255;

int red = givenRed * 2 - drawnRed;
red = Math.max(0, Math.min(255, red));
int green = givenGreen * 2 - drawnGreen;
green = Math.max(0, Math.min(255, green));
int blue = givenBlue * 2 - drawnBlue;
blue = Math.max(0, Math.min(255, blue));
solution[i].color = (red << 16) | (green << 8) | (blue);

long delta = calculateScoreEachRadius(i);

circles[circleIndex].first = delta;
Circle second = circles[circleIndex].second;
second.r = solution[i].r;
second.c = solution[i].c;
second.radius = solution[i].radius;
second.color = solution[i].color;
circleIndex++;
}
{

ArraysUtils.select(circles, 0, circleIndex, 0);
Pair<Long, Circle> pair = circles[0];
solution[i].r = pair.second.r;
solution[i].c = pair.second.c;
solution[i].radius = pair.second.radius;

int medianGiven = medianColor(givenImage, solution[i].r, solution[i].c, pair.second.radius);
int meanDrawn = meanColor(drawnImage, solution[i].r, solution[i].c, pair.second.radius);

int givenRed = (medianGiven >>> 16) & 255;
int givenGreen = (medianGiven >>> 8) & 255;
int givenBlue = (medianGiven >>> 0) & 255;

int drawnRed = (meanDrawn >>> 16) & 255;
int drawnGreen = (meanDrawn >>> 8) & 255;
int drawnBlue = (meanDrawn >>> 0) & 255;

int red = givenRed * 2 - drawnRed;
red = Math.max(0, Math.min(255, red));
int green = givenGreen * 2 - drawnGreen;
green = Math.max(0, Math.min(255, green));
int blue = givenBlue * 2 - drawnBlue;
blue = Math.max(0, Math.min(255, blue));

solution[i].color = (red << 16) | (green << 8) | (blue);

long delta = calculateScore(i);

circles[circleIndex].first = delta;
Circle second = circles[circleIndex].second;
second.r = solution[i].r;
second.c = solution[i].c;
second.radius = solution[i].radius;
second.color = solution[i].color;
circleIndex++;
}

maxCircleIndex = Math.max(maxCircleIndex, circleIndex);
ArraysUtils.select(circles, 0, circleIndex, 0);
Pair<Long, Circle> pair = circles[0];
Circle second = pair.second;
solution[i].r = second.r;
solution[i].c = second.c;
solution[i].radius = second.radius;
solution[i].color = second.color;
// bestScore = pair.first.longValue();
comparator.setCircle(solution[i]);
ArraysUtils.select(circles, 0, circleIndex, Math.min(circleIndex, N + 10 - i), comparator);
int nextCircleIndex = Math.min(circleIndex, N + 10 - i);
Arrays.sort(circles, 0, nextCircleIndex, comparator);
for (int j = 0; j < nextCircleIndex; j++) {
if (circles[j].second.intersect(solution[i])) {
nextCircleIndex = j;
break;
}
}
for (int j = nextCircleIndex; j < circleIndex; j++) {
used[circles[j].second.r][circles[j].second.c] = false;
}
circleIndex = nextCircleIndex;
// currentScore += bestScore;

update(i);

// if (i < 10 || Integer.bitCount(i) == 1 || i > N - 5) {
// Utils.debug("i", i, "step", step, "currentScore", currentScore);
// }
}

score = calculateScore();
Utils.debug("step", step, "score", score, "maxCircleIndex", maxCircleIndex);

}

private IntArray redForMedian = new IntArray(1 << 20);
private IntArray greenForMedian = new IntArray(1 << 20);
private IntArray blueForMedian = new IntArray(1 << 20);

private int medianColor(int[][] given, int colorR, int colorC, int radius) {
redForMedian.clear();
greenForMedian.clear();
blueForMedian.clear();
for (int r = Math.max(colorR - radius, 0); r <= Math.min(colorR + radius, H - 1); r++) {
int dc = (int) Math.sqrt(p2(radius) - p2(colorR - r));
for (int c = Math.max(colorC - dc, 0); c <= Math.min(colorC + dc, W - 1); c++) {
redForMedian.add((given[r][c] >>> 16) & 255);
greenForMedian.add((given[r][c] >>> 8) & 255);
blueForMedian.add((given[r][c] >>> 0) & 255);
}
}
ArraysUtils.select(redForMedian.values, 0, redForMedian.length, redForMedian.length >>> 1);
ArraysUtils.select(greenForMedian.values, 0, greenForMedian.length, greenForMedian.length >>> 1);
ArraysUtils.select(blueForMedian.values, 0, blueForMedian.length, blueForMedian.length >>> 1);
int medianRed = redForMedian.values[redForMedian.length >>> 1];
int medianGreen = greenForMedian.values[greenForMedian.length >>> 1];
int medianBlue = blueForMedian.values[blueForMedian.length >>> 1];
return (medianRed << 16) | (medianGreen << 8) | (medianBlue);
}

private MeanHelper redForMean = new MeanHelper();
private MeanHelper greenForMean = new MeanHelper();
private MeanHelper blueForMean = new MeanHelper();

private int meanColor(int[][] given, int colorR, int colorC, int radius) {
redForMean.clear();
greenForMean.clear();
blueForMean.clear();
for (int r = Math.max(colorR - radius, 0); r <= Math.min(colorR + radius, H - 1); r++) {
int dc = (int) Math.sqrt(p2(radius) - p2(colorR - r));
for (int c = Math.max(colorC - dc, 0); c <= Math.min(colorC + dc, W - 1); c++) {
redForMean.add((given[r][c] >>> 16) & 255);
greenForMean.add((given[r][c] >>> 8) & 255);
blueForMean.add((given[r][c] >>> 0) & 255);
}
}
int meanRed = (int) redForMean.mean();
int meanGreen = (int) greenForMean.mean();
int meanBlue = (int) blueForMean.mean();
return (meanRed << 16) | (meanGreen << 8) | (meanBlue);
}

private int p2(int t) {
return t * t;
}

private long calculateScore() {
for (int r = 0; r < H; ++r) {
Arrays.fill(drawnImage[r], 0);
}
for (int i = 0; i < N; ++i) {
for (int r = Math.max(solution[i].r - solution[i].radius, 0); r <= Math.min(solution[i].r + solution[i].radius, H - 1); r++) {
int dc = (int) Math.sqrt(p2(solution[i].radius) - p2(solution[i].r - r));
for (int c = Math.max(solution[i].c - dc, 0); c <= Math.min(solution[i].c + dc, W - 1); c++) {
if (p2(solution[i].r - r) + p2(solution[i].c - c) <= p2(solution[i].radius)) {
drawnImage[r][c] = drawOver(drawnImage[r][c], solution[i].color);
}
}
}
}
long diff = 0;
for (int r = 0; r < H; ++r) {
for (int c = 0; c < W; ++c) {
diff += getDiff(givenImage[r][c], drawnImage[r][c]);
}
}
return diff;
}

private long calculateScore(int from, int to) {
for (int r = 0; r < H; ++r) {
Arrays.fill(drawnImage[r], 0);
}
for (int i = from; i <= to; ++i) {
for (int r = Math.max(solution[i].r - solution[i].radius, 0); r <= Math.min(solution[i].r + solution[i].radius, H - 1); r++) {
int dc = (int) Math.sqrt(p2(solution[i].radius) - p2(solution[i].r - r));
for (int c = Math.max(solution[i].c - dc, 0); c <= Math.min(solution[i].c + dc, W - 1); c++) {
if (p2(solution[i].r - r) + p2(solution[i].c - c) <= p2(solution[i].radius)) {
drawnImage[r][c] = drawOver(drawnImage[r][c], solution[i].color);
}
}
}
}
long diff = 0;
for (int r = 0; r < H; ++r) {
for (int c = 0; c < W; ++c) {
diff += getDiff(givenImage[r][c], drawnImage[r][c]);
}
}
return diff;
}

private void update(int i) {
int minR = Math.max(solution[i].r - solution[i].radius, 0);
int maxR = Math.min(solution[i].r + solution[i].radius, H - 1);
for (int r = minR; r <= maxR; r++) {
int dc = (int) Math.sqrt(p2(solution[i].radius) - p2(solution[i].r - r));
int minC = Math.max(solution[i].c - dc, 0);
int maxC = Math.min(solution[i].c + dc, W - 1);
for (int c = minC; c <= maxC; c++) {
assert p2(solution[i].r - r) + p2(solution[i].c - c) <= p2(solution[i].radius);
drawnImage[r][c] = drawOver(drawnImage[r][c], solution[i].color);
}
}
}

private long calculateScore(int i) {
long diff = 0;
int minR = Math.max(solution[i].r - solution[i].radius, 0);
int maxR = Math.min(solution[i].r + solution[i].radius, H - 1);
for (int r = minR; r <= maxR; r++) {
int dc = (int) Math.sqrt(p2(solution[i].radius) - p2(solution[i].r - r));
int minC = Math.max(solution[i].c - dc, 0);
int maxC = Math.min(solution[i].c + dc, W - 1);
for (int c = minC; c <= maxC; c++) {
assert p2(solution[i].r - r) + p2(solution[i].c - c) <= p2(solution[i].radius);
diff -= getDiff(givenImage[r][c], drawnImage[r][c]);
diff += getDiff(givenImage[r][c], drawOver(drawnImage[r][c], solution[i].color));
}
}
return diff;
}

private long calculateScoreEachRadius(int i) {
int r0 = solution[i].r;
int c0 = solution[i].c;
int color0 = solution[i].color;

long diff = 0;
long bestDiff = (long) 1e18;
int bestRadius = 0;
for (int radius = 0; radius < drs.length; radius++) {
if (radius > bestRadius + 3) {
break;
}

IntArray dr = drs[radius];
IntArray dc = dcs[radius];

for (int d = 0; d < dr.length; d++) {
int r = r0 + dr.values[d];
int c = c0 + dc.values[d];
if (r < 0 || r >= H) {
continue;
}
if (c < 0 || c >= W) {
continue;
}

diff -= getDiff(givenImage[r][c], drawnImage[r][c]);
diff += getDiff(givenImage[r][c], drawOver(drawnImage[r][c], color0));

}

if (diff < bestDiff) {
bestDiff = diff;
bestRadius = radius;
}

}

solution[i].radius = bestRadius;
return bestDiff;
}

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

int H = Integer.parseInt(br.readLine());

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

int N = Integer.parseInt(br.readLine());

CirclesMix cm = new CirclesMix();
int[] ret = cm.drawImage(H, pixels, N);

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

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<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
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<T, S> other = (Pair<T, S>) 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<T, S> o) {
return first.compareTo(o.first);
}
}

class Circle implements Comparable<Circle> {
int r;
int c;
int radius;
int color;

@Override
public int compareTo(Circle o) {
if (radius > o.radius) {
return -1;
}
if (radius < o.radius) {
return 1;
}
return 0;
}

public boolean intersect(Circle circle) {
int dr = r - circle.r;
int dc = c - circle.c;
return Math.sqrt(dr * dr + dc * dc) <= radius + circle.radius;
}
}

class ArraysUtils {
private ArraysUtils() {
}

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

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());
ArraysUtils.swap(a, i, j);
}
}

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

private static final void select0(int[] a, int l, int r, int k) {
while (l < r) {
int i = ArraysUtils.partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

private static final void select0(double[] a, int l, int r, int k) {
while (l < r) {
int i = ArraysUtils.partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

private static final void select0(Comparable[] a, int l, int r, int k) {
while (l < r) {
int i = ArraysUtils.partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

private static final <T> void select0(T[] a, int l, int r, int k, Comparator<T> comparator) {
while (l < r) {
int i = ArraysUtils.partition3(a, l, r, comparator);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

public static final void select(int[] a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

public static final void select(double[] a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

public static final void select(Comparable[] a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

public static final <T> void select(T[] a, int startInclusive, int endExclusive, int k, Comparator<T> comparator) {
select0(a, startInclusive, endExclusive - 1, k, comparator);
}

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

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

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

public static final void sort3(int[] a, int i, int j, int k) {
if (a[i] > a[j]) {
swap(a, i, j);
}
if (a[i] > a[k]) {
swap(a, i, k);
}
if (a[j] > a[k]) {
swap(a, j, k);
}
}

public static final void sort3(double[] a, int i, int j, int k) {
if (a[i] > a[j]) {
swap(a, i, j);
}
if (a[i] > a[k]) {
swap(a, i, k);
}
if (a[j] > a[k]) {
swap(a, j, k);
}
}

public static final void sort3(Comparable[] a, int i, int j, int k) {
if (a[i].compareTo(a[j]) > 0) {
swap(a, i, j);
}
if (a[i].compareTo(a[k]) > 0) {
swap(a, i, k);
}
if (a[j].compareTo(a[k]) > 0) {
swap(a, j, k);
}
}

public static final <T> void sort3(T[] a, int i, int j, int k, Comparator<T> comparator) {
if (comparator.compare(a[i], a[j]) > 0) {
swap(a, i, j);
}
if (comparator.compare(a[i], a[k]) > 0) {
swap(a, i, k);
}
if (comparator.compare(a[j], a[k]) > 0) {
swap(a, j, k);
}
}

public static final int partition3(int[] 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;
int v = a[r1];
int i = l - 1;
int j = r1;
for (;;) {
for (; a[++i] < v;) {
}
for (; a[--j] > v;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final int partition3(double[] 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;
double v = a[r1];
int i = l - 1;
int j = r1;
for (;;) {
for (; a[++i] < v;) {
}
for (; a[--j] > v;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final int partition3(Comparable[] 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;
Comparable v = a[r1];
int i = l - 1;
int j = r1;
for (;;) {
for (; a[++i].compareTo(v) < 0;) {
}
for (; a[--j].compareTo(v) > 0;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

public static final <T> int partition3(T[] a, int l, int r, Comparator<T> 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[r1];
int i = l - 1;
int j = r1;
for (;;) {
for (; comparator.compare(a[++i], v) < 0;) {
}
for (; comparator.compare(a[--j], v) > 0;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

}

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 Point implements Comparable<Point> {

public int x;
public int y;

public Point() {
this(0, 0);
}

public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}

public Point add(Point point) {
return new Point(x + point.x, y + point.y);
}

public Point subtract(Point point) {
return new Point(x - point.x, y - point.y);
}

public Point multiply(int a) {
return new Point(a * x, a * y);
}

public Point divide(int a) {
return new Point(x / a, y / a);
}

public double cross(Point point) {
return x * point.y - y * point.x;
}

public Point operator(Point a) {
return new Point(x * a.x - y * a.y, x * a.y + y * a.x);
}

@Override
public int compareTo(Point o) {
if (x == o.x) {
if (y == o.y) {
return 0;
} else if (y < o.y) {
return -1;
} else {
return 1;
}
} else if (x < o.x) {
return -1;
} else {
return 1;
}
}

@Override
public String toString() {
return "(" + x + "," + y + ")";
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
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;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}

}

class MeanHelper {
private double max;
private double min;
private double sum;
private double sumSquared;
private double sumCubed;
private double sumFourth;
private int count;
private String description;

public MeanHelper() {
clear();
}

public void add(double value) {
max = Math.max(max, value);
min = Math.min(min, value);
sum += value;
double valueSquared = value * value;
sumSquared += valueSquared;
sumCubed += valueSquared * value;
sumFourth += valueSquared * valueSquared;
count++;
}

public double kurtosis(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double sigma = standardDeviation(0);
if (sigma == 0) {
return 0;
}
double mu = mean(0);
return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
}

public double skewness(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double sigma = standardDeviation(0);
if (sigma == 0) {
return 0;
}
double mu = mean(0);
return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
}

public double mean() {
if (isEmpty()) {
throw new AssertionError();
}
return sum / count;
}

public double mean(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return sum / count;
}

public double sumOfSquaredError() {
if (isEmpty()) {
throw new AssertionError();
}
return sumSquared - sum * sum / count;
}

public double variance() {
if (isEmpty()) {
throw new AssertionError();
}
double E_XX = sumSquared / count;
double E_X = sum / count;
return E_XX - E_X * E_X;
}

public double variance(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double E_XX = sumSquared / count;
double E_X = sum / count;
return E_XX - E_X * E_X;
}

public double unbiasedVariance() {
if (count - 1 == 0) {
throw new AssertionError();
}
return (count * variance()) / (count - 1);
}

private double unbiasedVariance(double defaultValue) {
if (count - 1 == 0) {
return defaultValue;
}
return (count * variance()) / (count - 1);
}

public double standardDeviation() {
return Math.sqrt(variance());
}

public double standardDeviation(double defaultValue) {
return Math.sqrt(variance(defaultValue));
}

public double unbiasedStandardDeviation() {
return Math.sqrt(unbiasedVariance());
}

public double unbiasedStandardDeviation(double defaultValue) {
return Math.sqrt(unbiasedVariance(defaultValue));
}

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

public void clear() {
max = Double.NEGATIVE_INFINITY;
min = Double.POSITIVE_INFINITY;
sum = 0;
sumSquared = 0;
sumCubed = 0;
sumFourth = 0;
count = 0;
description = null;
}

public double max() {
if (isEmpty()) {
throw new AssertionError();
}
return max;
}

public double max(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return max;
}

public double min() {
if (isEmpty()) {
throw new AssertionError();
}
return min;
}

public double min(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return min;
}

public int count() {
return count;
}

public double sum() {
return sum;
}

public double sumSquared() {
return sumSquared;
}

public void setDescription(String description) {
if (this.description != null) {
if (this.description.hashCode() != description.hashCode()) {
throw new AssertionError();
}
if (!this.description.equals(description)) {
throw new AssertionError();
}
} else {
this.description = description;
}
}

public String getDescription() {
return description;
}
}




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


このページのトップヘ