🐙

AtCoder Beginner Contest 352参加記

2024/05/05に公開

AtCoder

競プロ

tech

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

今回は3完です。

A - AtCoder Line

明示的に場合分けするとバグらせそうな気がしてちょっと嫌だったので、 $X$ と $Y$ の大小関係にかかわらずとにかく区間を作って、 $Z$ がそれに含まれるかどうかで判定しました。

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

fun main() {
    val (n, x, y, z) = readln().split(" ").map { it.toInt() }

    val list = (min(x, y)..max(x, y))
    if(z in list) {
        println("Yes")
    } else {
        println("No")
    }
}

この時、listはIntRange型になっています。

B - Typing

添字2つを扱うとバグらせそうな気がしてちょっと嫌だったので、 $T$ のうちチェック済で不要となった箇所を消しながら、 $S$ の各文字が最初に出現した位置を記録していくようにしました。
これはこれでバグらせそうな変な実装なので、何やってるのか意味不明ですね。しかしノーペナでいけてよかった…

fun main() {
    val s = readln()
    val inT = readln()

    val ans = mutableListOf<Int>()

    var t = StringBuilder(inT)
    var diff = 0
    for(i in s.indices) {
        val index = t.indexOfFirst { it == s[i] }
        ans.add(index + 1 + diff)

        t = t.deleteRange(0, index + 1)
        diff += index + 1
    }

    println(ans.joinToString(" "))
}

C - Standing On The Shoulders

~~駆逐してやる~~

サンプルから、頭の高さと肩の高さの差が小さいほうから積み上げていけばいいと思ってそのようにしました。高さは基本的に肩の高さの合計ですが、最後だけは頭の高さを足します。

実際には、一番上の巨人さえ合っていればあとは何でもいいのですが。

fun main() {
    val n = readln().toInt()
    val titans = List(n) {
        val (a, b) = readln().split(" ").map { it.toLong() }
        Titan(a, b, b - a)
    }
        .sortedBy { it.diff }

    var sum = titans.sumOf { it.a }
    sum = sum - titans.last().a + titans.last().b

    println(sum)
}

data class Titan(
    val a: Long,
    val b: Long,
    val diff: Long,
)

クラス名をGiantにするとTitanにするかというしょうもないことでちょっと迷いました。

D - Permutation Subsequence

全然わかりませんでした。これは数学的な考察というより、データ構造で殴る系統ではないかという気はしたのですが。

解説を見たところ、各数値の出現位置を記録して、 $K$ 個要素を持つ範囲を全部見て、各範囲の最大値と最小値の差を求めていけばいいということでした。

各数値の出現位置を記録すること自体は考えていたので、なぜあともう一歩考えが進まなかったのかと悔しいですね…

KotlinやJavaだとTreeSetが使えます。

import java.util.TreeSet
import kotlin.math.min

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

    val pos = IntArray(n)
    for(i in p.indices) {
        pos[p[i]-1] = i
    }

    val treeSet = TreeSet<Int>()
    for(i in 0 until k) {
        treeSet.add(pos[i])
    }

    var ans = treeSet.last() - treeSet.first()

    for(i in 0 until n) {
        if(i + k == n) {
            break
        }

        treeSet.remove(pos[i])
        treeSet.add(pos[i+k])

        ans = min(ans, treeSet.last() - treeSet.first())
    }

    println(ans)
}

TreeSet使えば解けるのに気づかない、というパターンがけっこう多いですね…

感想

コンテスト中はDが解ける気がしなかったですが、蓋を開けてみたらむしろ解けないといけないような問題だったと感じたので非常に悔しいですね。
こういう結果になると、どうすれば解けていたのだろうと考えてはみますが、なかなかこれだという答えが見つかりません。
仮に解ける可能性があったとしたら、各数値の出現位置を記録することを考えるだけでなくて、それを紙に書き出して眺めるみたいなことをしていれば気付いた可能性がありますね。まあ、「可能性がある」程度なので、十分高い確率で再現させる自信がないですけどね。典型を覚えるとか、実装の練習をするとかも必要なのですが、こういった考察のやり方ももっとうまくなりたいですねぇ。
（執筆時間: 46分54秒）

A - AtCoder Line

B - Typing

C - Standing On The Shoulders

D - Permutation Subsequence

感想

Discussion