🐷

AtCoder Beginner Contest 353参加記

2024/05/12に公開

AtCoder

競プロ

tech

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

今回は2完です。連敗中…

A - Buildings

最初の要素より大きい要素を探します。indexOfFirstは要素がなければ-1が返ります。

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

    val f = h.first()

    val ans = h.indexOfFirst { it > f }

    if(ans > 0) {
        println(ans +1 )
    } else {
        println(-1)
    }
}

B - AtCoder Amusement Park

なんかちょっと手間取りました。結局、空席数を管理しながらシミュレーションするだけでした。この実装だと乗れない場合にだけアトラクションをスタートさせているので、ループを抜けた後にもう一回スタートする必要があるので最後に+1です。

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

    var ans = 0
    var sheet = k
    for(i in a.indices) {
        if(sheet - a[i] < 0) {
            ans++
            sheet = k
        }
        sheet -= a[i]
    }

    println(ans + 1)
}

C - Sigma Problem

これは解けませんでした。シグマ記号に慣れないですが、要するに数列のうち重複なしで2つを選んだ場合の数ですね。愚直にやると $_NC_2$ で、概ね $N^2$ 通りなので間に合いません。

まず、 $i$ を固定して考えました。 $i$ が1の場合は、あまりをとるのを無視すれば $A$ の総和に $A_1 \times (N - 2)$ を足せば求められます。例1では $(3 + 50000001) + (3 + 50000002)$ ですが、これは $(3 + 50000001 + 50000002) + 3$ と同じです。 $i$ が2なら $A$ の総和から $A_1$ を引き、それに $A_2 \times (N - 3)$ を足します。
それに対してあまりをとるだけならそれでよかったのですが、どうもそうはいかないらしい。あまりをとるのは総和に対してではなく、あくまでも $A_i + A_j$ の和に対してということで…

しばらく悩んだのですが、要するに問題となるのは $A_i + A_j$ が $10^8$ 以上になるケースが存在する場合だけです。それがなければあまりをとらずに足すだけなのですがー
それをなんとかする方法さえあればと考えていって、最終的にはそのような組み合わせの個数をカウントして、それ × $10^8$ を総和から引けばいいと気づきました。
$A_i$ の制約は $1\leqA_i<10^8$ となっているので、 $A_i + A_j$ を $10^8$ で割ったあまりとは、 $A_i + A_j$ が $10^8$ 以上になる場合は $10^8$ で引くのと同じだからです。これにもっと早く気づいていれば…

$A_i + A_j$ が $10^8$ 以上になる組み合わせの個数をどうやって求めたらいいのかも悩みましたが、これは $A$ をソートして二分探索すればよかったです。これに気づくのにも時間がかかりました。 $10^8 - A_i$ 以上かどうかという判定問題で探索すればOK。重複する組み合わせを探索しないように、探索範囲は順次狭めます。

$A$ はソートして問題ないというのも結局コンテスト中に気づかなかったですね…
重複なしで選んだ組み合わせで、 $A_i + A_j$ も $A_j + A_i$ も変わらないので順番が変わっても問題ないのですね…

import kotlin.math.abs

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

    val mod = 100000000L

    var ans = 0L
    var total = a.sum()

    var count = 0L
    for(i in 0 until n-1) {
        val c = mod - a[i]
        val index = binarySearch(i.toLong(), n.toLong()) { a[it.toInt()] >= c }

        val p = if(index == n.toLong()) {
            0
        } else {
            abs(index - n)
        }

        count += p

        val multiply = a[i] * (n - i - 2)

        ans += (total + multiply)
        total -= a[i]
    }

    println(ans - count * mod)
}

fun binarySearch(minNg: Long, maxOk: Long, isOk: (Long) -> Boolean): Long {
    var ng = minNg
    var ok = maxOk

    while(abs(ok - ng) > 1) {
        val mid = (ok + ng) / 2
        if(isOk(mid)) {
            ok = mid
        } else {
            ng = mid
        }
    }
    return ok
}

解けなかったので悲しいけど、面白い問題とは思いました。

感想

ちょっと精進できてないだけで衰えすぎではとだいぶ驚きました。Cは難しいといえばそうだけど解けないほどではなかったはずですし、そもそもAとかBでも手間取っているし…
以前は精進できていないしーと言いつつも、なんだかんだ1日1問くらいは解いていて、それも難しい問題ではなく比較的すんなり解けるような問題だったりしたのですが、それが意外と効果があったんだろうなと思いました。今はそれすらできていない結果がこれなので。
なぜ直近1日1問も解けていないかというと、時間の問題もあるのですが、これまでABCの過去問で解けそうな問題を解いてきた結果既にけっこう埋まってきていて、めぼしい問題がないなーと思って手が止まっていました。しかし、それなら以前解いた問題を解き直すとか、もしくはAtCoderにこだわらずPaizaとかこどふぉとかの問題を解けばいいのでは…って思いました。
なので今日からはしばらくそんな感じで、なんでもいいので1問解くようにしていこうかなと思います。
連敗中ですが、まあそのうちなんとかなります。
（執筆時間: 39分20秒）

A - Buildings

B - AtCoder Amusement Park

C - Sigma Problem

感想

Discussion