EvbCFfp1XB

problem and my answer.

August 2016

Ubuntu 15.10 の場合


Android Studio の実行
  • android-studio-ide-XXX-linux.zip をダウンロード
  • android-studio-ide-XXX-linux.zip を展開(android-studio と言うフォルダに展開される)
  • cd android-studio/bin
  • ./studio.sh

Android SDK のインストール
  • Android Studio での何らかの操作で ~/Android/ と言うフォルダができる
  • cd ~/Android/Sdk/tools/
  • ./android update sdk --no-ui


必要なライブラリのインストール

  • Android Studio のホームページに "sudo apt-get install lib32z1 lib32ncurses5 lib32bz2-1.0 lib32stdc++6" を実行しろとあったが、lib32bz2-1.0 はインストールできなかったし必要なかった
  • sudo apt-get install lib32z1 lib32ncurses5 lib32stdc++6


KVM のインストール(http://askubuntu.com/questions/564910/kvm-is-not-installed-on-this-machine-dev-kvm-is-missing)

  • sudo apt-get install qemu-kvm
  • Enable Virtualization Technology in BIOS
  • sudo kvm-ok


Android application Hello World を実行する

  • 例えば https://anharu.keiji.io/lesson1/step1/ に従う。




I improved my approach.

The average of this approach reaches 0.995. The ratio of perfect is greater than 75 percent.

  • I used multi-start local search. It restarts if the number of moves is greater than the max number of moves or the number of beam search is greater than 64 + the number of beam search of best score for each restart.
  • It sorts the states in beam search.
  • It used RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4 instead of HashSet<Long>. This doubled the number of beam search.



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.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.TimeZone;

public class RollingBalls {
private XorShift rng = new XorShift();
private Board board = new Board();

private TimeManager timeManager = new TimeManager();

private double bestScore = -1;

private String[] bestSolution;
private RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4 used2 = new RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4(16, 1 << 20);
private int countRestart;
private int bestCountBeamsearch;
private double bestScoreRestart;

public String[] restorePattern(String[] start, String[] target) {
Utils.printDate();

board.init(start, target);

solve();

bestSolution = Arrays.copyOf(bestSolution, Math.min(bestSolution.length, board.maxNumRolls()));

Utils.debug("time", timeManager.toString(), "bestSolution.length", bestSolution.length, "maxNumRolls", board.maxNumRolls(), "countBeamsearch", countBeamsearch, "countAdd", countAdd, "countAdd/countBeamsearch", countAdd / countBeamsearch);
Utils.debug("countRestart", countRestart);

return bestSolution;
}

private static final int[] maxBalls = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, };

private void solve() {
for (; timeManager.getSecond() < 9.5;) {

if (board.getScorePoint1() > 0.999) {
break;
}

IntArray targetsScore0 = getTargetsScore0();

int targetIndex = targetsScore0.values[(int) (targetsScore0.length * rng.nextDouble())];

Utils.shuffle(maxBalls, rng);
for (int numBalls : maxBalls) {
if (board.getTargetScore(targetIndex) > 0.999) {
break;
}
if (timeManager.getSecond() > 9.5) {
break;
}

int nearestSameColorBallIndex = getSameColorScore0BallsDistanceFromTargetAscending(targetIndex).get(0).second;
ArrayList<Pair<Double, Integer>> balls = getBallsDistanceFromBallAscending(nearestSameColorBallIndex);

numBalls = Math.min(numBalls, balls.size());

IntArray ballIndexes = new IntArray();
for (int i = 0; i < numBalls; i++) {
ballIndexes.add(balls.get(i).second);
}

int maxDepth = 20;
int maxBeamWidth = 250;
if (countBeamsearch == 0) {
Utils.debug("maxBeamWidth", maxBeamWidth);
}
countBeamsearch++;
ArrayList<State> moves = beamsearch(ballIndexes, maxDepth, maxBeamWidth, targetIndex);
if (moves == null) {
continue;
}
for (State state : moves) {
assert board.canMove(state.index, state.direction);
board.next(state.index, state.direction);
}
if (board.getScorePoint1() > bestScore && board.numMoves() < board.maxNumRolls()) {
bestScore = board.getScorePoint1();
bestSolution = board.getSolution();
}
if (board.getScorePoint1() > bestScoreRestart && board.numMoves() < board.maxNumRolls()) {
bestScoreRestart = board.getScorePoint1();
bestCountBeamsearch = countBeamsearch;
}

if (board.numMoves() > board.maxNumRolls()) {
break;
}
}

if (board.numMoves() > board.maxNumRolls() || countBeamsearch > bestCountBeamsearch + 64) {
for (; board.numMoves() > 0;) {
board.previous();
}
countRestart++;
Utils.debug("Restart", "countBeamsearch", countBeamsearch, "bestCountBeamsearch", bestCountBeamsearch);
bestScoreRestart = 0;
bestCountBeamsearch = countBeamsearch;
}
}

}

private int countBeamsearch = 0;
private int countAdd = 0;

private ArrayList<Pair<Double, Integer>> getBallsDistanceFromBallAscending(int ballIndex0) {
ArrayList<Pair<Double, Integer>> balls = new ArrayList<>();

int[] distanceFromBall = distanceFromBall(ballIndex0);

for (int ballIndex = 0; ballIndex < board.numBalls(); ballIndex++) {
ColoredPoint ball = board.balls.get(ballIndex);
int distance = distanceFromBall[ball.z];
balls.add(new Pair<Double, Integer>(1e-2 * rng.nextDouble() + distance, ballIndex));
}
Collections.sort(balls);
return balls;
}

private int[] distanceFromBall(int ballIndex0) {
ColoredPoint ball0 = board.balls.get(ballIndex0);
int[] distanceFromBall = new int[64 * 64];
Arrays.fill(distanceFromBall, (int) 1e9);

LinkedList<Data> queue = new LinkedList<>();
{
Data e = new Data(ball0.z, 0);
queue.add(e);
distanceFromBall[ball0.z] = 0;
}
for (; !queue.isEmpty();) {
Data poll = queue.poll();

int nextDistance = poll.distance + 1;

for (int direction = 0; direction < 4; direction++) {
int nextZ = board.getNextZ(poll.z, direction);

if (board.isTargetWall(nextZ)) {
continue;
}
if (nextDistance < distanceFromBall[nextZ]) {
Data e = new Data(nextZ, nextDistance);
queue.add(e);
distanceFromBall[nextZ] = nextDistance;
}
}
}
return distanceFromBall;
}

private ArrayList<Pair<Double, Integer>> getSameColorScore0BallsDistanceFromTargetAscending(int targetIndex) {
ArrayList<Pair<Double, Integer>> balls = new ArrayList<>();
int targetColor = board.getTargetColor(targetIndex);
for (int ballIndex = 0; ballIndex < board.numBalls(); ballIndex++) {
if (board.getBallColor(ballIndex) != targetColor) {
continue;
}
if (board.getBallScore(ballIndex) > 0.999) {
continue;
}
ColoredPoint ball = board.balls.get(ballIndex);
int distance = board.getDistanceFromTarget(targetIndex, ball.z);
balls.add(new Pair<Double, Integer>(1e-2 * rng.nextDouble() + distance, ballIndex));
}
Collections.sort(balls);
return balls;
}

private IntArray getTargetsScore0() {
IntArray res = new IntArray(board.numBalls());
for (int targetIndex = 0; targetIndex < board.numBalls(); targetIndex++) {
if (board.getTargetScore(targetIndex) > 0.999) {
continue;
}
res.add(targetIndex);
}
return res;
}

private Comparator<State> moveHistoryHashComparator = new Comparator<State>() {
@Override
public int compare(State o1, State o2) {
if (o1.moveHistoryHash < o2.moveHistoryHash) {
return -1;
}
if (o1.moveHistoryHash > o2.moveHistoryHash) {
return 1;
}
return 0;
}
};

private ArrayList<State> beamsearch(IntArray ballIndexes, int maxDepth, int maxBeamWidth, int targetIndex) {
ArrayList<State> currents = new ArrayList<>();
ArrayList<State> nexts = new ArrayList<>();
State best = null;

int currentNumMoves = board.numMoves();

used2.clear();

for (int i = 0; i < ballIndexes.length; i++) {
int ballIndex = ballIndexes.values[i];
ColoredPoint ball = board.balls.get(ballIndex);
int z = ball.z;
for (int direction = 0; direction < 4; direction++) {
if (!board.canMove(ballIndex, direction)) {
continue;
}

board.next(ballIndex, direction);

boolean add = used2.add(board.getHash());
if (add) {
double score = getSumScore(ballIndexes);
double distance = getSumMinDistance(ballIndexes, targetIndex);
distance += 1e-2 * rng.nextDouble();
State e = new State(null, ballIndex, z, direction, score, distance);
e.moveHistoryHash |= ballIndex & ((1 << 6) - 1);
e.moveHistoryHash = e.moveHistoryHash << 2;
e.moveHistoryHash |= direction;
currents.add(e);
countAdd++;
}
board.previous();
}
}

depthLoop: for (int depth = 0; depth < maxDepth; depth++) {
if (currents.size() == 0) {
break;
}
int beamWidth = Math.min(maxBeamWidth, currents.size());
CollectionsUtils.select(currents, 0, currents.size(), beamWidth);
CollectionsUtils.sort(currents, 0, beamWidth - 1, moveHistoryHashComparator);
for (int beam = 0; beam < beamWidth; beam++) {
State currentState = currents.get(beam);

if (best == null || currentState.compareTo(best) < 0) {
best = currentState;
}

board.set(reverse2(toList(currentState)), currentNumMoves);

assert getSumScore(ballIndexes) == currentState.score;
if (currentState.score > ballIndexes.length - 1e-9) {
break depthLoop;
}

for (int i = 0; i < ballIndexes.length; i++) {
int ballIndex = ballIndexes.values[i];
ColoredPoint ball = board.balls.get(ballIndex);
int z = ball.z;
for (int direction = 0; direction < 4; direction++) {
if (!board.canMove(ballIndex, direction)) {
continue;
}

int nextZ = board.simulateNext(ball, direction);

if (used2.add(board.nextHash(board.getHash(), z, nextZ, ball))) {

double nextScore = currentState.score;
if (!board.isTargetEmpty(z) && board.getTargetColorByZ(z) == ball.color) {
nextScore--;
}
if (!board.isTargetEmpty(nextZ) && board.getTargetColorByZ(nextZ) == ball.color) {
nextScore++;
}

double nextDistance = currentState.distance + board.getDistanceFromTarget(targetIndex, nextZ) - board.getDistanceFromTarget(targetIndex, z) + 1e-2 * rng.nextDouble();

State e = new State(currentState, ballIndex, z, direction, nextScore, nextDistance);
e.moveHistoryHash = currentState.moveHistoryHash << 6;
e.moveHistoryHash |= ballIndex & ((1 << 6) - 1);
e.moveHistoryHash = e.moveHistoryHash << 2;
e.moveHistoryHash |= direction;
nexts.add(e);
countAdd++;
}
}
}
}
{
ArrayList<State> swap = currents;
currents = nexts;
nexts = swap;
}
nexts.clear();
}

for (; board.numMoves() > currentNumMoves;) {
board.previous();
}

if (best == null) {
return null;
}

return reverse2(toList(best));

}

private double getSumMinDistance(IntArray ballIndexes, int targetIndex) {
double sum = 0;
for (int i = 0; i < ballIndexes.length; i++) {
sum += getDistance(ballIndexes.values[i], targetIndex);
}
return sum;
}

private int getDistance(int ballIndex, int targetIndex) {
return board.getDistanceFromTarget(targetIndex, board.balls.get(ballIndex).z);
}

private double getSumScore(IntArray ballIndexes) {
double sum = 0;
for (int i = 0; i < ballIndexes.length; i++) {
int ballIndex = ballIndexes.values[i];
sum += (board.getBallScore(ballIndex) > 0.999 ? 1 : 0);
}
return sum;
}

private ArrayList<State> reverse2(ArrayList<State> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
return list;
}

private ArrayList<State> toList(State state2) {
ArrayList<State> res = new ArrayList<>();
for (State current = state2; current != null; current = current.parent) {
res.add(current);
}
return res;
}

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

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

int H = Integer.parseInt(reader.readLine());
String[] start = new String[H];
for (int i = 0; i < H; i++) {
start[i] = reader.readLine();
}
int H2 = Integer.parseInt(reader.readLine());
String[] target = new String[H2];
for (int i = 0; i < H2; i++) {
target[i] = reader.readLine();
}

String[] ret = o.restorePattern(start, target);
System.out.println(ret.length);
for (int i = 0; i < ret.length; i++) {
System.out.println(ret[i]);
}
System.out.flush();

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

class Data {
int z;
int distance;

public Data(int z, int distance) {
super();
this.z = z;
this.distance = distance;
}
}

class Board {
private static final int WALL = 1 << 27;
private static final int EMPTY = 1 << 28;
private static final int[] DELTA = { -1, 64, 1, -64, };
private static final int SHIFT = 6;
private static final int MASK = (1 << SHIFT) - 1;
private static final int[] ballIndex = new int[64 * 64];
private static final long[][] hashes = new long[64 * 64][10];
private int[][] distanceFromTarget;
private static final int[] targetIndex = new int[64 * 64];
public List<ColoredPoint> balls = new ArrayList<>();
public List<ColoredPoint> targets = new ArrayList<>();
private int R;
private int C;
private long hash = 0;
private int countPoint1;
private IntArray moveHistory = new IntArray(32 * 64 * 64);

public void init(String[] start, String[] target) {
R = start.length;
C = start[0].length();

initBoard(start);
initTargetBoard(target);
initScore();
initHash();
initDistanceFromTarget();
}

public long getHash() {
return hash;
}

public int getDistanceFromTarget(int targetIndex, int z) {
return distanceFromTarget[targetIndex][z];
}

public long nextHash(long currentHash, int z, int nextZ, ColoredPoint ball) {
return currentHash ^ (hashes[z][ball.color] ^ hashes[nextZ][ball.color]);
}

public int getNextZ(int z, int direction) {
return z + Board.DELTA[direction];
}

public boolean isTargetEmpty(int z) {
return targetIndex[z] == Board.EMPTY;
}

public boolean isTargetWall(int z) {
return targetIndex[z] == Board.WALL;
}

public int getBallColor(int ballIndex) {
return balls.get(ballIndex).color;
}

public int getTargetColorByZ(int z) {
return getTargetColor(targetIndex[z]);
}

public int getTargetColor(int targetIndex) {
return targets.get(targetIndex).color;
}

public int numMoves() {
return moveHistory.length;
}

private void initDistanceFromTarget() {
distanceFromTarget = new int[numBalls()][64 * 64];

for (int targetIndex = 0; targetIndex < numBalls(); targetIndex++) {
ColoredPoint target = targets.get(targetIndex);
Arrays.fill(distanceFromTarget[targetIndex], (int) 1e9);

LinkedList<Data> queue = new LinkedList<>();
{
Data e = new Data(target.z, 0);
queue.add(e);
distanceFromTarget[targetIndex][target.z] = 0;
}
for (; !queue.isEmpty();) {
Data poll = queue.poll();

int nextDistance = poll.distance + 1;

for (int direction = 0; direction < 4; direction++) {
int nextZ = poll.z + DELTA[direction];

if (this.targetIndex[nextZ] == WALL) {
continue;
}
if (nextDistance < distanceFromTarget[targetIndex][nextZ]) {
Data e = new Data(nextZ, nextDistance);
queue.add(e);
distanceFromTarget[targetIndex][nextZ] = nextDistance;
}
}
}
}
}

public static final int getZ(int r, int c) {
return (r << Board.SHIFT) | c;
}

private void initHash() {
XorShift rng = new XorShift(System.nanoTime());
for (int z = 0; z < hashes.length; z++) {
for (int color = 0; color < 10; color++) {
hashes[z][color] = rng.nextLong();
}
}

hash = 0;
for (ColoredPoint ball : balls) {
hash ^= hashes[ball.z][ball.color];
}
}

public void set(ArrayList<State> list, int startIndex) {
int startIndexMinus1 = startIndex - 1;
for (int i = 0; i < list.size() && startIndex + i < moveHistory.length; i++) {
int state0 = moveHistory.values[startIndex + i];
int z = (state0 >>> 2) & ((1 << 12) - 1);
int direction = (state0 >>> 0) & ((1 << 2) - 1);

State state = list.get(i);
if (state.z == z && state.direction == direction) {
startIndexMinus1 = startIndex + i;
continue;
}
break;
}
for (; numMoves() > startIndexMinus1 + 1;) {
previous();
}
for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
State state2 = list.get(i);
next(state2.index, state2.direction);
}
}

public int numBalls() {
return balls.size();
}

public int maxNumRolls() {
return 20 * balls.size();
}

public String[] getSolution() {
ArrayList<String> res = new ArrayList<>();
for (int i = 0; i < numMoves(); i++) {
int state = moveHistory.values[i];
int z = (state >>> 2) & ((1 << 12) - 1);
int r = getR(z);
int c = getC(z);
int d = (state >>> 0) & ((1 << 2) - 1);
res.add("" + (r - 1) + " " + (c - 1) + " " + d);
}
return (String[]) res.toArray(new String[res.size()]);
}

public static final int getC(int z) {
return z & Board.MASK;
}

public static final int getR(int z) {
return z >>> Board.SHIFT;
}

public double getBallScore(int ballIndex) {
ColoredPoint ball = balls.get(ballIndex);
int index = targetIndex[ball.z];
return index == EMPTY ? 0 : getTargetColor(index) == ball.color ? 1 : 0.5;
}

public double getTargetScore(int targetIndex) {
ColoredPoint target = targets.get(targetIndex);
int index = ballIndex[target.z];
return index == EMPTY ? 0 : getBallColor(index) == target.color ? 1 : 0.5;
}

private void initScore() {
countPoint1 = 0;
for (int i = 0; i < balls.size(); i++) {
double score = getBallScore(i);
if (score > 0.999) {
countPoint1++;
}
}
}

public double getScorePoint1() {
return ((double) countPoint1) / balls.size();
}

public boolean canMove(int ballIndex, int direction) {
return Board.ballIndex[balls.get(ballIndex).z + DELTA[direction]] == EMPTY;
}

public int simulateNext(int ballIndex, int direction) {
return simulateNext(balls.get(ballIndex), direction);
}

public int simulateNext(ColoredPoint ball, int direction) {
int z = ball.z;

do {
z += DELTA[direction];
} while (Board.ballIndex[z] == EMPTY);
z -= DELTA[direction];

return z;
}

public void next(int ballIndex, int direction) {
ColoredPoint ball = balls.get(ballIndex);
moveHistory.add((ballIndex << 14) | (ball.z << 2) | (direction));

int z = ball.z;
ball.z = simulateNext(ball, direction);

this.ballIndex[z] = EMPTY;
this.ballIndex[ball.z] = ballIndex;

hash = nextHash(hash, z, ball.z, ball);

if (targetIndex[z] != EMPTY && getTargetColor(targetIndex[z]) == ball.color) {
countPoint1--;
}
if (targetIndex[ball.z] != EMPTY && getTargetColor(targetIndex[ball.z]) == ball.color) {
countPoint1++;
}
}

public void previous() {
int lastMove = moveHistory.remove();
int ballIndex = (lastMove >>> 14);
int z = (lastMove >>> 2) & ((1 << 12) - 1);

ColoredPoint ball = balls.get(ballIndex);
assert this.ballIndex[ball.z] == ballIndex;
hash = nextHash(hash, ball.z, z, ball);

this.ballIndex[ball.z] = EMPTY;
this.ballIndex[z] = ballIndex;
if (targetIndex[ball.z] != EMPTY && getTargetColor(targetIndex[ball.z]) == ball.color) {
countPoint1--;
}
if (targetIndex[z] != EMPTY && getTargetColor(targetIndex[z]) == ball.color) {
countPoint1++;
}

ball.z = z;

}

private void initBoard(String[] start) {
for (int z = 0; z < ballIndex.length; z++) {
ballIndex[z] = WALL;
}

int index = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
char charAt = start[r].charAt(c);
int z = getZ(r + 1, c + 1);
if (charAt == '#') {
ballIndex[z] = WALL;
continue;
}
if (charAt == '.') {
ballIndex[z] = EMPTY;
continue;
}
ballIndex[z] = index++;
balls.add(new ColoredPoint(z, charAt - '0'));
}
}
}

private void initTargetBoard(String[] target) {
for (int z = 0; z < targetIndex.length; z++) {
targetIndex[z] = WALL;
}

int index = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
char charAt = target[r].charAt(c);
int z = getZ(r + 1, c + 1);
if (charAt == '#') {
targetIndex[z] = WALL;
continue;
}
if (charAt == '.') {
targetIndex[z] = EMPTY;
continue;
}
targetIndex[z] = index++;
targets.add(new ColoredPoint(z, charAt - '0'));
}
}
}
}

class Point {
int z;

public Point(int z) {
this.z = z;
}
}

class ColoredPoint extends Point {
int color;

public ColoredPoint(int z, int color) {
super(z);
this.color = color;
}
}

final class Utils {
private Utils() {
}

public static final double earthDistance(double latitude0, double longitude0, double latitude1, double longitude1, double earthRadius) {
double deltaLon = Math.abs(longitude0 - longitude1);
if (deltaLon > 180) {
deltaLon = 360 - deltaLon;
}
deltaLon = Math.toRadians(deltaLon);
longitude0 = Math.toRadians(longitude0);
longitude1 = Math.toRadians(longitude1);
latitude0 = Math.toRadians(latitude0);
latitude1 = Math.toRadians(latitude1);
double e = Math.cos(latitude0) * Math.sin(deltaLon);
double e2 = Math.cos(latitude1) * Math.sin(latitude0) - Math.sin(latitude1) * Math.cos(latitude0) * Math.cos(deltaLon);
return earthRadius * Math.atan2(Math.sqrt(e * e + e2 * e2), Math.sin(latitude1) * Math.sin(latitude0) + Math.cos(latitude1) * Math.cos(latitude0) * Math.cos(deltaLon));
}

public static final double transitTime(double latitude0, double longitude0, double latitude1, double longitude1, double earthRadius) {
double highSlope = 60.0 / 122.0;
double lowSlope = 53.3 / 120.0;
double meanSlope = 60.0 * (highSlope + lowSlope) / 2.0;
double earthCircumference = 2.0 * Math.PI * earthRadius;
double earthDistance = earthDistance(latitude0, longitude0, latitude1, longitude1, earthRadius);
return (earthDistance / earthCircumference) * 360.0 * meanSlope;
}

public static final double euclideanDistance(double r1, double c1, double r2, double c2) {
double deltaR = r2 - r1;
double deltaC = c2 - c1;
return Math.sqrt(deltaR * deltaR + deltaC * deltaC);
}

public static final double manhattanDistance(double r1, double c1, double r2, double c2) {
double deltaR = r2 - r1;
double deltaC = c2 - c1;
return Math.abs(deltaR) + Math.abs(deltaC);
}

public static final int manhattanDistance(int r1, int c1, int r2, int c2) {
int deltaR = r2 - r1;
int deltaC = c2 - c1;
return Math.abs(deltaR) + Math.abs(deltaC);
}

public static final double calculateRandomForestMemory(double numTrees, double maxDepth, double nodeSize) {
return numTrees * (1 << (int) maxDepth) * nodeSize / (8e6);
}

public static final double calculateRandomForestMemory2(double numTrees, int numSamples, double nodeSize) {
return numTrees * (2 * numSamples) * nodeSize / (8e6);
}

public static final double calculateRandomForestFeatureMemory(double numBits, double numRows, double numColumns) {
return calculateMemory(numBits, numRows, numColumns);
}

public static final double calculateMemory(double numBits, double numRows, double numColumns) {
double bits = numBits * numRows * numColumns;
double bytes = bits / 8;
double MB = bytes / 1e6;
return MB;
}

public static final String format(double second) {
return TimeManager.toString(second);
}

public static final void printDate() {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;

long end = Constants.endTime.getTimeInMillis();
long current = Constants.currentTime.getTimeInMillis();

long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);

int year = Constants.currentTime.get(Calendar.YEAR);
int month = 1 + Constants.currentTime.get(Calendar.MONTH);
int day = Constants.currentTime.get(Calendar.DAY_OF_MONTH);
int hour = Constants.currentTime.get(Calendar.HOUR_OF_DAY);
int minute = Constants.currentTime.get(Calendar.MINUTE);
int second = Constants.currentTime.get(Calendar.SECOND);

debug(String.format("%02d/%02d/%02d %02d:%02d:%02d Time Left %d Hrs %d Mins", year, month, day, hour, minute, second, numHours, numMinutes));
}

public static final String toStringDate() {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;

long end = Constants.endTime.getTimeInMillis();
long current = Constants.currentTime.getTimeInMillis();

long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);

int year = Constants.currentTime.get(Calendar.YEAR);
int month = 1 + Constants.currentTime.get(Calendar.MONTH);
int day = Constants.currentTime.get(Calendar.DAY_OF_MONTH);
int hour = Constants.currentTime.get(Calendar.HOUR_OF_DAY);
int minute = Constants.currentTime.get(Calendar.MINUTE);
int second = Constants.currentTime.get(Calendar.SECOND);

return String.format("%02d/%02d/%02d %02d:%02d:%02d Time Left %d Hrs %d Mins", year, month, day, hour, minute, second, numHours, numMinutes);
}

public static final void debug(Object... o) {
System.err.println(toString(o));
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

public static final void assertEquals(String message, double expected, double actual, double delta) {
if (Math.abs(expected - actual) > delta) {
throw new AssertionError(message);
}
}

public static final void assertEquals(String message, int expected, int actual) {
if (expected != actual) {
throw new AssertionError(message);
}
}

public static final <T extends Comparable<T>> int partition(ArrayList<T> a, int l, int r) {
int i = l - 1, j = r;
T v = a.get(r);
for (;;) {
while (a.get(++i).compareTo(v) < 0)
;
while (v.compareTo(a.get(--j)) < 0)
if (j == l)
break;
if (i >= j)
break;
swap(a, i, j);
}
swap(a, i, r);
return i;
}

public static final <T extends Comparable<T>> int partition3(ArrayList<T> 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;

T v = a.get(r1);
int i = l - 1;
int j = r1;
for (;;) {
for (; a.get(++i).compareTo(v) < 0;) {
}
for (; a.get(--j).compareTo(v) > 0;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r1);
return i;
}

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

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 <T extends Comparable<T>> void sort3(ArrayList<T> a, int i, int j, int k) {
if (a.get(i).compareTo(a.get(j)) > 0) {
swap(a, i, j);
}
if (a.get(i).compareTo(a.get(k)) > 0) {
swap(a, i, k);
}
if (a.get(j).compareTo(a.get(k)) > 0) {
swap(a, j, k);
}
}

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

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 <T> void swap(ArrayList<T> a, int i, int j) {
T swap = a.set(i, a.get(j));
a.set(j, swap);
}

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 swapXor(int[] a, int i, int j) {
if (i == j) {
return;
}
a[i] = a[i] ^ a[j];
a[j] = a[i] ^ a[j];
a[i] = a[i] ^ a[j];
}

public static final <T extends Comparable<T>> void select(ArrayList<T> a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

private static final <T extends Comparable<T>> void select0(ArrayList<T> a, int l, int r, int k) {
while (l < r) {
int i = partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

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

private static final <T> void select0(ArrayList<T> a, int l, int r, int k, Comparator<T> comparator) {
while (l < r) {
int i = 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);
}

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

public static final <T> void shuffle(ArrayList<T> list, XorShift rng) {
for (int i = list.size() - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
swap(list, 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());
swap(a, i, j);
}
}

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

}

final class Constants {
public static final boolean TIMER = !true;
public static final boolean LOCAL = true;
public static final boolean DEBUG = true;
public static final boolean ASSERTION = true;

private static final String id = "GMT-4:00";
public static final Calendar currentTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
}

public static final Calendar startTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
startTime.set(2015, 12 - 1, 14, 13, 0, 0);
}

public static final Calendar endTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
endTime.set(2015, 12 - 1, 28, 13, 0, 0);
}

private Constants() {
}
}

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

}

class TimeManager {
private long start;
private int count;

public TimeManager() {
init();
}

public int getCount() {
return count;
}

public double getSecond() {
count++;
return (System.currentTimeMillis() - start) * 1e-3;
}

public long getTime() {
count++;
return System.currentTimeMillis() - start;
}

public void init() {
init(System.currentTimeMillis());
}

public void init(long start) {
this.start = start;
count = 0;
}

public String toString() {
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 static final double toDouble = 1.0 / 2147483648.0;
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift() {
x = (int) System.nanoTime();
}

public XorShift(long l) {
x = (int) l;
}

public double nextDouble() {
return (nextInt() & Integer.MAX_VALUE) * toDouble;
}

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 int nextInt(int n) {
return (int) (n * nextDouble());
}

public long nextLong() {
long a = nextInt();
long b = nextInt();
return (a << 32) ^ b;
}

}

class State implements Comparable<State> {
State parent;
public int index;
public int z;
public int direction;
public double score;
public double distance;
public long moveHistoryHash;

public State(State parent, int index, int z, int direction, double score, double distance) {
super();
this.parent = parent;
this.index = index;
this.z = z;
this.direction = direction;
this.score = score;
this.distance = distance;
}

@Override
public int compareTo(State o) {
if (score > o.score) {
return -1;
}
if (score < o.score) {
return 1;
}
if (distance < o.distance) {
return -1;
}
if (distance > o.distance) {
return 1;
}
return 0;
}

}

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 RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4 {
private long mask;
private long[] used;
private IntArray indexes;
private long mask2 = ((1L << 16) - 1L) << 48;

public RestrictedHashSetLongHasFalseNegativeAndFalsePositive16x4(int numBits, int capacity) {
mask = (1L << numBits) - 1L;
used = new long[1 << numBits];
indexes = new IntArray(capacity);
}

public boolean add(long hash) {
int index = (int) (hash & mask);
long value = hash & mask2;

if ((used[index] & mask2) == value) {
return false;
}
if (((used[index] << 16) & mask2) == value) {
return false;
}
if (((used[index] << 32) & mask2) == value) {
return false;
}
if (((used[index] << 48) & mask2) == value) {
return false;
}

used[index] = (used[index] >>> 16) | value;
indexes.add(index);

return true;
}

public void clear() {
for (int i = 0; i < indexes.length; i++) {
used[indexes.values[i]] = 0;
}
indexes.clear();
}
}

class CollectionsUtils {
private CollectionsUtils() {
}

public static final <T> void shuffle(ArrayList<T> list, Random rng) {
for (int i = list.size() - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
CollectionsUtils.swap(list, i, j);
}
}

public static final <T> void shuffle(ArrayList<T> list, XorShift rng) {
for (int i = list.size() - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
CollectionsUtils.swap(list, i, j);
}
}

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

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

public static final <T extends Comparable<T>> void select0(ArrayList<T> a, int l, int r, int k) {
while (l < r) {
int i = CollectionsUtils.partition3(a, l, r);
if (i >= k)
r = i - 1;
if (i <= k)
l = i + 1;
}
}

public static final <T extends Comparable<T>> void select(ArrayList<T> a, int startInclusive, int endExclusive, int k) {
select0(a, startInclusive, endExclusive - 1, k);
}

public static final <T> void swap(ArrayList<T> a, int i, int j) {
T swap = a.set(i, a.get(j));
a.set(j, swap);
}

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

public static final <T extends Comparable<T>> void sort3(ArrayList<T> a, int i, int j, int k) {
if (a.get(i).compareTo(a.get(j)) > 0) {
swap(a, i, j);
}
if (a.get(i).compareTo(a.get(k)) > 0) {
swap(a, i, k);
}
if (a.get(j).compareTo(a.get(k)) > 0) {
swap(a, j, k);
}
}

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

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

public static final <T extends Comparable<T>> int partition(ArrayList<T> a, int l, int r) {
int i = l - 1, j = r;
T v = a.get(r);
for (;;) {
while (a.get(++i).compareTo(v) < 0)
;
while (v.compareTo(a.get(--j)) < 0)
if (j == l)
break;
if (i >= j)
break;
swap(a, i, j);
}
swap(a, i, r);
return i;
}

public static final <T> void sort(ArrayList<T> a, int lInclusive, int rInclusive, Comparator<T> comparator) {
if (lInclusive >= rInclusive) {
return;
}
int k = partition3(a, lInclusive, rInclusive, comparator);
sort(a, lInclusive, k - 1, comparator);
sort(a, k + 1, rInclusive, comparator);
}

public <T> ArrayList<T> reverse(ArrayList<T> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
return list;
}

public <T> ArrayList<T> newReverse(ArrayList<T> list) {
ArrayList<T> res = new ArrayList<>();
for (int i = list.size() - 1; i >= 0; i--) {
res.add(list.get(i));
}
return res;
}

}



このページのトップヘ