EvbCFfp1XB

problem and my answer.



Approach 貪欲法を使いました。

  • 各ターン 4.5/K 秒間で見つかった最も良い増減を適用する。
  • length = 1,2,... と増やしていって、最もスコアを改善するペアを見つける。
  • v は、 min ( min( A[i+a] - (i+a+1) ) , min( (k+a+1) - A[k+a] ) )  for (a = 0,1,...,length)

source code

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

public class Main {
private int N;
private int K;
private int[] A;

private int[] is;
private int[] js;
private int[] ks;
private int[] ls;
private int[] vs;

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

public static void main(String[] args) {
new Main().run();
}

private void run() {
readProblem();
solve();
writeSolution();
}

private void readProblem() {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
String line = br.readLine();
String[] split = line.split(" ");
N = Integer.parseInt(split[0]);
K = Integer.parseInt(split[1]);
A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(br.readLine());
}

is = new int[K];
js = new int[K];
ks = new int[K];
ls = new int[K];
vs = new int[K];

} catch (Exception e) {
e.printStackTrace();
}
}

private void solve() {
greedy();
Utils.debug("score", calculateScore(), "time", watch.getSecondString());
Utils.debug("score", 1e9 - calculateScore(), "time", watch.getSecondString());
Utils.debug("score", 41e9 - 41 * calculateScore(), "time", watch.getSecondString());
}

private void greedy() {
double startTime = watch.getSecond();
for (int k = 0; k < K; k++) {

long best = (long) 1e9;
int besti = 0;
int bestj = 0;
int bestk = 1;
int bestl = 1;
int bestv = 0;
{
long score = calculateScore();
if (score < best) {
best = score;
}
}
for (int numIterations = 0;; numIterations++) {

int length = numIterations;
int bestIValue = (int) -1e9;
int bestI = -1;
int bestKValue = (int) -1e9;
int bestK = -1;
for (int i = 0; i + length < N; i++) {
int minI = (int) 1e9;
int minK = (int) 1e9;
for (int j = 0; j <= length; j++) {
minI = Math.min(minI, A[i + j] - (i + j + 1));
minK = Math.min(minK, (i + j + 1) - A[i + j]);
}
if (minI * (length + 1) > bestIValue) {
bestIValue = minI * (length + 1);
bestI = i;
}
if (minK * (length + 1) > bestKValue) {
bestKValue = minK * (length + 1);
bestK = i;
}
}
int i2 = bestI;
int j2 = i2 + length;
int k2 = bestK;
int l2 = k2 + length;
is[k] = i2;
js[k] = j2;
ks[k] = k2;
ls[k] = l2;
for (int plusAlpha = 0; plusAlpha < 2; plusAlpha++) {
vs[k] = Math.min(bestIValue / (length + 1), bestKValue / (length + 1));
if (plusAlpha > 0) {
if (watch.getSecond() - startTime >= 4.5 * (k + 1) / K) {
Utils.debug(k, numIterations, "best", best, "time", watch.getSecondString());
break;
}
vs[k] += 2000;
}
if (isValid(k)) {
next(k);
long score = calculateScore();
if (score < best) {
best = score;
besti = is[k];
bestj = js[k];
bestk = ks[k];
bestl = ls[k];
bestv = vs[k];
}
previous(k);
}
}

if (watch.getSecond() - startTime >= 4.5 * (k + 1) / K) {
Utils.debug(k, numIterations, "best", best, "time", watch.getSecondString());
break;
}
}
is[k] = besti;
js[k] = bestj;
ks[k] = bestk;
ls[k] = bestl;
vs[k] = bestv;
if (isValid(k)) {
next(k);
}

}
}

private void next(int k) {
int v = vs[k];
for (int i = is[k]; i <= js[k]; i++) {
A[i] -= v;
}
for (int i = ks[k]; i <= ls[k]; i++) {
A[i] += v;
}
}

private void previous(int k) {
int v = vs[k];
for (int i = is[k]; i <= js[k]; i++) {
A[i] += v;
}
for (int i = ks[k]; i <= ls[k]; i++) {
A[i] -= v;
}
}

private boolean isValid(int k) {
if (vs[k] < 0 || vs[k] >= N) {
return false;
}

if (is[k] > js[k]) {
return false;
}
if (ks[k] > ls[k]) {
return false;
}

if (js[k] - is[k] != ls[k] - ks[k]) {
return false;
}

for (int i = is[k]; i <= js[k]; i++) {
if (A[i] - vs[k] <= 0) {
return false;
}
}
for (int i = ks[k]; i <= ls[k]; i++) {
if (A[i] + vs[k] > N) {
return false;
}
}
return true;
}

private void writeSolution() {
for (int k = 0; k < K; k++) {
is[k]++;
js[k]++;
ks[k]++;
ls[k]++;
}

for (int k = 0; k < K; k++) {
System.out.println(is[k] + " " + js[k] + " " + ks[k] + " " + ls[k] + " " + vs[k]);
}
System.out.flush();
}

private long calculateScore() {
long score = 0;
for (int i = 0; i < N; i++) {
score += Math.abs(A[i] - (i + 1));
}
return score;
}
}

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

}




Approach 貪欲法 + 焼きなまし法 を使いました。

  • 貪欲法
    • オーダーを並べ替える。
      • 納期が早い、数量が多い、最早開始日時が早い、(納期 - 最早開始日時) が短いオーダーを優先する。
    • 最早開始日時 から使える枠(リソースと時間のペア)を探す。
      • 同じパンの枠がある場合はその枠を優先する。
      • 同じパンの枠に追加するとき、追加した後のキャパシティの小さい枠を優先する。
      • 枠が空のとき、キャパシティの大きい枠を優先する。
  • 焼きなまし法
    • 近傍1 : オーダーを納期に間に合うように移動する。
      • 別のパンがあって、無効な移動なことがあります。
    • 近傍2 : オーダーを同じパンの別の枠に移動する。
      • 納期に間に合わなくても気にしない。
    • 近傍3 : オーダーを同じパンの別の枠のオーダーと交換する。
    • 近傍4 : ある枠の全てのオーダーを、別の枠の全てのオーダーと交換する。
      • 別の枠は、リソースはランダムで、時間は前後 ± 1。
      • 枠のオーダーの最早開始日時の最大値と数量の和を持つと、有効な交換かどうかO(1)で判定できる。
      • 時間は前後 ± 1なので、スコアの差を、事前に計算できます。
    • 近傍5 : ある枠の全てのオーダーを、同じパンの別の枠に移動する。
  • 高速化
    • 構造体のメンバーを vector にコピーして、vector を使いました。



problem https://github.com/kosakkun/Typical-MM/tree/master/GraphColoring

Approach
  • 貪欲法で有効な彩色を見つける。
  • その状態から色を1つ減らして、焼きなまし法やタブーサーチで有効な彩色を見つける。これを繰り返す。

  • 診断人さんが使ってたタブーサーチが強かった。

  • 貪欲法
    • 次数の大きい頂点から彩色する。
  • タブーサーチ
    • 有効な彩色が見つかったら、ある色を無色にして、色を1つ減らす。
    • 無色の頂点から1つランダムに選ぶ。
    • その頂点に隣接する頂点の色ごとに次数の和を求める。
    • タブーリストにない色で、最も次数の和が小さい色で彩色する。
      • 全ての色がタブーリストに載ってたら、タブーリストを無視して、最も次数の和が小さい色で彩色する。
    • 隣接する頂点が同じ色なら、その頂点を無色にする。
    • 彩色した色と頂点のペアをタブーリストに加える。





source code

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

public class GraphColoring {
private static final int NUM_TABU_LIST = 75;
private static final int NG = ((1 << 16) - 1);

private int numVertexes;
private int numEdges;
private IntSet[] nextVertexSet;
private int usedColors;
private int[] vertexToColor;

private int bestUsedColors;
private int[] bestVertexToColor;

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

private int[] tabuList = new int[NUM_TABU_LIST];
private int indexOfTabuList = 0;
private boolean[][] isTabu;

private int[] colorToSumDegree = new int[256];

private int[] run(int N, int M, int[] a, int[] b) {
init(N, M, a, b);
solve();
return vertexToColor;
}

private void init(int N, int M, int[] a, int[] b) {
this.numVertexes = N;
this.numEdges = M;

Utils.debug("numVertexes", numVertexes, "numEdges", numEdges);

nextVertexSet = new IntSet[numVertexes];
for (int i = 0; i < numVertexes; i++) {
nextVertexSet[i] = new IntSet(numVertexes);
}
for (int i = 0; i < numEdges; i++) {
nextVertexSet[a[i]].add(b[i]);
nextVertexSet[b[i]].add(a[i]);
}

vertexToColor = new int[numVertexes];
bestVertexToColor = new int[numVertexes];
for (int i = 0; i < numVertexes; i++) {
vertexToColor[i] = -1;
bestVertexToColor[i] = -1;
}

bestUsedColors = (int) 1e9;

uncoloredVertexSet = new IntSet(numVertexes);

isTabu = new boolean[numVertexes][256];
}

private void solve() {
greedy();
tabuSearch();
}

private void tabuSearch() {
for (int numIterations = 0;; numIterations++) {
if ((numIterations & ((1 << 10) - 1)) == 0) {
if (watch.getSecond() >= 9.5) {
loadBest();
Utils.debug("numIterations", numIterations, "usedColors", usedColors, "time", watch.getSecondString());
break;
}
}
while (uncoloredVertexSet.size() == 0) {
saveBest();
Utils.debug("numIterations", numIterations, "usedColors", usedColors, "time", watch.getSecondString());
usedColors--;
for (int v = 0; v < numVertexes; v++) {
if (vertexToColor[v] == usedColors) {
uncoloredVertexSet.add(v);
}
}
initTabuList();
}

int vertex = uncoloredVertexSet.get((int) (uncoloredVertexSet.size() * rng.nextDouble()));

for (int color = 0; color < usedColors; color++) {
colorToSumDegree[color] = 0;
}
for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
int nextVertex = nextVertexSet[vertex].get(i);
colorToSumDegree[vertexToColor[nextVertex]] += nextVertexSet[nextVertex].size();
}

int bestSumDegree = (int) 1e9;
int bestColor = -1;
for (int color = 0; color < usedColors; color++) {
if (isTabu[vertex][color]) {
continue;
}

if (colorToSumDegree[color] < bestSumDegree) {
bestSumDegree = colorToSumDegree[color];
bestColor = color;
}
}

if (bestColor == -1) {
for (int color = 0; color < usedColors; color++) {
if (colorToSumDegree[color] < bestSumDegree) {
bestSumDegree = colorToSumDegree[color];
bestColor = color;
}
}
}

vertexToColor[vertex] = bestColor;
uncoloredVertexSet.removeValue(vertex);

for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
int nextVertex = nextVertexSet[vertex].get(i);
if (vertexToColor[nextVertex] == bestColor) {
vertexToColor[nextVertex] = usedColors;
uncoloredVertexSet.add(nextVertex);
}
}

addTabu(vertex, bestColor);

}
}

private void addTabu(int vertex, int color) {
int tabu = tabuList[indexOfTabuList];
if (vertex(tabu) != NG) {
isTabu[vertex(tabu)][color(tabu)] = false;
}

tabuList[indexOfTabuList] = encode(vertex, color);
isTabu[vertex][color] = true;

indexOfTabuList++;
if (indexOfTabuList >= NUM_TABU_LIST) {
indexOfTabuList = 0;
}
}

private void initTabuList() {
for (int i = 0; i < NUM_TABU_LIST; ++i) {
int tabu = tabuList[i];
if (vertex(tabu) != NG) {
isTabu[vertex(tabu)][color(tabu)] = false;
}
tabuList[i] = encode(NG, NG);
}
}

private void greedy() {
ArrayList<Pair<Integer, Integer>> degreeAndVertexPairs = new ArrayList<>();
for (int vertex = 0; vertex < numVertexes; vertex++) {
degreeAndVertexPairs.add(new Pair<Integer, Integer>(-nextVertexSet[vertex].size(), vertex));
}
Collections.sort(degreeAndVertexPairs);
for (int i = 0; i < degreeAndVertexPairs.size(); i++) {
int vertex = degreeAndVertexPairs.get(i).second.intValue();
for (int color = 0; color < 256; color++) {
if (canUse(vertex, color)) {
vertexToColor[vertex] = color;
break;
}
}
}
usedColors = calculateUsedColors();
saveBest();
Utils.debug("greedy", "usedColors", usedColors, "time", watch.getSecondString());
}

private int calculateUsedColors() {
HashSet<Integer> set = new HashSet<>();
for (int vertex = 0; vertex < numVertexes; vertex++) {
set.add(vertexToColor[vertex]);
}
return set.size();
}

private boolean canUse(int vertex, int color) {
for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
int nextVertex = nextVertexSet[vertex].get(i);
if (vertexToColor[nextVertex] == color) {
return false;
}
}
return true;
}

private void saveBest() {
if (usedColors < bestUsedColors) {
bestUsedColors = usedColors;
for (int i = 0; i < numVertexes; i++) {
bestVertexToColor[i] = vertexToColor[i];
}
}
}

private void loadBest() {
usedColors = bestUsedColors;
for (int i = 0; i < numVertexes; i++) {
vertexToColor[i] = bestVertexToColor[i];
}
}

private static final int encode(int vertex, int color) {
return (vertex << 16) | color;
}

private static final int vertex(int v) {
return v >>> 16;
}

private static final int color(int v) {
return v & ((1 << 16) - 1);
}

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

String line = br.readLine();
String[] split = line.split(" ");
int N = Integer.parseInt(split[0]);
int M = Integer.parseInt(split[1]);
int[] a = new int[M];
int[] b = new int[M];
for (int i = 0; i < M; i++) {
line = br.readLine();
split = line.split(" ");
a[i] = Integer.parseInt(split[0]);
b[i] = Integer.parseInt(split[1]);
}

GraphColoring gc = new GraphColoring();
int[] ret = gc.run(N, M, a, b);
for (int i = 0; i < N; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (IOException e) {
e.printStackTrace();
}
}

}

class IntSet {
private static final int EMPTY = -1;
private int size;
private int[] indexToValue;
private int[] valueToIndex;

public IntSet(int capacity) {
this.size = 0;
indexToValue = new int[capacity];
valueToIndex = new int[capacity];
Arrays.fill(valueToIndex, EMPTY);
}

public boolean add(int value) {
if (valueToIndex[value] != EMPTY) {
return false;
}
indexToValue[size] = value;
valueToIndex[indexToValue[size]] = size;
size++;
return true;
}

public boolean remove(int index) {
if (size == 0) {
return false;
}
assert index < size;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[size - 1];
indexToValue[size - 1] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[size - 1]] = EMPTY;

size--;
return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public int get(int index) {
assert index < size;
return indexToValue[index];
}

public int indexOf(int value) {
return valueToIndex[value];
}

public int size() {
return size;
}

public boolean isEmpty() {
return size() <= 0;
}

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

}

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

}


このページのトップヘ