EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)

March 2018



Approach Guided Local Search(GLS) を使いました。 TCO2016 MM R3 で CatalinT さんが使ったものと本質的に同じもの。
 ちなみに、CatalinT さんの C++ のを Java になおして実行したら、普通に TLE して、 「C++ 早えー。または、Java 遅せー」と思いました。次の瞬間「どうなってんの?」と自分の目を疑いました。スコアをよく見ると、自分の最終提出(相対スコアで約99.4%)よりいいスコアを出してました。TLE した後一瞬だけ実行された GLS に負けていました。


Score

kosakkunさんの適当なSAGLS
1494.01053692588624485.4605733810348
2530.1168033455548517.7671599235256
3367.93392449788024360.1746149965883
4493.59914978630474486.95184401291823
5364.88013978229515364.41532260772044
6304.6700126557216301.3079655440071
7482.3144426341467469.5112459237517
8579.3091643733519572.0601824834589
9352.68717930411583345.82962544607824
10558.819510787507553.5887500736407




source code

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

public class EuclideanTravellingSalesmanProblem {
private static final long START = System.nanoTime();
private static final long END = (long) (START + 9.8 * 1e9);
private int N;
private double[][] distance;

private int[] nodeToCity;
private double score;

private int[] bestNodeToCity;
private double bestScore;

public int[] getOrder(double[] x, double[] y) {
init(x, y);
GLS();
return nodeToCity;
}

private void init(double[] x, double[] y) {
this.N = x.length;

nodeToCity = new int[N];
bestNodeToCity = new int[N];
for (int i = 0; i < nodeToCity.length; i++) {
nodeToCity[i] = i;
}

distance = new double[N][N];
for (int i = 0; i < distance.length; i++) {
for (int j = 0; j < i; j++) {
double dx = x[i] - x[j];
double dy = y[i] - y[j];
distance[i][j] = Math.sqrt(dx * dx + dy * dy);
distance[j][i] = distance[i][j];
}
}

score = calculateScore();
bestScore = score;

}

private void GLS() {
double[][] penalty = new double[N][N];
int[] maxUtilNodes = new int[N];
boolean[] isTarget = new boolean[N];
Arrays.fill(isTarget, true);

for (int iteration = 0;; iteration++) {
if ((iteration & ((1 << 10) - 1)) == 0) {
if (System.nanoTime() >= END) {
score = bestScore;
System.arraycopy(bestNodeToCity, 0, nodeToCity, 0, N);
break;
}
}

for (int i = 0, node = 0; i < N; i++, node = (node + 1) % N) {
if (!isTarget[nodeToCity[node]]) {
continue;
}

int B = node;
int A = B - 1;
if (A < 0) {
A = N - 1;
}

boolean update = false;
for (int node2 = 0; node2 < N; node2++) {
if (node2 == node) {
continue;
}
int C = node2;
int D = node2 + 1;
if (D == N) {
D = 0;
}

if (C == A) {
continue;
}
if (D == B) {
continue;
}

double A_BC_D = distance[nodeToCity[A]][nodeToCity[B]] + distance[nodeToCity[C]][nodeToCity[D]];
double A_CB_D = distance[nodeToCity[A]][nodeToCity[C]] + distance[nodeToCity[B]][nodeToCity[D]];
double deltaScore = A_CB_D - A_BC_D;

double pA_BC_D = penalty[nodeToCity[A]][nodeToCity[B]] + penalty[nodeToCity[C]][nodeToCity[D]];
double pA_CB_D = penalty[nodeToCity[A]][nodeToCity[C]] + penalty[nodeToCity[B]][nodeToCity[D]];
double deltaPenalty = (0.3 * bestScore / N) * (pA_CB_D - pA_BC_D);

if (deltaScore + deltaPenalty < 0) {
update = true;
score += deltaScore;

if (B <= C) {
for (int l = B, r = C; l < r; l++, r--) {
int swap = nodeToCity[l];
nodeToCity[l] = nodeToCity[r];
nodeToCity[r] = swap;
}
} else {
for (int l = C + 1, r = B - 1; l < r; l++, r--) {
int swap = nodeToCity[r];
nodeToCity[r] = nodeToCity[l];
nodeToCity[l] = swap;
}
}

if (score < bestScore) {
bestScore = score;
System.arraycopy(nodeToCity, 0, bestNodeToCity, 0, N);
}

break;
}

}

if (update) {
i = -1;
} else {
isTarget[nodeToCity[node]] = false;
}
}

double maxUtil = -1e9;
int size = 0;
for (int node = 0; node < N; node++) {
double util = distance[nodeToCity[node]][nodeToCity[(node + 1) % N]] / (penalty[nodeToCity[node]][nodeToCity[(node + 1) % N]] + 1.0);
if (util > maxUtil) {
maxUtil = util;
size = 0;
maxUtilNodes[size++] = node;
} else if (Math.abs(util - maxUtil) < 1e-5) {
maxUtilNodes[size++] = node;
}
}
for (int i = 0; i < size; i++) {
int node = maxUtilNodes[i];
int city1 = nodeToCity[node];
int city2 = nodeToCity[(node + 1) % N];
penalty[city1][city2]++;
penalty[city2][city1]++;
isTarget[city1] = true;
isTarget[city2] = true;
}

}
}

private double calculateScore() {
double score = 0.0;
for (int i = 0; i < N; i++) {
score += distance[nodeToCity[i]][nodeToCity[(i + 1) % N]];
}
return score;
}

public static void main(String[] args) {
EuclideanTravellingSalesmanProblem o = new EuclideanTravellingSalesmanProblem();

try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {

int N = Integer.parseInt(reader.readLine().trim());
double[] x = new double[N];
double[] y = new double[N];
for (int i = 0; i < N; i++) {
String[] split = reader.readLine().trim().split(" ");
x[i] = Double.parseDouble(split[0]);
y[i] = Double.parseDouble(split[1]);
}

int[] ret = o.getOrder(x, y);

StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++)
sb.append(ret[i] + "\n");

System.out.println(sb.toString());
System.out.flush();

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




yowaさんのスコアだと、0.905位。上位から4%ほど悪いらしい。

Approach
  • コインが200以下で始まった時、即終了。(1回くらいnotePlayしても良かったかも?)
  • コインが最初の25%以下になったら終了。(kelly criterion より多く賭けているとき終了というのを入れていた。そして、終了の時のコインの枚数を見ると6枚とかで、kelly criterionより全然少なく賭けていることがわかった。そしたら、最初のコインの枚数から大きく減るはずがないので、これを入れておいた。)
  • notePlay する確率 1から0に線形に減らす。(乱数使いたくなかった。)
    • notePlay することにしても、期待値+ボーナスが最も良いマシーンが40回以上 notePlay してたら、 quickPlay に変える。
    • quickPlay することにしても、期待値が1以下なら notePlay に変える。
  • リールは重複除去して覚える。(Testerで調べると、長さが30のリールでも、重複除去してもだいたい28〜30パターン残ったので、これで充分だと思った。)
  • ボーナス = 2 * Math.pow((40 - 選んだマシーンの現在のnotePlayの回数) / 40, 2) (UCBから変えた。)

強化学習したかった。



source code

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

public class BrokenSlotMachines {
private XorShift rng = new XorShift(System.nanoTime());

private int coins;
private int maxTime;
private int noteTime;
private int numMachines;

private int startCoins;

private ArrayList<Character>[][] wheels;
private HashSet<String>[][] wheelPatternSet;

private int[] countNote;
private double[] expected;

public int playSlots(int coins, int maxTime, int noteTime, int numMachines) {
init(coins, maxTime, noteTime, numMachines);

solve();

Utils.debug("coins", this.coins);
return 0;
}

private void solve() {
for (int time = 0; time < maxTime;) {
if (coins <= 0.25 * startCoins) {
break;
}

calculateExpected();

int bestMachine = -1;

boolean isExplore = isExplore(time);
if (isExplore) {

double[] evPlusBonus = new double[numMachines];
for (int i = 0; i < evPlusBonus.length; i++) {
evPlusBonus[i] = expected[i] + bonus(i);
}
bestMachine = argMax(evPlusBonus);
if (countNote[bestMachine] >= 40) {
isExplore = false;
bestMachine = argMax(expected);
}

} else {
bestMachine = argMax(expected);
if (expected[bestMachine] < 1) {

isExplore = true;
double[] evPlusBonus = new double[numMachines];
for (int i = 0; i < evPlusBonus.length; i++) {
evPlusBonus[i] = expected[i] + bonus(i);
}
bestMachine = argMax(evPlusBonus);
}
}

if (coins <= 200) {
if (expected[argMax(expected)] > 1.1) {

} else {
break;
}
}

coins--;

int value;
String[] notePlay;
boolean useNote = isExplore;
useNote &= time + noteTime < maxTime;
if (useNote) {
notePlay = PlaySlots.notePlay(bestMachine, 1);
value = Integer.parseInt(notePlay[0]);
for (int c = 0; c < 3; c++) {
StringBuilder pattern = new StringBuilder();
for (int r = 0; r < 3; r++) {
pattern.append(notePlay[1].charAt(r * 3 + c));
}
if (wheelPatternSet[bestMachine][c].add(pattern.toString())) {
for (int r = 0; r < 3; r++) {
wheels[bestMachine][c].add(notePlay[1].charAt(r * 3 + c));
}
}
}
countNote[bestMachine]++;
} else {
value = PlaySlots.quickPlay(bestMachine, 1);
}
coins += value;
if (useNote) {
time += noteTime;
} else {
time++;
}
}

calculateExpected();

Utils.debug("expected", toString(expected));
}

private String[] toString(double[] expected2) {
String[] s = new String[expected2.length];
for (int i = 0; i < s.length; i++) {
s[i] = String.format("%.2f", expected2[i]);
}
return s;
}

private static int argMax(double[] values) {
int maxIndex = -1;
double max = -1e99;
for (int i = 0; i < values.length; i++) {
if (values[i] > max) {
max = values[i];
maxIndex = i;
}
}
return maxIndex;
}

private boolean isExplore(int time) {
double nextDouble = rng.nextDouble();
double range = updateRange(1.0, (double) 0, (double) time, (double) 0, (double) (maxTime - 1), 1.0);
return nextDouble < range;
}

private double bonus(int machine) {
if (countNote[machine] > 40) {
return 0;
}
return updateRange(2.0, 0, countNote[machine], 0, 40, 2.0);
}

private double updateRange(double startRange, double endRange, double time, double startTime, double endTime, double exp) {
if (time > endTime) {
return 0;
}
return endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), exp);
}

private int count(ArrayList<Character> s, char c) {
int ret = 0;
for (int i = 0; i < s.size(); i++) {
if (s.get(i) == c)
ret++;
}
return ret;
}

private void calculateExpected() {
int[] payouts = new int[numMachines];
expected = new double[numMachines];
for (int i = 0; i < numMachines; i++) {
payouts[i] += count(wheels[i][0], 'A') * count(wheels[i][1], 'A') * count(wheels[i][2], 'A') * 1000;
payouts[i] += count(wheels[i][0], 'B') * count(wheels[i][1], 'B') * count(wheels[i][2], 'B') * 200;
payouts[i] += count(wheels[i][0], 'C') * count(wheels[i][1], 'C') * count(wheels[i][2], 'C') * 100;
payouts[i] += count(wheels[i][0], 'D') * count(wheels[i][1], 'D') * count(wheels[i][2], 'D') * 50;
payouts[i] += count(wheels[i][0], 'E') * count(wheels[i][1], 'E') * count(wheels[i][2], 'E') * 20;
payouts[i] += count(wheels[i][0], 'F') * count(wheels[i][1], 'F') * count(wheels[i][2], 'F') * 10;
payouts[i] += count(wheels[i][0], 'G') * count(wheels[i][1], 'G') * count(wheels[i][2], 'G') * 5;
if (payouts[i] == 0) {
expected[i] = 0;
continue;
}
expected[i] = 1.0 * payouts[i] / wheels[i][0].size() / wheels[i][1].size() / wheels[i][2].size();
}
}

private void init(int coins, int maxTime, int noteTime, int numMachines) {
this.coins = coins;
this.startCoins = coins;
this.maxTime = maxTime;
this.noteTime = noteTime;
this.numMachines = numMachines;
wheels = new ArrayList[numMachines][3];
for (int i = 0; i < wheels.length; i++) {
for (int j = 0; j < 3; j++) {
wheels[i][j] = new ArrayList<Character>();
}
}

wheelPatternSet = new HashSet[numMachines][3];
for (int i = 0; i < wheelPatternSet.length; i++) {
for (int j = 0; j < 3; j++) {
wheelPatternSet[i][j] = new HashSet<String>();
}
}

countNote = new int[numMachines];
Utils.debug("coins", coins, "maxTime", maxTime, "noteTime", noteTime, "numMachines", numMachines);
}

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

int coins = BR.readInt();
int maxTime = BR.readInt();
int noteTime = BR.readInt();
int numMachines = BR.readInt();

BrokenSlotMachines pw = new BrokenSlotMachines();
int ret = pw.playSlots(coins, maxTime, noteTime, numMachines);

System.out.println(ret);
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 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 Princesses に一番近いところから入る。Princessがいる確率が高そうな場所から調べる。Monstersを倒す。


source code

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

public class PrincessesAndMonsters {
private static final int DEAD = -1;
private static final int LEFT_THE_DUNGEON = -2;

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

char[] dirs = "NEWS ".toCharArray();
int[] dr = new int[] { -1, 0, 0, 1, 0, };
int[] dc = new int[] { 0, 1, -1, 0, 0, };

char[] entrancesChar = "0123".toCharArray();
int[] entranceRs;
int[] entranceCs;

private int S;
private Point[] princesses;
private Point[] monsters;
private Point[] knights;
private int K;
private double meanR;
private double meanC;
private int nearestEntrance;
private int[] phases;
private static final int MOVE_TO_MEAN = 0;
private static final int MOVE_TO_PRINCESSES = 1;
private static final int MOVE_TO_MEAN2 = 2;
private static final int MOVE_TO_ENTRANCE = 3;
private static final int MOVE_TO_MONSTERS = 4;
private static final int MOVE_TO_MEAN_IN_MOVE_TO_PRINCESSES = 5;

private int numKnightsPhaseMOVE_TO_PRINCESSES;

private double[][] princessProbability;
private double[][] monsterProbability;
private double[][] princessProbability100;
private double[][] monsterProbability100;

public String initialize(int S, int[] princesses, int[] monsters, int K) {
this.S = S;

this.princesses = new Point[princesses.length / 2];
for (int i = 0; i < this.princesses.length; i++) {
this.princesses[i] = new Point(princesses[2 * i + 0], princesses[2 * i + 1]);
}

this.monsters = new Point[monsters.length / 2];
for (int i = 0; i < this.monsters.length; i++) {
this.monsters[i] = new Point(monsters[2 * i + 0], monsters[2 * i + 1]);
}

this.K = K;

Utils.debug("S", S, "P", this.princesses.length, "M", this.monsters.length, "K", K);

entranceRs = new int[] { 0, 0, S - 1, S - 1, };
entranceCs = new int[] { 0, S - 1, S - 1, 0, };

double sumR = 0;
double sumC = 0;
for (int i = 0; i < this.princesses.length; i++) {
sumR += this.princesses[i].r;
sumC += this.princesses[i].c;
}

meanR = (int) (0.5 + sumR / this.princesses.length);
meanC = (int) (0.5 + sumC / this.princesses.length);

nearestEntrance = 0;
for (int i = 0; i < entranceRs.length; i++) {
if (Math.abs(meanR - entranceRs[i]) + Math.abs(meanC - entranceCs[i]) < Math.abs(meanR - entranceRs[nearestEntrance]) + Math.abs(meanC - entranceCs[nearestEntrance])) {
nearestEntrance = i;
}
}
Utils.debug("nearestEntrance", nearestEntrance);

this.knights = new Point[K];
for (int i = 0; i < this.knights.length; i++) {
this.knights[i] = new Point(entranceRs[nearestEntrance], entranceCs[nearestEntrance]);
}
this.phases = new int[K];
for (int i = 0; i < K; i++) {
this.phases[i] = MOVE_TO_MEAN;
}

princessProbability = new double[S][S];
princessProbability100 = new double[S][S];
for (int i = 0; i < this.princesses.length; i++) {
princessProbability[this.princesses[i].r][this.princesses[i].c] += 1;
princessProbability100[this.princesses[i].r][this.princesses[i].c] += 1;
}
monsterProbability = new double[S][S];
monsterProbability100 = new double[S][S];
for (int i = 0; i < this.monsters.length; i++) {
monsterProbability[this.monsters[i].r][this.monsters[i].c] += 1;
monsterProbability100[this.monsters[i].r][this.monsters[i].c] += 1;
}
next = new double[S][S];

calculateProbabilityTurn100();

numKnightsNextTurn = new int[S][S];

char[] c = new char[K];
for (int i = 0; i < K; i++) {
c[i] = entrancesChar[nearestEntrance];
}
return new String(c);
}

private int turn = 0;
private int previousP;
private int previousM;
private int previousK;

private char directionPhase_MOVE_TO_MONSTERS = 'S';

public String move(int[] status, int P, int M, int timeLeft) {
print(status, P, M);

char[] c = new char[K];
Arrays.fill(c, dirs[4]);
for (int k = 0; k < K; k++) {
if (status[k] == DEAD) {
continue;
}
if (status[k] == LEFT_THE_DUNGEON) {
continue;
}

if (phases[k] == MOVE_TO_MEAN || phases[k] == MOVE_TO_MEAN2 || phases[k] == MOVE_TO_MEAN_IN_MOVE_TO_PRINCESSES) {
moveToMeanPrincess(c, k);
continue;
}
if (phases[k] == MOVE_TO_ENTRANCE) {
moveToEntrance(c, k);
continue;
}
if (phases[k] == MOVE_TO_PRINCESSES) {
moveToBestScore(c, k);
continue;
}
if (phases[k] == MOVE_TO_MONSTERS) {
moveToMonster(c, k);
continue;
}
}

updatePhases(status, P, M);

updateProbability();

return new String(c);
}

private void moveToRandom(char[] c, int k) {
int direction = (int) (dr.length * rng.nextDouble());
c[k] = dirs[direction];
updateKnightPosition(k, direction);
}

private boolean isInside(int r, int c) {
return r >= 0 && c >= 0 && r < S && c < S;
}

private boolean isExit(int r, int c) {
return (r == 0 || r == S - 1) && (c == 0 || c == S - 1);
}

private double[][] next;

private void updateProbability() {
{
for (int r = 0; r < S; r++) {
Arrays.fill(next[r], 0);
}
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
if (princessProbability[r][c] < 1e-9) {
continue;
}
for (int d = 0; d < dr.length; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (!isInside(nr, nc)) {
nr = r;
nc = c;
}
if (isExit(nr, nc)) {
continue;
}
next[nr][nc] += 0.2 * princessProbability[r][c];
}
}
}
for (int r = 0; r < S; r++) {
System.arraycopy(next[r], 0, princessProbability[r], 0, S);
}
}
{
for (int r = 0; r < S; r++) {
Arrays.fill(next[r], 0);
}
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
if (monsterProbability[r][c] < 1e-9) {
continue;
}
for (int d = 0; d < dr.length; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (!isInside(nr, nc)) {
nr = r;
nc = c;
}
next[nr][nc] += 0.2 * monsterProbability[r][c];
}
}
}
for (int r = 0; r < S; r++) {
System.arraycopy(next[r], 0, monsterProbability[r], 0, S);
}
}
}

private void calculateProbabilityTurn100() {
for (int i = 0; i < 100; i++) {
for (int r = 0; r < S; r++) {
Arrays.fill(next[r], 0);
}
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
if (princessProbability100[r][c] < 1e-9) {
continue;
}
for (int d = 0; d < dr.length; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (!isInside(nr, nc)) {
nr = r;
nc = c;
}
if (isExit(nr, nc)) {
continue;
}
next[nr][nc] += 0.2 * princessProbability100[r][c];
}
}
}
for (int r = 0; r < S; r++) {
System.arraycopy(next[r], 0, princessProbability100[r], 0, S);
}
}
for (int i = 0; i < 100; i++) {
for (int r = 0; r < S; r++) {
Arrays.fill(next[r], 0);
}
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
if (monsterProbability100[r][c] < 1e-9) {
continue;
}
for (int d = 0; d < dr.length; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (!isInside(nr, nc)) {
nr = r;
nc = c;
}
next[nr][nc] += 0.2 * monsterProbability100[r][c];
}
}
}
for (int r = 0; r < S; r++) {
System.arraycopy(next[r], 0, monsterProbability100[r], 0, S);
}
}
}

private void updatePhases(int[] status, int P, int M) {
double maxDistanceFromMeanP = maxDistanceFromMeanP(knights, status);
int numKnights = numKnights(status);
int numPrincesses = numPrincesses(status);

for (int k = 0; k < K; k++) {
if (phases[k] == MOVE_TO_MEAN) {
if (distanceFromMeanPrincess(knights[k].r, knights[k].c) < 1e-5) {
phases[k] = MOVE_TO_PRINCESSES;
numKnightsPhaseMOVE_TO_PRINCESSES = numKnights;
continue;
}
if (princessProbability[knights[k].r][knights[k].c] > 0) {
phases[k] = MOVE_TO_PRINCESSES;
numKnightsPhaseMOVE_TO_PRINCESSES = numKnights;
continue;
}
}
if (phases[k] == MOVE_TO_PRINCESSES) {
if (P == numPrincesses) {
phases[k] = MOVE_TO_MEAN2;
continue;
}
if (numKnights < 5) {
phases[k] = MOVE_TO_MEAN2;
continue;
}
if (status[k] > 0) {
phases[k] = MOVE_TO_MEAN_IN_MOVE_TO_PRINCESSES;
continue;
}
}
if (phases[k] == MOVE_TO_MEAN_IN_MOVE_TO_PRINCESSES) {
if (P == numPrincesses) {
phases[k] = MOVE_TO_MEAN2;
continue;
}
if (numKnights < 5) {
phases[k] = MOVE_TO_MEAN2;
continue;
}
if (status[k] == 0) {
phases[k] = MOVE_TO_PRINCESSES;
continue;
}
}
if (phases[k] == MOVE_TO_MEAN2 && maxDistanceFromMeanP < 1e-5) {
phases[k] = MOVE_TO_MONSTERS;
continue;
}
if (phases[k] == MOVE_TO_MONSTERS) {
if (M == 0) {
phases[k] = MOVE_TO_ENTRANCE;
continue;
}
if (numKnights < 5) {
phases[k] = MOVE_TO_ENTRANCE;
continue;
}
if (turn >= S * S * S - 2 * S) {
phases[k] = MOVE_TO_ENTRANCE;
continue;
}
continue;
}
}
}

private void moveToMonster(char[] c, int k) {
if (knights[k].r == 1) {
directionPhase_MOVE_TO_MONSTERS = 'S';
}
if (knights[k].r == S - 2) {
directionPhase_MOVE_TO_MONSTERS = 'N';
}

if (knights[k].r % 2 == 0) {
if (knights[k].c < S - 1) {
int direction = getDirection('E');
c[k] = dirs[direction];
updateKnightPosition(k, direction);
} else {
int direction = getDirection(directionPhase_MOVE_TO_MONSTERS);
c[k] = dirs[direction];
updateKnightPosition(k, direction);
}
} else {
if (knights[k].c > 0) {
int direction = getDirection('W');
c[k] = dirs[direction];
updateKnightPosition(k, direction);
} else {
int direction = getDirection(directionPhase_MOVE_TO_MONSTERS);
c[k] = dirs[direction];
updateKnightPosition(k, direction);
}
}
}

private void moveToEntrance(char[] c, int k) {
int nearestDirection = 0;
double best = (int) 1e9;
for (int d = 0; d < dr.length; d++) {
int nr = knights[k].r + dr[d];
int nc = knights[k].c + dc[d];
if (!isInside(nr, nc)) {
continue;
}
if (distanceFromEntrance(nr, nc) < best) {
nearestDirection = d;
best = distanceFromEntrance(nr, nc);
}
}
c[k] = dirs[nearestDirection];
updateKnightPosition(k, nearestDirection);
}

private void moveToMeanPrincess(char[] c, int k) {
int nearestDirection = 0;
double best = (int) 1e9;
for (int d = 0; d < dr.length; d++) {
int nr = knights[k].r + dr[d];
int nc = knights[k].c + dc[d];
if (!isInside(nr, nc)) {
continue;
}
if (distanceFromMeanPrincess(nr, nc) < best) {
nearestDirection = d;
best = distanceFromMeanPrincess(nr, nc);
}
}
c[k] = dirs[nearestDirection];
updateKnightPosition(k, nearestDirection);
}

private int[][] numKnightsNextTurn;

private void moveToBestScore(char[] c, int k) {
if (k == 0) {
for (int r = 0; r < S; r++) {
Arrays.fill(numKnightsNextTurn[r], 0);
}
}
int bestDirection = -1;
double best = (int) -1e9;
for (int d = 0; d < dr.length; d++) {
int nr = knights[k].r + dr[d];
int nc = knights[k].c + dc[d];
if (!isInside(nr, nc)) {
continue;
}
double score = 0;
score += 100 * princessProbability[nr][nc];
score += -5 * monsterProbability[nr][nc];
if (score > best) {
bestDirection = d;
best = score;
}
}
c[k] = dirs[bestDirection];
updateKnightPosition(k, bestDirection);
numKnightsNextTurn[knights[k].r][knights[k].c]++;
princessProbability[knights[k].r][knights[k].c] = 0;
monsterProbability[knights[k].r][knights[k].c] *= 1.0 / (numKnightsNextTurn[knights[k].r][knights[k].c] + 1);
}

private void print(int[] status, int P, int M) {
if (P != previousP || M != previousM || numKnights(status) != previousK) {
Utils.debug(turn, "P", P, "M", M, "K", numKnights(status));
}
turn++;
previousP = P;
previousM = M;
previousK = numKnights(status);
}

private int getDirection(char c) {
for (int i = 0; i < dirs.length; i++) {
if (dirs[i] == c) {
return i;
}
}
return 4;
}

private void updateKnightPosition(int k, int direction) {
knights[k].r += dr[direction];
knights[k].c += dc[direction];
knights[k].r = Math.max(0, Math.min(S - 1, knights[k].r));
knights[k].c = Math.max(0, Math.min(S - 1, knights[k].c));
}

private double maxDistanceFromMeanP(Point[] knights, int[] status) {
double max = 0;
for (int i = 0; i < knights.length; i++) {
if (status[i] >= 0) {
max = Math.max(max, distanceFromMeanPrincess(knights[i].r, knights[i].c));
}
}
return max;
}

private int numKnights(int[] status) {
int numKnights = 0;
for (int i = 0; i < K; i++) {
if (status[i] >= 0) {
numKnights++;
}
}
return numKnights;
}

private int numPrincesses(int[] status) {
int numPrincesses = 0;
for (int i = 0; i < K; i++) {
if (status[i] > 0) {
numPrincesses += status[i];
}
}
return numPrincesses;
}

private int distanceFromEntrance(int nr, int nc) {
return Math.abs(entranceRs[nearestEntrance] - nr) + Math.abs(entranceCs[nearestEntrance] - nc);
}

private double distanceFromMeanPrincess(int nr, int nc) {
double dr = meanR - nr;
double dc = meanC - nc;
return Math.sqrt(dr * dr + dc * dc);
}

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

PrincessesAndMonsters pam = new PrincessesAndMonsters();

int S = Integer.parseInt(br.readLine());
int P = Integer.parseInt(br.readLine());
int[] princesses = new int[P];
for (int i = 0; i < P; ++i) {
princesses[i] = Integer.parseInt(br.readLine());
}
int M = Integer.parseInt(br.readLine());
int[] monsters = new int[M];
for (int i = 0; i < M; ++i) {
monsters[i] = Integer.parseInt(br.readLine());
}
int K = Integer.parseInt(br.readLine());

String retInit = pam.initialize(S, princesses, monsters, K);
System.out.println(retInit);
System.out.flush();

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

int nP = Integer.parseInt(br.readLine());
int nM = Integer.parseInt(br.readLine());
int timeLeft = Integer.parseInt(br.readLine());

String ret = pam.move(status, nP, nM, timeLeft);
System.out.println(ret);
System.out.flush();
}
} catch (Exception e) {
e.printStackTrace();
}
}
}

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

}

class Point {
public Point(int r, int c) {
super();
this.r = r;
this.c = c;
}

int r;
int c;
}



このページのトップヘ