AtCoder Beginner Contest 378参加記
AtCoder Beginner Contest 378に参加したので記録を残します。
ACで2完の爆死です。ミスってこうなったというより、今は実際にこれくらいの実力まで落ちているように感じます。たぶん。
A - Pairing
各数値が何個あるか調べました。4個あれば2回、3個か2個なら1回、1個か0個なら0回です。
fun main() {
val a = readln().split(" ").map { it.toInt() }
val b = IntArray(5)
for(i in a.indices) {
b[a[i]]++
}
var ans = 0
for(i in b.indices) {
if(b[i] == 2) {
ans++
}
if(b[i] == 3) {
ans++
}
if(b[i] == 4) {
ans += 2
}
}
println(ans)
}
B - Garbage Collection
計算ができないので諦めました。制約が大きいのでシミュレーションはできず。
コンテスト後に落ち着いて考えたら解けました。質問ごとに独立して考えればいいのですが、なんかごっちゃになってました。
思考が明後日の方向に進みましたが、
計算ができないので、このレベルの計算式もがっつり考え込まないと出てきません。
fun main() {
val n = readln().toInt()
val qr = List(n) {
val (q, r) = readln().split(" ").map { it.toInt() }
q to r
}
val qq = readln().toInt()
for(i in 0 until qq) {
val (t, d) = readln().split(" ").map { it.toInt() }
val (q, r) = qr[t-1]
val mod = d % q
if(mod == r) {
println(d)
} else if(mod < r) {
val diff = r - mod
println(d + diff)
} else {
val diff = q - (mod - r)
println(d + diff)
}
}
}
C - Repeating
この問題は癒やし。各数値ごとに出現位置のリストを作って、前回の位置をそこから習得しました。リストを作りきってからだと探索に時間がかかってしまうので、リストは都度作っていきます。
fun main() {
val n = readln().toInt()
val a = listOf(0) + readln().split(" ").map { it.toInt() }
val map = mutableMapOf<Int, MutableList<Int>>()
val ans = mutableListOf<Int>()
for(i in 1..n) {
val ai = a[i]
map.putIfAbsent(ai, mutableListOf())
if(map[ai]!!.isEmpty()) {
ans.add(-1)
map[ai]?.add(i)
continue
}
ans.add(map[ai]!!.last())
map[ai]?.add(i)
}
println(ans.joinToString(" "))
}
D - Count Simple Paths
この問題も解けず。例2を見て、連結成分ごとに考えるのかなとか思考が明後日の方向に行って帰って来られませんでした。単純にDFSで調べるだけではと思った時点でもう時間が残っておらず。
コンテスト後に落ち着いて考えたら解けました。DFSで探索しますが、移動回数が
最初はスタックを使って非再帰で書いていたのですが、探索を終えて戻った時に移動回数をデクリメントする必要があり、再帰を使うと自然とそうなるので再帰を使ったほうが楽でした。
fun main() {
val (h, w, k) = readln().split(" ").map { it.toInt() }
val s = List(h) {
readln()
}
val diffs = listOf(
-1 to 0,
1 to 0,
0 to -1,
0 to 1,
)
val set = mutableSetOf<Int>()
val graph = Array(100) { mutableListOf<Int>() }
for(i in 0 until h) {
for(j in 0 until w) {
val from = i * w + j
val c = s[i][j]
if(c == '#') {
continue
}
set.add(from)
for((di, dj) in diffs) {
val ii = i + di
val jj = j + dj
if(ii !in 0 until h) {
continue
}
if(jj !in 0 until w) {
continue
}
if(s[ii][jj] == '#') {
continue
}
val to = ii * w + jj
graph[from].add(to)
}
}
}
for(i in 0 until 100) {
if(i !in set) {
continue
}
dfs(graph, k, i, BooleanArray(100), 0)
}
println(ans)
}
var ans = 0L
fun dfs(graph: Array<MutableList<Int>>, k: Int, start: Int, seen: BooleanArray, count: Int) {
if(seen[start]) {
return
}
if(count == k) {
ans++
return
}
seen[start] = true
for(node in graph[start]) {
if(seen[node]) {
continue
}
dfs(graph, k, node, seen, count + 1)
}
seen[start] = false
}
感想
ちゃんと考えずに実装が先行して解けない、みたいなかつてやったような失敗をやらかしましたね。しばらくコンテストに参加していなかったことでそういう立ち回り方を忘れていた感じ。その一方で、ちょっと立ち回り方を忘れるだけで途端に解けなくなるくらい、素の実力がないってことでもありそう。
ちょっと思ったのが、今までやってきたのはただのパターン記憶で、アルゴリズムをちゃんと考えて実装するという基本が実はできていないのではということでした。競プロのための精進というより、そもそもそういう基礎力をちゃんと鍛えたほうが、遠回りに見えるけど一番いいのかなあ…
Discussion