AtCoder Beginner Contest 270 A～Cのメモ
トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)に参加したのでメモを残しておきます。
A - 1-2-4 Test
絶対もっとマシな方法あるわーと思いながら投げつけたのがこちら。
fun main() {
val (a, b) = readLine()!!.split(" ").map { it.toInt() }
var test1 = 0
var test2 = 0
var test3 = 0
when(a) {
1 -> {
test1 = 1
}
2 -> {
test2 = 2
}
3 -> {
test1 = 1
test2 = 2
}
4 -> {
test3 = 4
}
5 -> {
test1 = 1
test3 = 4
}
6 -> {
test2 = 2
test3 = 4
}
7 -> {
test1 = 1
test2 = 2
test3 = 4
}
}
when(b) {
1 -> {
test1 = 1
}
2 -> {
test2 = 2
}
3 -> {
test1 = 1
test2 = 2
}
4 -> {
test3 = 4
}
5 -> {
test1 = 1
test3 = 4
}
6 -> {
test2 = 2
test3 = 4
}
7 -> {
test1 = 1
test2 = 2
test3 = 4
}
}
println(test1 + test2 + test3)
}
なかなか酷い…
以下のような実装でよかったようです。
fun main() {
val (a, b) = readLine()!!.split(" ").map { it.toInt() }
println(a or b)
}
1、2、4は2の乗数なので単純にOR演算すればよかったと。1、2、4という並びを見てピンと来るべきだったんですね。まだまだ修行が足りない。
B - Hammer
なかなか苦労しました。よく見たらなんかimportに変なのがいますね…
import kotlin.math.abs
import kotlin.math.atan
fun main() {
val (x, y, z) = readLine()!!.split(" ").map { it.toInt() }
val tx = if(x > 0) {
(0..x).toList()
} else {
(0 downTo x).toList()
}
val ty = if(y > 0) {
(0..y).toList()
} else {
(0 downTo y).toList()
}
val tz = if(z > 0) {
(0..z).toList()
} else {
(0 downTo z).toList()
}
if(!isOverlap(tx, ty)) {
println(abs(x))
} else if(abs(x) < abs(y)) {
println(abs(x))
} else {
if(!isOverlap(ty, tz)) {
println(abs(z) * 2 + abs(x))
} else {
if(abs(y) < abs(z)) {
println(-1)
} else {
println(abs(x))
}
}
}
}
fun isOverlap(a: List<Int>, b: List<Int>): Boolean {
return (a.toSet() intersect b.toSet()).any { it != 0 }
}
単純に大小関係だけで判定すると、正負の違いのせいでバグらせる予感しかしなかったので、区間として保持してそれが重複部分を持つかどうかで判定しています。
解説を見るともっと賢い方法でやっていますが、このアイデアでも多少は場合分けを減らせました。
まあ、それでもちょっと混乱して実装に時間がかかってしまいました。以前の私ならWAを出していたと思うので、一発で通っただけでもよしとしますｗ
C - Simple path
これは結局提出できず、解説ACしました。
木は扱ったことがあるので解けるような気がしたのですが全然そんなことはありませんでした。
今まで木を扱う時は以下のような感じのデータ構造を使っていました。
（雑に書いたので雰囲気だけ感じ取ってください）
data class Node(val value: Int, val children: List<Node>)
これだと実装できないってわけじゃないと思うのですが、これだと下にしか辿れないのでどこが根なのかはっきり決まっていないと対応できません。
私はまさに上のような構造で木を捉えていたので、木とは根が一意に決まっているものだと思っていました。
その認識だと、例2の以下を理解できません。（できませんでした）
どこが根なんだろう。というかこれは木なのか？って思ってました。
時間が経って、別にどこを根と捉えても成り立つとようやく気づきました。そういうものだったのですね。軽く衝撃を受けました。
そうなると、頂点Xを根として木を構築し、頂点Yを探索すればいいことになります。
ただ、入力をもとにどうやって木を構築すればいいのかとちょっと悩みました。こういうのは絶対過去に類似問題があるはずと思って、そこでどうやっているのか見てみようと思いググりました。
たしかにそれらしいのはいくつか見つかったのですが、いずれも配列の配列で木を表現していました。上のNodeクラスのような構造にまだ頭を支配されていたので、どうしてそれで木を表現できるのかわかりませんでした。そして、この辺りでもう時間切れでしたｗ
解説を見て
まず配列の配列で木を表現するのは、実際にどうなっているのか見ればなんとなくわかりました。
上の木は、以下のように表現できます。
[[], [3, 2, 4], [5, 1, 6], [1], [1], [2], [2]]
ある頂点から辿れる頂点を配列として保持しています。頂点1から辿れるのは3、2、4なので添字1に対応する配列が[3, 2, 4]になっています。添字を活用するのってつい最近他の問題でも見ました…
（最初の空配列は1オリジンとして扱うためのダミーです）
これが優れているのは、柔軟に任意の頂点を根として選べることです。いや、根って表現するのがそもそもおかしいのかもしれません。要するに任意の頂点から探索を開始できます。慣れている人からすると当たり前だと思いますが、上のNodeクラスではできないことです…ｗ
まあこれで木を表すことができたので、あとはDFSで探索すればいいということになります。木を作ってDFSすればいいとは思っていましたが、そもそも木を作るところで躓いていたのでなんとも残念な話です。
まあ値を受け取るところとDFSの部分がいまいち消化できていないのですが、もう一つのイディオムとして記憶してしまおうと思います。（なんか前も同じようなことを書きましたが…）
最終的なコードは以下のようになりました。
import java.io.PrintWriter
private var graph: MutableList<MutableList<Int>> = mutableListOf()
private var n: Int = 0
private var x: Int = 0
private var y: Int = 0
private val ans = mutableListOf<Int>()
class Main: Runnable {
override fun run() {
val br = System.`in`.bufferedReader()
val (tn, tx, ty) = readLine()!!.split(" ").map { it.toInt() }
n = tn
x = tx
y = ty
graph = MutableList(n + 1) { mutableListOf<Int>() }
repeat(n - 1) {
val (u, v) = br.readLine()!!.split(" ").map { it.toInt() }
graph[u].add(v)
graph[v].add(u)
}
//println(graph)
dfs(y, -1)
val out = PrintWriter(System.out)
ans.indices.forEach {
out.print(ans[it])
if(it == ans.size - 1) {
out.println()
} else {
out.print(' ')
}
}
out.flush()
}
}
fun main() {
Thread(null, Main(), "", 128 * 1024 * 1024).start()
}
fun dfs(v: Int, p: Int): Boolean {
if(v == x) {
ans.add(v)
return true
}
for(u in graph[v]) {
if(u == p) {
continue
}
if(dfs(u, v)) {
ans.add(v)
return true
}
}
return false
}
いろいろと余分なコードがあるのは後で説明します。
XからYを探索すると、出力は逆順になります。任意の頂点から探索を開始できるなら、YからXを探索すればいいよねってことでそうなっています。
解説だとラムダ式を使っていましたが、Kotlinだとちょっとどうやって書いていいかよくわからない点があったので、変数をグローバル化して普通の関数としてdfsを実装しました。
注意が必要なのは、子を探索する時に子は親も参照しているので、循環しないようにガードする必要があります。
解説の書き写しでは通らなかった話
上記の余分なコードについてです。
最初は以下を提出しました。
private var graph: MutableList<MutableList<Int>> = mutableListOf()
private var n: Int = 0
private var x: Int = 0
private var y: Int = 0
private val ans = mutableListOf<Int>()
fun main() {
val (tn, tx, ty) = readLine()!!.split(" ").map { it.toInt() }
n = tn
x = tx
y = ty
graph = MutableList(n + 1) { mutableListOf<Int>() }
repeat(n - 1) {
val (u, v) = readLine()!!.split(" ").map { it.toInt() }
graph[u].add(v)
graph[v].add(u)
}
//println(graph)
dfs(y, -1)
println(ans.joinToString(" "))
}
fun dfs(v: Int, p: Int): Boolean {
if(v == x) {
ans.add(v)
return true
}
for(u in graph[v]) {
if(u == p) {
continue
}
if(dfs(u, v)) {
ans.add(v)
return true
}
}
return false
}
しかし、これはなんとREになりました。
まず疑うべきは配列の範囲外参照ですが、見直してもその恐れがある箇所は見つけられませんでした。
次に疑ったのはスタックオーバーフローです。以前読んだ記事で、JavaだとC++に比べて再帰を使った時にスタックオーバーフローが起こりやすいと書いてあったのを思い出したのです。
JVMで動くという意味でKotlinでも同じだろうと思いました。なので、上記記事の内容に従ってスタックサイズを多めに確保したスレッドを作って実行するようにしました。
private var graph: MutableList<MutableList<Int>> = mutableListOf()
private var n: Int = 0
private var x: Int = 0
private var y: Int = 0
private val ans = mutableListOf<Int>()
class Main: Runnable {
override fun run() {
val (tn, tx, ty) = readLine()!!.split(" ").map { it.toInt() }
n = tn
x = tx
y = ty
graph = MutableList(n + 1) { mutableListOf<Int>() }
repeat(n - 1) {
val (u, v) = readLine()!!.split(" ").map { it.toInt() }
graph[u].add(v)
graph[v].add(u)
}
//println(graph)
dfs(y, -1)
println(ans.joinToString(" "))
}
}
fun main() {
Thread(null, Main(), "", 16 * 1024 * 1024).start()
}
fun dfs(v: Int, p: Int): Boolean {
if(v == x) {
ans.add(v)
return true
}
for(u in graph[v]) {
if(u == p) {
continue
}
if(dfs(u, v)) {
ans.add(v)
return true
}
}
return false
}
REは消えましたが、今度はいくつかWAが出ました。
もう開き直って解説動画のコードをほぼ写しているので、アルゴリズム面での誤りがあるとは考えづらいです。どうしたものだろうか…
ここまで来てようやく気づいたのですが、この問題って個数とかでなくパスの過程の頂点を全て出力する必要があるので、出力が大量になる可能性がありますね？
そうなると気になるのは最後の出力部分です。
println(ans.joinToString(" "))
カジュアルに使ってますが、これってリストの要素を全て結合した文字列を生成するので、大量データの場合は巨大な文字列が生成されてしまうんですよね。WAと関係があるかはわかりませんが、ちょっと嫌な感じなのでループして出力するようにしました。
import java.io.PrintWriter
private var graph: MutableList<MutableList<Int>> = mutableListOf()
private var n: Int = 0
private var x: Int = 0
private var y: Int = 0
private val ans = mutableListOf<Int>()
class Main: Runnable {
override fun run() {
val (tn, tx, ty) = readLine()!!.split(" ").map { it.toInt() }
n = tn
x = tx
y = ty
graph = MutableList(n + 1) { mutableListOf<Int>() }
repeat(n - 1) {
val (u, v) = readLine()!!.split(" ").map { it.toInt() }
graph[u].add(v)
graph[v].add(u)
}
//println(graph)
dfs(y, -1)
val out = PrintWriter(System.out)
ans.indices.forEach {
out.print(ans[it])
if(it == ans.size - 1) {
out.println()
} else {
out.print(' ')
}
}
out.flush()
}
}
fun main() {
Thread(null, Main(), "", 16 * 1024 * 1024).start()
}
fun dfs(v: Int, p: Int): Boolean {
if(v == x) {
ans.add(v)
return true
}
for(u in graph[v]) {
if(u == p) {
continue
}
if(dfs(u, v)) {
ans.add(v)
return true
}
}
return false
}
ついでに、PrintWriterでラップして都度フラッシュしないようにすることで高速化しました。このテクニックは知ってはいましたが、今まで大量出力するケースに遭遇したことがなくて使っていませんでした。
これでなぜか通りました。WAは謎ですが、まあ大量出力の場合は気をつけないといけないということですね…
ただ、実行が遅いのが気になりました。出力だけでなく入力も大量なので、そちらのせいかもしれません。
入力の高速化については知見がないのですが、BufferedReaderを使っているコードを見たことがあったのでそうしてみます。
import java.io.PrintWriter
private var graph: MutableList<MutableList<Int>> = mutableListOf()
private var n: Int = 0
private var x: Int = 0
private var y: Int = 0
private val ans = mutableListOf<Int>()
class Main: Runnable {
override fun run() {
val br = System.`in`.bufferedReader()
val (tn, tx, ty) = br.readLine()!!.split(" ").map { it.toInt() }
n = tn
x = tx
y = ty
graph = MutableList(n + 1) { mutableListOf<Int>() }
repeat(n - 1) {
val (u, v) = br.readLine()!!.split(" ").map { it.toInt() }
graph[u].add(v)
graph[v].add(u)
}
//println(graph)
dfs(y, -1)
val out = PrintWriter(System.out)
ans.indices.forEach {
out.print(ans[it])
if(it == ans.size - 1) {
out.println()
} else {
out.print(' ')
}
}
out.flush()
}
}
fun main() {
Thread(null, Main(), "", 16 * 1024 * 1024).start()
}
fun dfs(v: Int, p: Int): Boolean {
if(v == x) {
ans.add(v)
return true
}
for(u in graph[v]) {
if(u == p) {
continue
}
if(dfs(u, v)) {
ans.add(v)
return true
}
}
return false
}
そしたらまたWAが出ました。なぜ……
動作的には変わると思えなかったので謎です。前述の記事で「WAが実はRE」というケースがあると書いてあったので、それっぽい気がしました。
そしてREの内容としてはリソース不足的なやつしか思いつかなかったので、とりあえずスタックをさらに拡張してみます。
import java.io.PrintWriter
private var graph: MutableList<MutableList<Int>> = mutableListOf()
private var n: Int = 0
private var x: Int = 0
private var y: Int = 0
private val ans = mutableListOf<Int>()
class Main: Runnable {
override fun run() {
val br = System.`in`.bufferedReader()
val (tn, tx, ty) = readLine()!!.split(" ").map { it.toInt() }
n = tn
x = tx
y = ty
graph = MutableList(n + 1) { mutableListOf<Int>() }
repeat(n - 1) {
val (u, v) = br.readLine()!!.split(" ").map { it.toInt() }
graph[u].add(v)
graph[v].add(u)
}
//println(graph)
dfs(y, -1)
val out = PrintWriter(System.out)
ans.indices.forEach {
out.print(ans[it])
if(it == ans.size - 1) {
out.println()
} else {
out.print(' ')
}
}
out.flush()
}
}
fun main() {
Thread(null, Main(), "", 128 * 1024 * 1024).start()
}
fun dfs(v: Int, p: Int): Boolean {
if(v == x) {
ans.add(v)
return true
}
for(u in graph[v]) {
if(u == p) {
continue
}
if(dfs(u, v)) {
ans.add(v)
return true
}
}
return false
}
これで再び通り、多少速くなりました。まだ遅いっちゃ遅いですが、1600msとかよりはだいぶマシに見えるのでこれくらいで満足しておきます。
ということでこれが最終的なコードになります。
追記
スタックを使ってDFSを実現する（再帰関数を使わない）ことでスタック拡張をせずに通すコードをTwitterで教えてもらいました。
そういう手もあるのですね…！
教訓
- ビット演算にもっと慣れる必要がある
- 木は任意の頂点を根と見なせる
- 木は配列の配列で扱うと便利（典型的なパターンとして覚える）
- 入力、出力が大量になるケースは要注意
Discussion