🌊

AtCoder Beginner Contest 281 A～Dのメモ

2022/12/11に公開

AtCoder

競プロ

tech

AtCoder Beginner Contest 281に参加したので記録を残しておきます。
https://atcoder.jp/contests/abc281

A - Count Down

問題文の通りです。なお今回から簡単な問題向けにテンプレコードを貼って対応してみました。

fun readInt() = readString().toInt()

fun main() {
    val n = readInt()
    for(i in n downTo 0) {
        println(i)
    }
}

B - Sandwich Number

問題文の通り愚直に実装しました。ガード節のように一致しないものは除外していく感じでやっています。

fun readString() = readLine()!!

fun main() {
    val s = readString()

    if(s.length != 8) {
        println("No")
        return
    }

    if(!s[0].isUpperCase()) {
        println("No")
        return
    }

    val maybeNum = s.substring(1, 7)
    if(!isNumber(maybeNum) || maybeNum.toInt().toString().length != 6) {
        println("No")
        return
    }

    if(!s.last().isUpperCase()) {
        println("No")
        return
    }

    println("Yes")
}

fun isNumber(s: String): Boolean {
    try {
        s.toInt()
    } catch (e: Exception) {
        return false
    }
    return true
}

正規表現使えば一発じゃんとコンテスト後に気づきました。ただ、Kotlinでこうやって正規表現を使ったことがなかったので、微妙にバグらせて逆に時間かかった可能性もありますので、まあいいか…

fun main() {
    val s = readLine()!!
    if(s.matches(Regex("^[A-Z][1-9]\\d{5}[A-Z]$"))) {
        println("Yes")
    } else {
        println("No")
    }
}

C - Circular Playlist

愚直に考えると、Aの各要素をTからどんどん引いていって0以下になったらその時の曲が答えになります。該当の曲の引いた後の値（0以下の値）をAに足せば秒数が求まります。

ただTの制約が大きいので、単純にそれを実行すると残り秒数が0以下にならない可能性があります。その場合はもう一周すればいいのかというと、それだと計算量が大きくてTLEになる可能性があります。

結論としては、Aの合計値でTを割った余りで上記を実行すればいいです。上記を実行していくと、結局それと同じことになります。余りを求めることでショートカットでき、現実的な時間で処理できるようになります。

余りもそれなりに大きな数になる可能性はあり、それに対して線形時間かかりますが、一周未満なのはたしかなので線形時間なら十分間に合います。

fun main() {
    val (n, t) = readLine()!!.split(" ").map { it.toLong() }
    val aList = readLine()!!.split(" ").map { it.toInt() }
    val aSum = aList.map { it.toLong() }.sum()

    val mod = t % aSum

    var rest = mod
    for(i in aList.indices) {
        val a = aList[i]
        rest -= a
        if(rest <= 0) {
            println("${i+1} ${a + rest}")
            return
        }
    }
}

Aの合計値とTはLongで扱う必要があります。割った余りは確実にAの合計値未満なので、引き算が一巡しても0以下にならないということはありません。

D - Max Multiple

これは全然わかりませんでした。解説によると3次元のDPで解けるということでしたが、3次元は扱ったことがないためかなかなか理解に至らず…

そもそもコンテスト中にわかったのは実際に集合Sを作るのは無理ってところまでで、DPを使えば解けるのではと発想することもできませんでした。厳しいですね。

とりあえず解説内容の理解を試みます。（※途中で挫折しています）

i個中j個選んだ場合、その総和をDで割った余りをkとした3次元データで、その総和を保持します。DPの基本として、いきなり最終的な答えを求めるのではなく問題を一般化して段階的に解いていきます。次の段階に進む時に前の段階の値を使い回せるので計算量が削減できるという感じですね。データの持ち方と埋め方（埋めるのに使う値、次の段階に進むための遷移式）が決まったらそれに従って埋めていって、最後に目当ての位置にある値を取り出せばOKです。
これはDPの基本についてのおさらいですが、なんかその辺りから怪しいので書いています…ｗ

この問題の話に入っていきますが、DPテーブルは全て-1で初期化します。また、0個中0個選んだ場合は総和も0で、割った余りも確実に0なので、まずは dp[0][0][0] = 0 と埋めることができます。

解説では配るDPとして実装しています。つまり、既に埋まった行（行？3次元だとなんて言う…？）を走査して、埋まっていた場合はそれをもとに次の値を求めます。埋まっていない場合（-1の場合）はその選択パターンでその余りに到達することがないので、それ以上の計算は不要ということになります。埋まっている場合はその余りに到達する場合があるので、もう一つ選択する数を増やして計算をします。

そういう意味ですと、 dp[0][0] の場合は dp[0][0][0] = 0 以外には埋められる位置が存在し得ないというのもポイントですね。0個中0個選んだ状態なので、Dがどのような数にせよ割った余りが0以外になることはありません。それにより、 dp[0][0] は完全に埋まった行として走査可能になります。

ただ、埋まっている場合に次の値を求めるところが難しくていまいち理解に至っていないです。走査する行は完全に埋まっていなければならないため、選ばない場合でも次の計算のために引き継いでおく必要があり、それが選ばない場合の遷移です。既に埋まっている場合も考慮してmaxをとるというのもわかります。
選ぶ場合の遷移ですが、解説だと dp[i+1][j+1][(k+a[i])%D] に設定しています。そもそも次のiに値を配るためなのでi+1は当然です。選ぶので、j+1も当然。 (k+a[i])%D ですが、これは選んだ値の総和をDで割った余りなので (dp[i][j][k]+a[i])%Dということだと思います。余りは随時とっても同じ結果になるので、同じ意味のはず…
埋める値ですが、基本は dp[i][j][k]+a[i] ですが、既に埋まっていることも考慮してmaxをとっているという感じですね。

そんな感じで、何をやっているのかはわかったと思うのですが、なんでこれでいいのかがわかりません。根本的なところがわかっていない感…

ちょっと今日はこのあたりで限界が来たので解説ACは一旦とっておきます。

感想

今回のCは前回ほどではないにせよ簡単なほうだったので、解けたからすごく嬉しいってほどではないのですが、私の基準からすると早めに解けてレーティングも少し上がったので、まあまあ良かったのかもしれません。

Dについては私よりもはるかに強い人でも解けてなかったりしたようなので、解けなかったのはまあ仕方ないです。解説を見ても十分には理解できないのも仕方ないですが、DPについてちゃんと勉強・練習すれば理解できそうではあるんですよね。ということで、しばらくはDPの練習をしようと思いました。
DPについては以前勉強して一旦一区切りつけたつもりでしたが、これはDPで解けるかもって思うことすらなかったので、とても十分とは言えないですね。なので、もうちょっとやりますｗ

A - Count Down

B - Sandwich Number

C - Circular Playlist

D - Max Multiple

感想

Discussion