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