🦔

AtCoder Beginner Contest 267 A～Cのメモ

2022/09/04に公開

AtCoder

競プロ

tech

NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)に参加したのでメモを残しておきます。
https://atcoder.jp/contests/abc267

A - Saturday

リストを作ってしまい、リスト内の位置から答えを求めます。ゼロオリジンなので5から引けば求まります。

fun main() {
    val list = listOf("Monday", "Tuesday", "Wednesday", "Thursday", "Friday")
    val s = readLine()!!
    println(5 - list.indexOf(s))
}

B - Split?

先頭のピンが倒れていなければ確実に答えはNoなので、その場合はさっさとガード節みたいな感じでreturnします。

文字列のまま扱うのはわかりづらいので、1列を表すColumnクラスを作っています。
Columnはピンの配列を持ち、ピンが全て倒れているか、一本でも残っているかはこのオブジェクトに訊けばわかるようにします。

あとは左から1列ずつ見ていって、

1本以上ピンが残っている列があるか・・・①
①がある場合、その右側にピンが全て倒れている列があるか・・・②
①と②がある場合、その右側にピンが残っている列があるか

を見ています。

fun main() {
    val s = readLine()!!
    if(s[0] == '1') {
        println("No")
        return
    }

    val columns = Column.of(s)
    var hasNotAllDownColumn1 = false
    var hasAllDownColumn = false
    var hasNotAllDownColumn2 = false
    for(c in columns) {
        if(!hasNotAllDownColumn1 && c.isNotAllDown()) {
            hasNotAllDownColumn1 = true
            continue
        }

        if(hasNotAllDownColumn1 && !hasAllDownColumn && c.isAllDown()) {
            hasAllDownColumn = true
            continue
        }

        if(hasNotAllDownColumn1 && hasAllDownColumn && c.isNotAllDown()) {
            println("Yes")
            return
        }
    }
    println("No")
}

data class Column(val pins: List<Char>) {
    companion object {
        fun of(s: String): List<Column> {
            return listOf(
                Column(listOf(s[6])),
                Column(listOf(s[3])),
                Column(listOf(s[7], s[1])),
                Column(listOf(s[4], s[0])),
                Column(listOf(s[8], s[2])),
                Column(listOf(s[5])),
                Column(listOf(s[9]))
            )
        }
    }

    fun isAllDown(): Boolean {
        return pins.all { it == '0' }
    }

    fun isNotAllDown(): Boolean {
        return !isAllDown()
    }
}

こういうフラグをいくつも使った実装はミスりやすいのであまり褒められたものではないですし、変数名にセンスがないし、しかもhasNotAllDownColumn2は使ってないじゃんって話なのですが、まあ通ればOKです。

C - Index × A(Continuous ver.)

これは解けませんでした。累積和を最近覚えたので、それを使うんじゃないかと思いつつ、それ以上考察は深まらず。なんか因数分解とかしようとしてました。
~~そもそもシグマ記号とか見せられて最初に思い浮かぶのはケツアゴハゲでしてねぇ…~~
~~ﾀｲﾁｮｳ！ｵｶﾗﾀﾞﾉﾎｳﾊ…~~

解説を見ても結局よくわからなかったので、全然私の手に負えない問題だったようです。

それでも解説ACはしたいので、なんとかわかったような気になって提出したのがこちら。

import kotlin.math.max

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toLong() }

    var s = a.slice(0 until m).mapIndexed { index, i -> i * (index + 1) }.sum()
    var t = a.slice(0 until m).sum()

    var ans = s
    for(i in 0 until n - m) {
        val ns = s - t + a[i + m] * m
        val nt = t - a[i] + a[i + m]
        s = ns
        t = nt
        ans = max(ans, s)
    }
    println(ans)
}

まんま解説動画で書いていたものですが…
一応、見ながら書いたわけではなく、わかったような気になったあとに何も見ずに書いたのですが、単に記憶しただけかもしれません。

やっていることとしては連続部分列の全探索ですが、前回の結果から次の結果をO(1)で求められるから速いということですね。
なので最初の「前回の結果」となるs tをループの外で求めてから、あとは1つずつずらしながら見ていきます。
sは答えの候補となる値、tは係数を掛けないただの合計で、次のsを求めるために必要になります。
ループ回数は n - m回です。nとmが等しければループに入りませんが、その場合は最初に求めたsがそのまま答えになります。

それで、ループ内でのtの更新については難しいことはありません。部分列が1つずれたことで除外された分を引いて、追加された分を足すだけです。それ以外は共通なので。

それでもって、結局わからなかったのが肝心のsの更新についてです。上記のような式を使えば次のsを求められるようでした。数学的考察によって得られた式です。これが得られる過程は解説動画で詳しく説明されているので、まともに数学ができる人なら普通にわかるのだろうと思います。私は圧倒的数学力不足によりわかりませんでしたが…

前回のsと次のsで共通部分があるので、差分だけ更新すればいいよねっていう雰囲気だけはわかったのですけどね。この辺は数学の勉強が進んだらそのうちリベンジしたいと思います。

教訓

数学をやるべし

A - Saturday

B - Split?

C - Index × A(Continuous ver.)

教訓

Discussion