AtCoder Beginner Contest 314参加記（A～D）
AtCoder Beginner Contest 314に参加したので記録を残します。
久しぶりにRated参加できました。遅め3完で成績は微妙だけど意外と満足。Dはコンテスト後に通したものです。
A - 3.14
問題文に記載されている円周率をコピペしてStringとして扱って必要な部分だけ切り取って出力です。
新ジャッジでKotlinのバージョンが上がっているので今まで readLine()!! になっていたところを readln() にしました。どうせここはスニペット化しているのであまり関係ないのですが、!!がなくなって見た目が少しすっきり。
fun main() {
val n = readln().toInt()
val s = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
println(s.substring(0, n + 2))
}
実行時間も少し速くなっています。
B - Roulette
問題文の通りやるだけなのですが、ちょっと実装が面倒な感じ。最初なぜか人の番号ではなく賭けた個数を出力しようとしていてちょっともたつきました。
import kotlin.math.min
fun main() {
val n = readln().toInt()
val list = List(n) {
val c = readln().toInt()
val a = readln().split(" ").map { it.toInt() }
it + 1 to a
}
val x = readln().toInt()
val ans = mutableListOf<Pair<Int, Int>>()
var m = Int.MAX_VALUE
for((c, a) in list) {
if(x !in a) {
continue
}
m = min(m, a.size)
ans.add(c to a.size)
}
val count = ans.filter { it.second == m }
println(count.size)
val s = ans.filter { it.second == m }.sortedBy { it.first }.map { it.first }.joinToString(" ")
println(s)
}
C - Rotate Colored Subsequence
問題文の意味を理解するのに少し時間がかかりました。同じ色を持つ文字ごとにグループ化して、その中でローテーションするってことですね。
色別に見ると、それぞれが互いに影響を与えず独立して操作可能なので、それぞれに対して操作をして、操作結果をもとに答えの文字列を作って出力でいけますね。
操作内容は各色に対して一度しか実行しません。操作自体は線形時間かかりそうで、見かけ上は二重ループになりますが、処理対象は全部で
色に対応する番号ごとに可変長配列を持たせて、各可変長配列ごとにローテーションをする、出力時は各色ごとに何番目まで出力したかを持たせて対応しました。
import java.util.Collections
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val s = readln()
val c = readln().split(" ").map { it.toInt() }
val wholeList = MutableList<MutableList<Int>>(m + 1) { mutableListOf() }
for(i in 0 until n) {
val color = c[i]
wholeList[color].add(i)
}
for(list in wholeList) {
val size = list.size
if(size == 0) {
continue
}
if(size == 1) {
continue
} else if(size == 2) {
Collections.swap(list, 0, 1)
} else {
val tail = list.last()
for(j in size - 2 downTo 0) {
list[j + 1] = list[j]
}
list[0] = tail
}
}
val sb = StringBuilder()
val table = IntArray(m + 1)
for(cc in c) {
sb.append(s[wholeList[cc][table[cc]]])
table[cc]++
}
println(sb)
}
ローテーション部分は自分で実装してましたが、 Collections.rotate() で一発でしたね…
Collections はけっこう便利です。
import java.util.Collections
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val s = readln()
val c = readln().split(" ").map { it.toInt() }
val wholeList = MutableList<MutableList<Int>>(m + 1) { mutableListOf() }
for(i in 0 until n) {
val color = c[i]
wholeList[color].add(i)
}
for(list in wholeList) {
val size = list.size
if(size == 0) {
continue
}
Collections.rotate(list, 1)
}
val sb = StringBuilder()
val table = IntArray(m + 1)
for(cc in c) {
sb.append(s[wholeList[cc][table[cc]]])
table[cc]++
}
println(sb)
}
D - LOWER
これは解けませんでした。実装したけどWAが2つあって通らず。翌日に考え直したら普通に通りました。残念。
まず最後の操作が操作2なら全部小文字、操作3なら全部大文字になることはわかります。これらは互いの操作を打ち消すので、最後に実行されたのがどちらなのかが重要となります。
最後の操作が操作1なら、その前に実行された操作1以外の操作が操作2であれば全部小文字にした後にそれ以降の操作1の結果だけ上書きする、みたいに考えられます。
操作2も操作3も一度も実行されない可能性も考慮します。
fun main() {
val n = readln().toInt()
val s = readln()
.toCharArray()
val q = readln().toInt()
val queryList = List(q) {
val txc = readln().split(" ")
Query(txc[0].toInt(), txc[1].toInt(), txc[2].first())
}
var last = 0
var lastCaseType = 0 to -1
var lowerOccurred = false
var upperOccurred = false
for(i in queryList.indices) {
val (t, x, c) = queryList[i]
last = t
when(t) {
1 -> {
s[x-1] = c
}
2 -> {
lowerOccurred = true
lastCaseType = 2 to i
}
3 -> {
upperOccurred = true
lastCaseType = 3 to i
}
}
}
if(!lowerOccurred && !upperOccurred) {
println(s.joinToString(""))
return
}
when (last) {
2 -> {
println(s.joinToString("").lowercase())
}
3 -> {
println(s.joinToString("").uppercase())
}
else -> {
printAns(queryList, n, s, lastCaseType)
}
}
}
private fun printAns(queryList: List<Query>, n: Int, s: CharArray, lastCaseType: Pair<Int, Int>) {
val tails = queryList.subList(lastCaseType.second, queryList.size).associate { it.x - 1 to it.c }
val sb = StringBuilder()
for(i in 0 until n) {
if(i in tails) {
sb.append(tails[i]!!)
} else {
if(lastCaseType.first == 2) {
sb.append(s[i].lowercase())
} else {
sb.append(s[i].uppercase())
}
}
}
println(sb)
}
data class Query(
val t: Int,
val x: Int,
val c: Char,
)
WAになっていたのは、最後の操作が操作1の場合、最後に実行された操作2（あるいは操作3）の後に実行された操作1の結果を全部反映しなければいけないのに、最後の1つしか反映していなかったためです。残念。
感想
Dを落としたのと、Cに時間がかかりすぎたのは残念でした。成績としては良くないのですが、それでも楽しかったですね。精進が止まっていたのでしばらくはこんな調子でしょう。まずはとにかく参加して、Rated参加を再度習慣化できるようにしていきたいと思います。
（執筆時間: 39分44秒）
Discussion