💨

AtCoder Beginner Contest 321参加記（A～C）

2023/09/24に公開

AtCoder

競プロ

tech

サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）に参加したので記録を残します。
https://atcoder.jp/contests/abc321

今回は（今回も）3完です。

A - 321-like Checker

ループで判定するのは面倒なのでsortedDescending()とdistinct()で楽をしました。
降順ソートしても値が変わらない、かつ重複排除しても値が変わらないのであれば答えです。
0でもYesになっちゃいますが、0は入力されないのでセーフ。

fun main() {
    val n = readln().toInt().toString().toList()

    if(n.sortedDescending() == n && n.distinct() == n) {
        println("Yes")
    } else {
        println("No")
    }
}

B - Cutoff

スコアとしてあり得る値（0以上100以下）を全て試しました。
最高スコアと最低スコアの除外は、ソートしてから最初と最後を除いた部分で合計値を求めることで実現します。
ソートしてから最初と最後を除くのは、探索対象のスコアを配列に追加した後にやります。

import kotlin.math.min

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

    var ans = Int.MAX_VALUE
    for(i in 0 .. 100) {
        val aa = (a + listOf(i)).sorted()

        var sum = 0
        for(j in 1 until n - 1) {
            sum += aa[j]
        }

        if(sum >= x) {
            ans = min(ans, i)
        }
    }

    if(ans == Int.MAX_VALUE) {
        println(-1)
    } else {
        println(ans)
    }
}

C - 321-like Searcher

$K$ の制約が明示的には書かれていなかったので混乱しましたが、clarで $K$ が有限個であるということが補足されたのを見て悪いことを思いつきました。全部調べてベタ書きすればいいんじゃない？と。

それをやったのがこちら。無駄に長いのでリンクだけ貼ります。

こんなコードで調べました。

import java.util.stream.IntStream

fun main() {
    IntStream.rangeClosed(1, Int.MAX_VALUE)
        .parallel()
        .filter { check(it) }
        .forEach { println(it) }
}

fun check(n: Int): Boolean {
    val nn = n.toString().toList()

    if(nn == nn.sortedDescending() && nn.distinct() == nn) {
        return true
    } else {
        return false
    }
}

32ビット整数の正の値を全部調べるというめちゃくちゃなことしていますが、parallelStreamを使えばまあまあ現実的な時間で調べることができるのですよね…

これがサクッと通っていればよかったのですが、実際には上記だと「9876543210」が漏れるので通りませんでした。最終的に気づいて付け足して通りましたが、けっこう時間が経ってしまい微妙な順位となりました。

ちなみに正攻法としては、同じ数字が複数出現することはないのを利用して、bit全探索や再帰で探索するのがいいみたいでした。
たしかに、各数字を採用するかしないかを決めるだけで321-like Numberになるってことですね。頭いい…

コンテスト後にbit全探索でやってみたのがこちら。

fun main() {
    val k = readln().toInt()

    val numbers = (9 downTo 0).toList()
    val list = mutableListOf<String>()

    for (i in 1 until 1024) {
        val bits = i.toString(2).padStart(10, '0')

        val s = bits.indices.map { if (bits[it] == '1') numbers[it] else "" }.joinToString("")

        if (s != "0") {
            list.add(s)
        }
    }

    println(list.map { it.toLong() }.sorted()[k - 1])
}

bit全探索って一般的にはビット演算を使うのですが、Stringの操作でやったほうが個人的にはずっとわかりやすいことに気づいたので、今後はこうやって書こうと思います…

わかりそうでわかりませんでした。 $Ai$ を足すと $P$ を超える場合と超えない場合の境目がわかればーってところまでは考えついたのですが。

組み込みの二分探索メソッドで、目的の値が見つからなくても、それに近い値の位置がわかるんですね…

これを使えば解けそうとは思いつつ、頭動かないのでまた今度やります。

感想

まあ精進していなかったらこうなるよねという感じです。今はなかなか時間がとれないので、時間がとれるようになったら頑張りたいですね。
（執筆時間: 30分17秒）

AtCoder Beginner Contest 321参加記（A～C）

A - 321-like Checker

B - Cutoff

C - 321-like Searcher

D - Set Menu

感想

Discussion