😺

AtCoder Beginner Contest 346参加記

2024/03/24に公開

AtCoder

競プロ

tech

ユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）に参加したので記録を残します。
https://atcoder.jp/contests/abc346

今回は3完です。遅いので負け。

A - Adjacent Product

$N - 1$ 回ループを回して前後の値の積を出力します。
無意味にLongにしました。

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

    val list = mutableListOf<Long>()
    for(i in 0 until n - 1) {
        list.add(a[i] * a[i+1])
    }

    println(list.joinToString(" "))
}

B - Piano

全探索して問題ないくらいの大きさの文字列を作ってしまって $W + B$ 個の範囲の中を全探索、を最後まで繰り返します。
substring()の際にはみ出てしまってREを出しました。残念…

import kotlin.math.min

fun main() {
    val (w, b) = readln().split(" ").map { it.toInt() }
    val s = "wbwbwwbwbwbw".repeat(100000)

    val size = w + b

    for(i in s.indices step size) {
        val sub = s.substring(i, min(s.length, i + size))
        val wc = sub.count { it == 'w' }
        val bc = sub.count { it == 'b' }

        if(wc == w && bc == b) {
            println("Yes")
            return
        }
    }

    println("No")
}

C - Σ

最初は1度も現れないものの総和を実際に求めようとしました。もちろん1から $K$ の全探索だと間に合わないんですが、 $A$ をソートしてから一つ一つ見ていけば隣り合う要素の間の数が現れない数なので総和を求めていけるだろうと。総和を求めるのは計算で $O(1)$ でできるので。
その場合、1から $A$ の最小値 - 1までの合計を求めるなども必要ですが、最小値が1だった場合の分岐を考える必要があるなど面倒でした。それを書いているうちに、1から $K$ までの総和を求めてから $A$ に登場する数を引いていけばもっと簡単じゃないかと気づきました。 $A$ は重複は排除する必要があるのと、 $K$ を超える数は引かないなどの考慮は必要です。
気づいたのはいいのですが、如何せん気づくのが遅かったです。

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

    var ans = sum(1, k)

    for(i in a.indices) {
        if(a[i] <= k) {
            ans -= a[i]
        }
    }

    println(ans)
}

fun sum(start: Long, end: Long): Long {
    return if((start + end - 1) % 2 == 0L) {
        (start + end) * ((end - start + 1) / 2)
    } else {
        val dEnd = end - 1
        (start + dEnd) * ((dEnd - start + 1) / 2) + end
    }
}

D - Gomamayo Sequence

DPが見えました。dp[i][j]でiが何文字目か、jが0か1という感じでコストを管理するのかなと思ったのですが、これだけだと解けません。i文字目を置き換えると決めた時、それによって同じ文字が連続するようになるのであればそれより後は連続する文字が出現しないようにする必要がありますし、置き換えで連続する文字でなくなるのであれば逆の判断が必要になります。どういう情報を持たせればそれが実現できるかわからなかったですが、いずれにしても判断のための何らかの情報を追加する必要があります。つまり3次元DPになるだろうと… うん、それ無理。
ということで解けませんでした。

解説を見るとやはり3次元DPで解法もありましたが、それ以外の解法もあったようです。余裕があればどちらも理解したいですが、まあ最低限どちらか片方でも理解したいですねぇ。

感想

Dは完全に実力が及ばない問題だったので解けなくてもしょうがなかったですね。Cの解法に気づくのが遅れたのが今回のやらかしです。最初に思いついた解法でも面倒とはいえ一応合ってたはずであることから、他にもっと良い解法はないかと考えずに突っ切ろうとしたのが問題でしたね。
配点を見ていなかったですが250点と少し軽めだったので、250点問題がこんな面倒な解法を要求するとは考えづらい、みたいなメタ読みをすればよかったのかなあ…
まあ、そんなことしなくてもパッと思いつくべきだったのでしょうけど。こういうのをパッと思いつけるほどの地力はまだないんですねぇ。悲しみ。地道に問題を解いていくしかないか。
（執筆時間: 24分16秒）

A - Adjacent Product

B - Piano

C - Σ

D - Gomamayo Sequence

感想

Discussion