AtCoder Beginner Contest 319参加記（A～C）
AtCoder Beginner Contest 319に参加したので記録を残します。
今回は2完！残念です。
A - Legendary Players
これはもうベタ書きするしかない感じですね。
fun main() {
val s = readln()
when (s) {
"tourist" -> {
println(3858)
}
"ksun48" -> {
println(3679)
}
"Benq" -> {
println(3658)
}
"Um_nik" -> {
println(3648)
}
"apiad" -> {
println(3638)
}
"Stonefeang" -> {
println(3630)
}
"ecnerwala" -> {
println(3613)
}
"mnbvmar" -> {
println(3555)
}
"newbiedmy" -> {
println(3516)
}
"semiexp" -> {
println(3481)
}
}
}
テキスト全体をコピーして、そこからMapを生成するとかするとだいぶマシな感じになるんですが、コンテスト中はわちゃわちゃしていてうまく書けず。
fun main() {
val s = readln()
val map = """
tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481
""".trimIndent()
.split("\n")
.map { it.split(" ") }
.associate { it.first() to it.last() }
println(map[s])
}
本当は↑こうしたかったですね。
B - Measure
問題文の通りに書くだけなんですが、問題文の意味を読み取るのに少し時間がかかりました。
1 以上 9 以下の N の約数 j であって というのがわかりづらかったですが、つまり
なので、
fun main() {
val n = readln().toInt()
val list = mutableListOf<Int>()
for(i in 1..9) {
if(n % i == 0 ) {
list.add(i)
}
}
val sb = StringBuilder()
for(i in (0..n)) {
var flg = false
for(j in list) {
if(i % (n / j) == 0) {
sb.append(j)
flg = true
break
}
}
if(!flg) {
sb.append("-")
}
}
println(sb)
}
よくわからない空白があったり、i in (0..n)とか普段は書かない（カッコを付けない）書き方をしていたりなど、すごく慌てていたのがよくわかります。
C - False Hope
これは解けませんでした。これも愚直に全部調べるだけでいいのですが、実装しきる前にタイムアップ。残念です。コンテスト終了後に解けました…
これも はじめに知ったほうの2マスというのがよくわからず、最初に見つかった2マスなのかと勘違いしていました。実際には、ビンゴか何かだと思えばわかりやすいですね。今回いずれかの数字を知ったことで、縦、横、斜めのいずれかの並びの3マス全てが判明したときの、今回数字を知ったマス以外の2マスがはじめに知ったほうの2マスですね。
（言葉で説明するの意外と難しい・・・）
9つの位置に対応する数字をランダムな順番で知るわけですが、そのランダムな順番としてあり得るのは9の階乗通りで、具体的には362880通りです。これくらいなら全探索できるので、これを全部試します。
import kotlin.math.abs
fun main() {
val table = List(3) {
readln().split(" ").map { it.toInt() }
}
var known: Array<BooleanArray>
var sad = 0L
val arr = IntArray(9) { it }
while1@do {
known = Array(3) { BooleanArray(3) }
for(z in 0 until 9) {
val (i, j) = index(arr[z])
if(judgeSad(i, j, known, table)) {
sad++
known[i][j] = true
continue@while1
}
known[i][j] = true
}
} while (arr.nextPermutation())
println((362880 - sad).toDouble() / 362880)
}
private fun judgeSad(ii: Int, jj: Int, known: Array<BooleanArray>, table: List<List<Int>>): Boolean {
fun otherIndex(index: Int): Pair<Int, Int> {
return (index + 1) % 3 to (index - 1 + 3) % 3
}
fun judgeBeside(i: Int, j: Int): Boolean {
val (j2, j3) = otherIndex(j)
if(!known[i][j2] || !known[i][j3]) {
return false
}
if(table[i][j2] == table[i][j3] && table[i][j] != table[i][j2]) {
return true
}
return false
}
fun judgeVertical(i: Int, j: Int): Boolean {
val (i2, i3) = otherIndex(i)
if(!known[i2][j] || !known[i3][j]) {
return false
}
if(table[i2][j] == table[i3][j] && table[i][j] != table[i2][j]) {
return true
}
return false
}
fun judgeDiagonal1(i: Int, j: Int) : Boolean{
val (i2, i3) = otherIndex(i)
val (j2, j3) = otherIndex(j)
if(i == j2 || i == j3 || j == j2 || j == j3) {
return false
}
if(!known[i2][j2] || !known[i3][j3]) {
return false
}
if(table[i2][j2] == table[i3][j3] && table[i][j] != table[i2][j2]) {
return true
}
return false
}
fun judgeDiagonal2(i: Int, j: Int):Boolean {
val indices = mutableListOf<Pair<Int, Int>>()
for(iii in 0 until 3) {
val jjj = abs(iii - 2)
if(iii != i && jjj != j) {
indices.add(iii to jjj)
}
}
if(indices.size != 2) {
return false
}
val (i2, j2) = indices[0]
val (i3, j3) = indices[1]
if(!known[i2][j2] || !known[i3][j3]) {
return false
}
if(table[i2][j2] == table[i3][j3] && table[i][j] != table[i2][j2]) {
return true
}
return false
}
// 横
if (judgeBeside(ii, jj)) {
return true
}
// 縦
if(judgeVertical(ii, jj)) {
return true
}
// 斜め（負の傾き）
if(judgeDiagonal1(ii, jj)) {
return true
}
// 斜め（正の傾き）
if(judgeDiagonal2(ii, jj)) {
return true
}
return false
}
private fun index(i: Int): Pair<Int, Int> {
return when(i) {
0 -> 0 to 0
1 -> 0 to 1
2 -> 0 to 2
3 -> 1 to 0
4 -> 1 to 1
5 -> 1 to 2
6 -> 2 to 0
7 -> 2 to 1
8 -> 2 to 2
else -> {-1 to -1}
}
}
// https://qiita.com/marienplatz/items/57013b2bbe1972f4fa17
fun IntArray.nextPermutation(): Boolean {
val n = size
var i = n - 2
// 末尾から、最初に大小関係が昇順になっている要素を探す
while (i >= 0) {
if (this[i] < this[i + 1]) break
i--
}
// 要素が全て降順になっていたらreturn
if (i < 0) return false
// i番目の要素を最初に上回る要素を末尾から探す
var j = n
do {
j--
} while (this[i] > this[j])
// 同じ値は想定しない
if (this[i] == this[j]) throw IllegalArgumentException("elements are the same")
// i番目の要素を最初に上回る要素をi番目の要素とswapする
val tmp = this[i]
this[i] = this[j]
this[j] = tmp
//
this.reverse(i + 1, n)
return true
}
けっこうエグい実装になりましたが、内容的にはほんとに全部試しているだけですね。
コンテスト中に通らなかった原因は、1-indexedに補正しようとしていたけど0-indexedじゃないと動かない実装をしている箇所があったとか、よく見ると探索範囲が間違っていたとか、しょうもないミスの積み重ねでした。
また、ランダムな数字の全組み合わせを求めるのは言語によっては標準ライブラリでできるのですがKotlinにはなく、かといって自分で実装したくもなく、ネットから拾ってしまいました。ありがとうございます or すみません。
あと細かいけど「がっかりする」というのはsadというよりdisappointedのほうが近そうですね。
感想
今回のCのような問題を解けるようにするには似たような問題をひたすら解いて練習するしかなさそうですが、今はなかなかその時間がとれないので当分は似たような結果が続くでしょうね。
良い結果ではないけど、先週みたいな体調不良によるUnratedではなく一応Ratedで参加できたので良しとします。
（執筆時間: 36分45秒）
Discussion