Overall Editorial by cirno3153
このユーザー解説はJava/Kotlinにおける実装例を紹介するものとなっています。
A問題 - Growth Record
このように変数が幾つも出てくる問題では、図を書いてみることが有効です。 例えば私の場合、格子状に線が入ったホワイトボードと8色のホワイトボードマーカーを常に用意しており、これに図を書いて考察することが多いです。
さて、実際に図を書いてみると以下のような形になります。
後は、この図から分かる式、つまり \(T - D \max(0, X - M)\) を実装しましょう。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt(), M = sc.nextInt(), X = sc.nextInt(), T = sc.nextInt(), D = sc.nextInt();
out.println(T - D * Math.max(0, X - M));
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt();
val M = sc.nextInt();
val X = sc.nextInt();
val T = sc.nextInt();
val D = sc.nextInt();
println(T - D * Math.max(0, X - M))
}
}
B問題 - Counterclockwise Rotation
このように点を回転させる問題は高校数学でも頻出であり、解き方は何通りかあります。
ただ、いずれも途中で三角関数を経由することと、JavaやKotlinの世界で三角関数の引数は弧度(ラジアン)で表すことから、いったんまずは与えられた \(d\) を弧度に変換しておきます。 度が \(d\) の時、弧度は \(\frac{d \pi}{180}\) で表すことができます。 以降、 \(d\) は弧度で表されているものとします。
方針1: 極座標変換を行う
極座標とは、原点からの距離 \(r\) 及び角度 \(\theta\) を用いて座標を表す方式です。これとは対照的に、 \(x\) 及び \(y\) 座標を用いて表す形式は直交座標と呼ばれます。
この座標は双方向に変換できます。
直交座標 \((x, y)\) を極座標で表すと \((\sqrt{x^2 + y^2}, \mathrm{atan2}(y, x))\) となります。
逆に、極座標 \((r, \theta)\) を直交座標で表すと \((r \cos \theta, r \sin \theta)\) となります。
極座標では、原点中心に回転する操作は簡単に行えます。角度が \(\theta\) で指定されているので、単に \(\theta\) に回す角度 \(d\) を足すだけです。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int a = sc.nextInt(), b = sc.nextInt(), d = sc.nextInt();
double rad = d * Math.PI / 180; // 弧度に変換
double r = Math.sqrt(a * a + b * b), theta = Math.atan2(b, a); // 極座標変換
theta += rad;
double x = r * Math.cos(theta), y = r * Math.sin(theta); // 直交座標変換
out.printf("%.06f %.06f\n", x, y);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val a = sc.nextDouble()
val b = sc.nextDouble()
val d = sc.nextDouble()
val rad = d * Math.PI / 180 // 弧度に変換
val r = Math.sqrt(a * a + b * b) // 原点からの距離
val theta = Math.atan2(b, a) + rad // 原点からの角度
val x = r * Math.cos(theta)
val y = r * Math.sin(theta)
println("%.06f %.06f".format(x, y))
}
}
方針2: 複素数平面で解く
複素数平面において、点を原点から \(d\) 回転させるには、単位円上にある原点から角度 \(d\) の点と掛け算をすれば良いです。 このような複素数は \(\cos d + i \sin d\) なので、これを掛ければ良いです。
Java/Kotlinに複素数クラスは存在しないので、計算部分だけ予め求めてしまいましょう。
\((a + ib)(\cos d + i \sin d) = (a \cos d + i^2 b \sin d) + i(b \cos d + a \sin d) = (a \cos d - b \sin d) + i(b \cos d + a \sin d)\) です。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int a = sc.nextInt(), b = sc.nextInt(), d = sc.nextInt();
double rad = d * Math.PI / 180; // 弧度に変換
double x = a * Math.cos(rad) - b * Math.sin(rad), y = b * Math.cos(rad) + a * Math.sin(rad); // 複素数平面上での掛け算を行う
out.printf("%.06f %.06f\n", x, y);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val a = sc.nextDouble()
val b = sc.nextDouble()
val d = sc.nextDouble()
val rad = d * Math.PI / 180 // 弧度に変換
val x = a * Math.cos(rad) - b * Math.sin(rad) // 複素数平面上での掛け算を行う
val y = b * Math.cos(rad) + a * Math.sin(rad) // 複素数平面上での掛け算を行う
println("%.06f %.06f".format(x, y))
}
}
方針3: 回転行列を用いる
アフィン変換を知っていれば、このような回転操作は行列積で表せることが分かります。
\( \begin{pmatrix} x \\ y \\ 1 \\ \end{pmatrix} = \begin{pmatrix} \cos d & -\sin d & 0 \\ \sin d & \cos d & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} a \\ b \\ 1 \\ \end{pmatrix} \)
より、 \((a \cos d - b \sin d, a \sin d + b \cos d)\) が導けます。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int a = sc.nextInt(), b = sc.nextInt(), d = sc.nextInt();
double rad = d * Math.PI / 180; // 弧度に変換
double x = a * Math.cos(rad) - b * Math.sin(rad), y = b * Math.cos(rad) + a * Math.sin(rad); // 回転行列を作用させる
out.printf("%.06f %.06f\n", x, y);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val a = sc.nextDouble()
val b = sc.nextDouble()
val d = sc.nextDouble()
val rad = d * Math.PI / 180 // 弧度に変換
val x = a * Math.cos(rad) - b * Math.sin(rad) // 回転行列を作用させる
val y = b * Math.cos(rad) + a * Math.sin(rad) // 回転行列を作用させる
println("%.06f %.06f".format(x, y))
}
}
方針4: こんな一般的な処理は標準ライブラリに任せる
上で書いた回転行列を用いた手法はもっと汎用的な方法があり、アフィン変換と呼ばれています。 アフィン変換を使った解法は回転だけでなく平行移動や鏡映など様々な操作を提供できるため、非常によく使われます。
ところで非常によく使われるならば、ライブラリとして出回っていても良さそうですよね？
実際、標準ライブラリにはAffineTransformが用意されており、簡単にアフィン変換を実装できます。
Javaの実装例
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int a = sc.nextInt(), b = sc.nextInt(), d = sc.nextInt();
double rad = d * Math.PI / 180; // 弧度に変換
AffineTransform affine = AffineTransform.getRotateInstance(rad); // 回転を表現するアフィン変換を得る
Point2D now = new Point2D.Double(a, b);
Point2D ans = affine.transform(now, null); // 変換を行う
out.printf("%.06f %.06f\n", ans.getX(), ans.getY());
}
}
}
Kotlinの実装例
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val a = sc.nextDouble()
val b = sc.nextDouble()
val d = sc.nextDouble()
val rad = d * Math.PI / 180 // 弧度に変換
val affine = AffineTransform.getRotateInstance(rad); // 回転を表現するアフィン変換を得る
val now = Point2D.Double(a, b)
val ans = affine.transform(now, null) // 変換を行う
println("%.06f %.06f".format(ans.getX(), ans.getY()))
}
}
C問題 - XX to XXX
この問題による操作がどのようなことをできるのか、に着目しましょう。
操作を見ると、同じ文字が並んでいるところを一つ選んで、その長さを \(1\) 増やす操作であることが分かります。 つまり、同じ文字間の長さだけが大事であることが分かります。
ここで、連続する同じ文字のことは連(Run)と呼ばれます。
試しに、abbaacを連で表すと \(((a, 1), (b, 2), (a, 2), (c, 1))\) となります。
この連の列に対して、行える操作を改めて考えます。 すると、できることは \(2\) 以上の長さの場所を増やすことだけです。
つまり、まず \(S\) と \(T\) をそれぞれ連で表した時、 \(S\) から \(T\) を構築するためには次の条件が必要であることが分かります。
- \(S\) と \(T\) の連の個数は等しい
- \(S\) の \(i\) 番目の連と \(T\) の \(i\) 番目の連はどちらも同じ文字である
- \(S\) の \(i\) 番目の連と \(T\) の \(i\) 番目の連の長さはどちらも \(1\) であるか、 \(S\) の連の長さが \(2\) 以上かつ \(T\) の連の長さが \(S\) の連の長さよりも長い
逆に、これらの条件を満たすならば \(S\) から \(T\) を構築することができます。
さて、実装を考えてみましょう。
まず、今回のように連の列に変換するアルゴリズムを連長圧縮(Run Length Encoding)と呼びます。 これは汎用的に使えるものなので、関数として切り出しておきましょう。
runLengthEncoding関数は入力として数列や文字列などを受け取り、連の列を返すアルゴリズムです。 連は要素と長さを持つペアとして表されます。 今回は簡単のため文字列にのみ対応しますが、他の形の列に対しても適用できるようにオーバーロードしておくと便利です。
この関数を \(S\) と \(T\) に呼び出した時、得られる連の列が条件を満たすかは、順に比較をしていけば分かります。
Javaの実装例
import java.util.ArrayList;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
String S = sc.next(), T = sc.next();
ArrayList<CharRun> rleS = runLengthEncoding(S), rleT = runLengthEncoding(T);
if (rleS.size() != rleT.size()) { // 操作によって連の個数は不変
out.println("No");
return;
}
for (int i = 0;i < rleS.size();++ i) {
CharRun runS = rleS.get(i), runT = rleT.get(i);
if (runS.c != runT.c) { // 違う文字ならNo
out.println("No");
return;
}
if (runS.length == 1 && runT.length != 1) { // 長さ1の連に操作はできない
out.println("No");
return;
}
if (runS.length > runT.length) { // 文字数を減らすことはできない
out.println("No");
return;
}
}
out.println("Yes");
}
}
/**
* 連を管理します。
* 連は文字c及び長さlengthで構成され、cがlength回続いていることを表します。
*/
public static class CharRun {
public final char c;
public int length;
CharRun(char c, int length) {
this.c = c;
this.length = length;
}
}
/**
* 連長圧縮を求めます。
* @param s 連長圧縮する文字列
* @return 連長圧縮した文字列
*/
public static ArrayList<CharRun> runLengthEncoding(String s) {
ArrayList<CharRun> rle = new ArrayList<>();
char last = '\0';
int len = -1;
for (char c : s.toCharArray()) {
if (len == -1) {
last = c;
len = 1;
continue;
}
if (last == c) {
++ len;
continue;
}
rle.add(new CharRun(last, len));
last = c;
len = 1;
}
if (len != -1) rle.add(new CharRun(last, len));
return rle;
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val S = sc.next()
val T = sc.next()
val rleS = runLengthEncoding(S)
val rleT = runLengthEncoding(T)
if (rleS.size != rleT.size) { // 操作によって連の個数は不変
println("No")
return
}
for (i in rleS.indices) {
val runS = rleS[i]
val runT = rleT[i]
if (runS.c != runT.c) { // 違う文字ならNo
println("No")
return
}
if (runS.length == 1 && runT.length != 1) { // 長さ1の連に操作はできない
println("No")
return
}
if (runS.length > runT.length) { // 文字数を減らすことはできない
println("No")
return
}
}
println("Yes")
}
}
/**
* 連を管理します。
* 連は文字c及び長さlengthで構成され、cがlength回続いていることを表します。
*/
data class CharRun(val c : Char, var length: Int)
/**
* 連長圧縮を求めます。
* @param s 連長圧縮する文字列
* @return 連長圧縮した文字列
*/
fun runLengthEncoding(s: String): List<CharRun> {
val rle = mutableListOf<CharRun>()
var last = 0.toChar()
var len = -1
for (c in s.toCharArray()) {
if (len == -1) {
last = c
len = 1
continue
}
if (last == c) {
++ len
continue
}
rle.add(CharRun(last, len))
last = c
len = 1
}
if (len != -1) rle.add(CharRun(last, len))
return rle
}
D問題 - Circumferences
この問題は、二つのパートに分けることができます。
まず、第一パートではどの円からどの円に移動できるかを調べることで、移動可能な円の関係を見ていきます。
二つの円 \((x_i, y_i, r_i), (x_j, y_j, r_j)\) の円周が交差するか判定してみましょう。
作図してみると分かりますが、大事なのは円同士の距離及びそれぞれの半径の大きさです。 そこで、距離 \(d = \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} \) と置いておきます。
この時、二つの円の円周が交差する条件は、 \(|r_i - r_j| \leq d \leq r_i + r_j\) です。 \(r_i \leq r_j\) の時について円 \(j\) の円周に円 \(i\) が内側と外側のそれぞれで接する条件を考えると、上記の式を導きやすいと思います。
さて、二つの円が与えられたときに双方向に移動可能か分かったなら、第二パートでは \((s_x, s_y)\) から \((t_x, t_y)\) へ移動可能かを調べます。
まず、円と点という複数のものが混ざると実装が難しくなるため、点 \((x, y)\) を半径 \(0\) で中心が \((x, y)\) の円だと思うことにします。
このとき、本問題は次のように表されます。
- \(N+2\) 個の円と、それぞれの円が行き来可能か否かが与えられます。この時、円 \(s\) から円 \(t\) に行くことができるか判定してください。
これは円 \(s\) と円 \(t\) が連結か否かが分かればよく、幅優先探索やUnion-Find法などで \(O(N^2)\) で求めることができます。
誤差のお話
おそらく、上で見た通りに実装するとWrong Answerになるはずです。 これは何故でしょうか？
確認のため、二つの円に対して接しているか判定する部分を確かめてみましょう。
まず、Circleクラスを作ります。これは中心と半径を管理する構造体です。
中心及び半径は、制約の範囲だとintに収まるのでintで管理することにします。
Javaの実装例
class Circle {
int x, y;
int r;
Circle(int x, int y, int r) {
this.x = x;
this.y = y;
this.r = r;
}
boolean intersect(Circle other) {
double d = Math.sqrt(Math.pow(x - other.x, 2) + Math.pow(y - other.y, 2));
return Math.abs(r - other.r) <= d && d <= r + other.r;
}
}
Kotlinの実装例
data class Circle(val x: Int, val y: Int, val r: Int) {
intersect(other: Circle): Boolean {
d = sqrt((x - other.x).toDouble().pow(2) + (y - other.y).toDouble().pow(2))
return abs(r - other.r) <= d && d <= r + other.r
}
}
さて、これを用いて3つの円を調べてみましょう。 円 \(1\) は中心 \((0, 0)\) で半径が \(5 \times 10^8\) の円です。 円 \(2\) は中心 \((10^9, 0)\) で半径が \(5 \times 10^8\) の円です。 円 \(3\) は中心 \((10^9, 1)\) で半径が \(5 \times 10^8\) の円です。
円 \(1\) と円 \(2\) の間の距離 \(d\) は \(\sqrt{(10^9-0)^2+(0-0)^2}=10^9\) で、 \(0 = |5 \times 10^8 - 5 \times 10^8| \leq d \leq 5 \times 10^8 + 5 \times 10^8 = 10^9\) より二つの円は交差します。
円 \(1\) と円 \(3\) の間の距離 \(d\) は \(\sqrt{(10^9-0)^2+(1-0)^2} \sim 1000000000.0000000005\) で、 \(0 = |5 \times 10^8 - 5 \times 10^8| \leq d > 5 \times 10^8 + 5 \times 10^8 = 10^9\) より二つの円は交差しません。
しかし、実際に先ほどの構造体を用いて判定を行うと、円 \(1\) と円 \(3\) も交差していると判定されます。
どうしてこんなことになるのでしょうか？
この問題は、 \((x_i-x_j)^2+(y_i-y_j)^2\) を平方根を計算するためにdouble型に変換したときに発生しています。
まず、double型とはどのような型なのかを確認します。
double型はIEEE 754によって規定された倍精度浮動小数点数であり、符号が1bit、指数部が11bit、仮数部が52bitで表されます。
符号を \(s\) 、指数部を \(e\) 、仮数部を \(f\) とします。 この時、小数は \((-1)^s \times 2^{e-2^{11-1}+1} \times \frac{2^{52} + f}{2^{52}}\) として表されます。
試しに、 \(10^{18}\) を上の形で表してみましょう。
Double.doubleToRawLongBitsを用いて出力させると、0100001110101011110000010110110101100111010011101100100000000000という値が求まります。
これは符号 \(s=0\) 、指数部 \(e=10000111010_{(2)}=1082\) 、 仮数部 \(f=1011110000010110110101100111010011101100100000000000_{(2)}=3308900372629504\) です。
また、小数は \((-1)^s \times 2^{e-2^{11-1}+1} \times \frac{2^{52} + f}{2^{52}} = 2^{59} \times \frac{2^{52} + 3308900372629504}{2^{52}}=10^{18}\) であり、正しく表せていることが分かります。
ところで、 \(10^{18}+1\) を出力させると、0100001110101011110000010110110101100111010011101100100000000000という値が求まります。
これは先ほどと同じ \(10^{18}\) になりますね？
何故このようになったかというと、doubleは仮数部を52bitしか持っていません。 従って、 \(10^{18}+1\) という60bit必要な情報を正確に格納することはできず、誤差が発生します。 このとき、表せる範囲で最も近い値に丸められた結果、 \(10^{18}+1\) はdouble型において \(10^{18}\) と同じ値になります。
さて、そうすると、本問題でdoubleを使うと必ず誤った答えを返してしまうことが分かりました。 そのため、本問題をACするためにはdoubleを経由せず、整数のまま解く必要があります。
判定式 \(|r_i - r_j| \leq \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} \leq r_i + r_j\) ですが、Math.sqrtを使おうとするならdoubleを使うことは避けられません。
そこで、判定式の両辺を2乗してみましょう。
すると、 \((r_i - r_j)^2 \leq (x_i-x_j)^2+(y_i-y_j)^2 \leq (r_i + r_j)^2\) となり、これは全て整数で扱えます。値域も最大で \(8 \times 10^{18}\) で、これは63bitに収まるのでlong型で扱えます。
Javaの実装例
import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt();
Point s = new Point(sc.nextInt(), sc.nextInt()), t = new Point(sc.nextInt(), sc.nextInt());
Circle[] circle = new Circle[N + 2];
for (int i = 0;i < N;++ i) circle[i] = new Circle(sc.nextInt(), sc.nextInt(), sc.nextInt());
final int S = N, T = N + 1; // 始点と終点
circle[S] = new Circle(s.x, s.y, 0);
circle[T] = new Circle(t.x, t.y, 0);
boolean[][] graph = new boolean[circle.length][circle.length];
for (int y = 0;y < circle.length;++ y) for (int x = 0;x < circle.length;++ x) graph[y][x] = circle[y].intersect(circle[x]); // graph[i][j]は、円iと円jの円周が交差するならtrue
boolean[] reachable = new boolean[circle.length];
Queue<Integer> bfs = new ArrayDeque<>();
reachable[S] = true;
bfs.add(S);
while(!bfs.isEmpty()) {
int source = bfs.poll();
for (int target = 0;target < circle.length;++ target) {
if (!graph[source][target] || reachable[target]) continue;
reachable[target] = true;
bfs.add(target);
}
}
out.println(reachable[T] ? "Yes" : "No");
}
}
}
class Circle {
int x, y, r;
Circle(int x, int y, int r) {
this.x = x;
this.y = y;
this.r = r;
}
long square(int x) {
return (long)x * x;
}
boolean intersect(Circle other) {
long squareDistance = square(x - other.x) + square(y - other.y);
return square(r - other.r) <= squareDistance && squareDistance <= square(r + other.r);
}
}
Kotlinの実装例
import java.awt.Point
import java.util.*
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val s = Point(sc.nextInt(), sc.nextInt())
val t = Point(sc.nextInt(), sc.nextInt())
val circle = MutableList(N) {Circle(sc.nextInt(), sc.nextInt(), sc.nextInt())}
circle.add(Circle(s.x, s.y, 0))
circle.add(Circle(t.x, t.y, 0))
val graph = Array(circle.size) { y ->
BooleanArray(circle.size) { x ->
circle[y].intersect(circle[x]) // graph[i][j]は、円iと円jの円周が交差するならtrue
}
}
val S = N // 始点の位置
val T = N + 1 // 終点の位置
val reachable = BooleanArray(circle.size) {it == S} // Sから辿り着ける頂点の集合
val bfs : Queue<Int> = ArrayDeque()
bfs.add(S)
while(!que.isEmpty()) {
val source = bfs.poll()
for (target in 0 until circle.size) {
if (!graph[source][target] || reachable[target]) continue
reachable[target] = true
bfs.add(target)
}
}
println(if (reachable[T]) "Yes" else "No")
}
}
data class Circle(val x: Int, val y: Int, val r: Int) {
fun intersect(other: Circle): Boolean {
val squareDistance = square(x - other.x) + square(y - other.y)
return square(r - other.r) <= squareDistance && squareDistance <= square(r + other.r)
}
}
fun square(x: Int): Long {
return x.toLong() * x.toLong()
}
余談: 実は最短経路も求まる
この問題で点 \(s\) から点 \(t\) に到達可能なとき、実はその最短経路も求めることができます。
円 \(x\) を固定して考えます。
円 \(x\) と円周が交差する円 \(y\) について、その交点は高々2つです。 それらをすべて記録し、円 \(y\) から見て時計回りに並べたものを \(p_1, p_2, \ldots, p_n\) とします。
このとき、 \(p_i\) と \(p_{i +1 \bmod n}\) の間にその円弧の長さに等しい重みの辺を貼ることとします。
このように構成したグラフは交点が \(O(N^2)\) 個、辺が \(O(N^2)\) 個の重み付きグラフとなるのでdijkstra法などを用いて計算量 \(O(N^2 \log N)\) などで解くことができます。
このように最短経路問題にする場合はdouble型を経由せばならず、誤差を考える必要があります。
しかし、交点の座標の誤差が \(2^{-50} \sim 10^{-15}\) としたとき、 \((\min, +)\) 半環で計算をする際は高々 \(N\) 個の値の和を見るので \(N \times 10^{-15} \leq 10^{-11}\) と、高い精度で答えを求めることができます。
posted:
last update: