AtCoderの問題を解いてみます。今回は初心者向けの問題のAtCoder Beginners Selectionの7回目です。
問題
ABC086C – Traveling
https://atcoder.jp/contests/abs/tasks/arc089_a
問題概要
二次元平面上を動くシカのAtCoDeerくんについての問題です。
AtCoDeerくんは時刻 t に 点(x,y)にいる場合、 時刻t+1には 点(x+1,y),(x−1,y),(x,y+1),(x,y−1)のいずれかに移動します。つまり、時刻が1進むごとに1だけx方向かy方向に進むことができます。
AtCoDeerくんは点(0,0)をスタートして二次元平面上を旅行します。
AtCoDeerくんの旅行プランとして、時刻tの時に(x,y)にいるという情報がN個入力されるので、その様な旅行が可能かを判定します。（整数Nも最初に入力されます。）
回答
言語
Java8 (OpenJDK 1.8.0)
コード（初期作成）
最初に作成したコードが以下になります。
public class Main {
public static void main(String... args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
pw.println(check(br));
pw.flush();
}
static String check(BufferedReader br) throws Exception {
int n = Integer.parseInt(br.readLine());
Point before = new Point(0, 0, 0);
boolean able = true;
for (int i = 0; i < n; i++) {
Point next = new Point(br.readLine());
if (before.isAbleWorkTo(next)) {
before = next;
} else {
able = false;
break;
}
}
return able ? "Yes" : "No";
}
private static class Point {
int t, x, y;
Point(int t, int x, int y) {
this.t = t;
this.x = x;
this.y = y;
}
Point(String str) {
String[] txy = str.split(" ");
this.t = Integer.parseInt(txy[0]);
this.x = Integer.parseInt(txy[1]);
this.y = Integer.parseInt(txy[2]);
}
boolean isAbleWorkTo(Point other) {
int planeDistance = abs(other.x - x) + abs(other.y - y);
int timeDistance = other.t - t;
if (planeDistance > timeDistance) {
return false;
}
return (timeDistance - planeDistance) % 2 == 0;
}
}
private static int abs(int a) {
return (a < 0) ? -a : a;
}
}解説
以下がメインのロジックです。詳細は後述しますが、独自クラスPointを作成し、それを使って処理する様になっています。
static String check(BufferedReader br) throws Exception {
int n = Integer.parseInt(br.readLine());
Point before = new Point(0, 0, 0);
boolean able = true;
for (int i = 0; i < n; i++) {
Point next = new Point(br.readLine());
if (before.isAbleWorkTo(next)) {
before = next;
} else {
able = false;
break;
}
}
return able ? "Yes" : "No";
}時刻tと座標(x,y)が標準入力から入力されるので、それを都度読み込みPointクラスのインスタンスを生成しています。それを一つ前に作成したPointから移動できるかを判定し、移動できない場合はそこでループを終了し、Noを返しています。ループを最後まで処理できた（最後まで移動ができた）場合はYesを返しています。
以下は独自クラスのPointクラスです。時刻tと座標(x,y)を保持したクラスです。
private static class Point {
int t, x, y;
Point(int t, int x, int y) {
this.t = t;
this.x = x;
this.y = y;
}
Point(String str) {
String[] txy = str.split(" ");
this.t = Integer.parseInt(txy[0]);
this.x = Integer.parseInt(txy[1]);
this.y = Integer.parseInt(txy[2]);
}
boolean isAbleWorkTo(Point other) {
int planeDistance = abs(other.x - x) + abs(other.y - y);
int timeDistance = other.t - t;
if (planeDistance > timeDistance) {
return false;
}
return (timeDistance - planeDistance) % 2 == 0;
}
}メインメソッドは入力された別のインスタンスに対して、移動ができるかを判定するメソッドです。（処理的には影響ないですがメソッド名が変なのにこれを書きながら気づきました。workじゃなくてwalkのつもりでした。）
処理的には平面上の距離と時間上の距離をそれぞれ算出し、それをベースに判定を行なっています。なお、平面上の距離はユークリッド距離ではなくマンハッタン距離になっています。
まず、平面上の距離が時間上の距離より大きい場合は、その座標に時間内に到達ができないので、falseです。また、平面上の距離の方が小さい場合でも、最終的な時刻にその点にいるためには行って戻ってという動きが必要になります。つまり、時間上の距離と平面上の距離の差が2の倍数である必要があります。2の倍数の時trueであり、2の倍数でない場合はfalseです。
結果
今回の結果は以下のようになりました。
- 実行時間：269 ms
- メモリ：43,580 KB
初期作成は性能はあまり考えずに作成しているとは言え、少々しょっぱい結果になったかなと思います。
コード（修正版）
最初のコードの作成後、色々と試して見ました。その中で、最も性能が良い結果になったのが以下のコードです。
public class Main {
public static void main(String... args) throws Exception {
PrintWriter pw = new PrintWriter(System.out);
try (InnerReader ir = new InnerReader(System.in)) {
pw.println(new Main().execute(ir));
pw.flush();
}
}
String execute(InnerReader reader) throws Exception {
int n = reader.readInt();
// before
int b_t = 0;
int b_x = 0;
int b_y = 0;
boolean able = true;
for (int i = 0; i < n; i++) {
// next
int n_t = reader.readInt();
int n_x = reader.readInt();
int n_y = reader.readInt();
if (!isAbleWorkTo(b_t, b_x, b_y, n_t, n_x, n_y)) {
able = false;
break;
}
b_t = n_t;
b_x = n_x;
b_y = n_y;
}
return able ? "Yes" : "No";
}
private static boolean isAbleWorkTo(int b_t, int b_x, int b_y, int n_t, int n_x, int n_y) {
int planeDistance = abs(n_x - b_x) + abs(n_y - b_y);
int timeDistance = n_t - b_t;
if (planeDistance > timeDistance) {
return false;
}
return (timeDistance - planeDistance) % 2 == 0;
}
private static int abs(int a) {
return (a < 0) ? -a : a;
}
private static class InnerReader implements AutoCloseable {
private final InputStream in;
private static final byte CHAR_0 = 48;
private static final byte CHAR_9 = 48 + 9;
private static final char CHAR_SPACE = ' ';
private static final byte END = -1;
InnerReader(InputStream in) {
this.in = in;
}
private int readInt() throws Exception {
int i = 0;
int j;
while (true) {
j = in.read();
if (j == END || j == CHAR_SPACE) {
break;
}
if (CHAR_0 <= j && j <= CHAR_9) {
i = i * 10 + (j - CHAR_0);
} else {
break;
}
}
return i;
}
@Override
public void close() throws IOException {
this.in.close();
}
}
}大雑把にいうと、独自の読み込みクラスを作成し、それを使って入力を読み込みを行う様にしています。
なお、最初のコードで使ったPointクラスを廃止していますが、そこは性能的にはあまり影響はありませんでした。（Pointクラスのバージョンでも試しましたが、実行時間で2ms、メモリで1MB程度の性能差でした）
解説
メイン処理も変わっていますが、基本的な考え方、作りは最初のコードと同じなので省略します。
修正版のコードで大きく変更が加わっているのは以下の箇所です。
private static class InnerReader implements AutoCloseable {
private final InputStream in;
private static final byte CHAR_0 = 48;
private static final byte CHAR_9 = 48 + 9;
private static final char CHAR_SPACE = ' ';
private static final byte END = -1;
InnerReader(InputStream in) {
this.in = in;
}
private int readInt() throws Exception {
int i = 0;
int j;
while (true) {
j = in.read();
if (j == END || j == CHAR_SPACE) {
break;
}
if (CHAR_0 <= j && j <= CHAR_9) {
i = i * 10 + (j - CHAR_0);
} else {
break;
}
}
return i;
}
@Override
public void close() throws IOException {
this.in.close();
}
}以前にも同様に性能劣化の原因になりましたが、JavaのStringクラスのインスタンス生成はコストがかなり大きいです。今回のコードはBufferedReaderなどによるreadを止めて、独自のReaderクラスでreadする様にしています。
今回の問題は、問題の制約によって入力は整数のみです（文字列の読み込みはありません）。整数以外は区切り文字のスペースと改行のみです。そのため、整数前提で読み込む形になっていて、整数以外に到達したらそこで読み込みを終了する様になっています。
なお、条件的には
if (CHAR_0 <= j && j <= CHAR_9) {だけで十分なはずなので、その前の
if (j == END || j == CHAR_SPACE) {は不要だと思いますが、これを消すと遅くなったので残しています。
整数の読み込み部分については、単純に先頭から1文字ずつ読み込み、次の読み込みでは元の数字の桁をあげて（10をかけて）足すという処理を繰り返しています。
結果
今回の結果は以下のようになりました。
- 実行時間：105 ms
- メモリ：22,612 KB
最初に比べると結構性能UPしたのではないかと思います。
補足
この記事を書いている途中で
- Java8 (OpenJDK 1.8.0)
が対象言語から消えて、近いものだと
- Java (OpenJDK 1.8.0)
になっていました（括弧の中身は同じですが、その前のJava8の部分がJavaになっている）。
気になったので試してみたところ、同じコード内容でも結果は以下の様に変わりました。
- 実行時間：89 ms
- メモリ：26,164 KB
実行時間は良くなり（早くなり）、メモリ消費は悪くなった（多くなった）みたいです。
作成物
今回の作成物は以下に置いています。
コメント