AtCoder Beginner Contest 283 A～Dのメモ

ユニークビジョンプログラミングコンテスト2022 冬(AtCoder Beginner Contest 283)に参加したので記録を書きます。

https://atcoder.jp/contests/abc283

A - Power

累乗ですね。標準ライブラリに任せます。Doubleを経由するのはなんか怖いけど大丈夫だったみたいです。

import java.lang.Math.pow

fun readString() = readLine()!!
fun readStrings() = readString().split(" ")
fun readInts() = readStrings().map { it.toInt() }

fun main() {
    val (a, b) = readInts()
    println(pow(a.toDouble(), b.toDouble()).toInt())
}

実はこれだと「JavaのじゃなくてKotlinの関数を使えや」ってIntelliJに怒られたのですが、急いでたので無視しました。

B - First Query Problem

これはいわゆる「やるだけ」ですね。
C問題のこういう系統の問題だと、愚直にやるとTLEになるような操作がクエリの中に含まれていたりするのですが、この問題だとどの操作も定数時間なのでそのままやるだけです。

import java.io.PrintWriter

fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine()!!.toInt()
    val a = br.readLine()!!.split(" ").map { it.toInt() }.toMutableList()
    val q = br.readLine()!!.toInt()

    val out = PrintWriter(System.out)
    repeat(q) {
        val query = br.readLine()!!.split(" ").map { it.toInt() }

        if(query[0] == 1) {
            val (_, k, x) = query

            a[k-1] = x
        } else {
            val (_, k) = query
            out.println(a[k-1])
        }
    }
    out.flush()
}

一応、入出力の高速化だけは考慮しています。やらなくてもギリギリ大丈夫な気もするんですが一応。

C - Cash Register

少し読解に時間がかかってしまったのですが、要するにボタン 00 を押した時だけ2桁増えて、それ以外のボタンを押した時は1桁増えます。

これは操作が終わった後の値が与えられるので、それを0に戻す操作をシミュレーションすると考えました。
注意が必要なのは00がある場合で、その場合は2桁まとめて1回でカウントします。

import kotlin.math.sign

fun main() {
    val s = readLine()!!.map { it - '0' }.toMutableList()

    var ans = 0
    var skip = false
    for(i in (s.size-1) downTo 0) {
        if(skip) {
            skip = false
            continue
        }

        if(s[i] != 0) {
            ans++
            continue
        }

        if(i != 0 && s[i-1] == 0) {
            ans++
            skip = true
        } else {
            ans++
        }
    }
    println(ans)
}

公式解説みたいに実際に削除していく実装のほうが綺麗なコードでしたね。

D - Scope

これは残念ながら解けなかったです。
良い文字列とは要するにカッコ()のセットがちゃんと揃っている文字列ということですね。なので、要するに)が出現したら直近の(までの文字列を消すことができるということです。
そこまでは理解したのですが、それを現実的な計算時間で処理するにはどうしたらいいのかという点で詰まりました。
「)が出現したら直近の(までの文字列を消す」という操作はどうしてもその長さに対して線形の処理時間がかかるため、それが何度も実行されたら間に合わないと思ったのです。

実際には、線形の処理時間といってもせいぜい()の間の長さの分だけなので、愚直に実装しても普通に間に合うようでした。うーんそれに気づけていれば…

import java.util.ArrayDeque

fun main() {
    val s = readLine()!!

    val stack = ArrayDeque<Char>()

    val set = mutableSetOf<Char>()

    for(c in s) {
        if(c in set) {
            println("No")
            return
        }

        if(c == ')') {
            do {
                val popped = stack.removeLast()
                set.remove(popped)
            } while (popped != '(')
        } else {
            if(c != '(') {
                set.add(c)
            }
            stack.add(c)
        }
    }
    println("Yes")
}

箱に出し入れする操作はそのままスタックで表現できます。アルファベットの場合は存在確認をしますが、スタックに対して存在確認を毎回行うとさすがに間に合わないので、存在確認を高速に行うために補助的にSetを利用します。

敗因としては、まずは計算量を正しく見積もれなかったことです。D問題でまさか愚直にやればOKなんて思いもしなかったです…

あとは、)が出現した時に直近の(までを削除する操作をどうやって高速に実行するか？に囚われていたことですね。なんかいい感じに高速に処理する方法はないのかみたいな、なんか思考放棄に等しい感じになっていて上記のシンプルな解法も思いつきませんでした。通るかはさておき愚直にやる場合はどうやればいいのか？と考えていれば思いついたかもしれませんし、そうしていれば、実は間に合うのでは？って発想になったかもしれません。

通るかはさておき愚直にやる場合はどうやればいいのか？っていうのは以前は考えていたのですが、最近はあまりそのように考えずになんかスマートな方法ないかなって思考になっていました。これは良くないですね。
愚直にやった場合はどうなるのか？それだと問題なのか？なぜ問題なのか？ならばどうすればいいのか？とちゃんと段階を踏んで考えないといけないと感じました。