AtCoder Beginner Contest 379参加記

トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)に参加したので記録を残します。
https://atcoder.jp/contests/abc379

2完です。Cが難しい。

A - Cyclic

文字列にしてから実際に入れ替えて出力しました。
見た目やばいコードに…

fun main() {
    val n = readln().toInt().toString()
    println("${n[1]}${n[2]}${n[0]} ${n[2]}${n[0]}${n[1]}")
}

https://atcoder.jp/contests/abc379/submissions/59564126

B - Strawberries

二重ループで調べました。しかし、今思えばindexOf()とか使えばもっと楽でしたね。

fun main() {
    val (n, k) = readln().split(" ").map { it.toInt() }
    val s = readln().toCharArray()

    var ans = 0

    for(i in s.indices) {
        var ok = true
        for(j in 0 until k) {
            if(i + j >= n) {
                ok = false
                break
            }

            if(s[i+j] == 'X') {
                ok = false
                break
            } else {
                s[i+j] = 'X'
            }
        }
        if(ok) {
            ans++
        }
    }
    println(ans)
}

https://atcoder.jp/contests/abc379/submissions/59570245

C - Sowing Stones

これは解けませんでした。

まずは石がある位置を起点に考えて、そこから隣接する石がないマスに石を移動する回数を調べるようにしました。石を移動するのに必要な回数は計算で求められます。実験した結果、石が$N$個あるマスから隣接する$(N - 1)$マスに石を移動するのに必要な回数は以下で求められました。

fun sumOfRange(n: Long): Long {
    val half = n / 2
    val diff = if(n % 2 == 0L) {
        0
    } else {
        half + 1
    }

    return (1 + n) * half + diff
}

それで以下のコードを提出したのですが…

fun main() {
    val (n, m) = readln().split(" ").map { it.toLong() }
    val x = readln().split(" ").map { it.toLong() }
    val a = readln().split(" ").map { it.toLong() }

    if(a.sum() != n.toLong()) {
        println(-1)
        return
    }

    val data = x.zip(a).map { Data(it.first, it.second) }
        .sortedBy { it.i }

    var ans = 0L

    var right: Long
    for(i in data.indices) {
        val xi = data[i].i
        val ai = data[i].count

        if(i.toLong() == m - 1) {
            right = n
        } else {
            right = data[i+1].i - 1

            if(right == xi) {
                if(ai == 1L) {
                    continue
                } else {
                    println(-1)
                    return
                }
            }
        }

        val rest = right - xi
        if(ai - 1 != rest) {
            println(-1)
            return
        }

        ans += sumOfRange(ai - 1)
    }
    println(ans)
}

data class Data(
    val i: Long,
    val count: Long,
)

fun sumOfRange(n: Long): Long {
    val half = n / 2
    val diff = if(n % 2 == 0L) {
        0
    } else {
        half + 1
    }

    return (1 + n) * half + diff
}

https://atcoder.jp/contests/abc379/submissions/59594399

ダメでした。

実装ミスも疑いましたが、そもそもこれだと、石の個数を$X$とすると、石があるマスの右側に石がないマスが連続して$(X - 1)$個ある場合しか考慮できてません。

たとえば以下のようなケースではダメそうでした。

10 4
1 4 7 10
3 4 2 1

それに気づいたのは終了10分前くらいだったのでそのまま解けず。

D - Home Garden

Cを考えていたら時間がなくなったのであまり見ていません。ただ、ざっと考えた程度だと解法は思い浮かびませんでした。

感想

Cは普通に難しかったようなのでしょうがないですね。Bで謎に詰まったりしなくてよかったということで。