💨

AtCoder Beginner Contest 347参加記

2024/03/31に公開

AtCoder

競プロ

tech

AtCoder Beginner Contest 347に参加したので記録を残します。
https://atcoder.jp/contests/abc347

微妙に調子悪くてスキップしようかと思っていたのに直前に気が変わって参加しました。
2完で残念でしたが、Cが難しかったのかレートは守られました。

A - Divisible

filterしてmapしてjoinです。
このレベルの問題ならもう20秒くらい早く提出したかったな。

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

    println(a.filter { it % k == 0  }.map { it / k }.joinToString(" "))
}

B - Substring

問題文の通りsubstringします。最大100文字しかないので単純に全探索で問題なし。
jはiから始めればよかったのですが、わざわざ0から始めたあとにiより小さかったらスキップとかしています。ちょっと慌ててましたね。
substringは半開区間[i, j)なので+1が必要です。

fun main() {
    val s = readln()

    val set = mutableSetOf<String>()

    for(i in s.indices) {
        for(j in s.indices) {
            if(j < i) {
                continue
            }

            set.add(s.substring(i, j + 1))
        }
    }
    println(set.size)
}

C - Ideal Holidays

解けませんでした。
今日としてあり得る曜日の範囲が広すぎるので全探索はできず、 $D_i$ のほうの探索でなんとかする必要があります。各予定の日が休日であるためにあり得る曜日の範囲をそれぞれ求めて、全てに共通区間があればOKとすればいいと思って実装しました。しかし通らず。循環するという観点で何か考慮漏れがあるのか、もしくは凡ミスがあるのかわかりませんが。

import kotlin.math.max
import kotlin.math.min

val empty = 0L to 0L

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

    // 1週目
    val list = mutableListOf<Pair<Long, Long>>()
    for(i in 0 until n){
        val dest = max(0, a - d[i])
        if(dest == 0L) {
            list.clear()
            break
        }

        list.add(1L to dest)
    }
    if(list.isNotEmpty() && list.reduce { acc, pair -> overlap(acc, pair) } != empty) {
        println("Yes")
        return
    }

    // 2週目
    list.clear()
    val days = a.toLong() + b.toLong()
    val start = days + 1
    val end = days + a
    val first = d.first()
    var current = start - first to end - first

    for(i in 1 until n) {
        val next = correction(start - d[i] to end - d[i], days)
        val o = overlap(current, next)
        if(o == empty) {
            println("No")
            return
        }
        current = o
    }

    println("Yes")
}

fun correction(p: Pair<Long, Long>, days: Long): Pair<Long, Long> {
    return if(p.first < 1) {
        p.first + days to p.second + days
    } else {
        p
    }
}

fun overlap(p1: Pair<Long, Long>, p2: Pair<Long, Long>): Pair<Long, Long> {
    if(p1 == p2) {
        return p1
    }

    val (a, b) = p1
    val (c, d) = p2
    return if(c <= b && a <= d) {
        max(a, c) to min(b, d)
    } else {
        empty
    }
}

そのうちupsolveするかも。ちょっと頭が動かないのでまた今度。

感想

2完でダメかと思いましたが早解きに救われました。今回のCは調子良くても解けなかった気がします。微妙に調子悪いといっても、普通に実力通りの結果になった印象。精進できてなくて強くなってないですが、弱くもなってないのでまあまあ焦らずにいきます。
（執筆時間: 17分49秒）

A - Divisible

B - Substring

C - Ideal Holidays

感想

Discussion