💬

AtCoder Beginner Contest 355参加記

2024/05/26に公開

AtCoder

競プロ

tech

東京海上日動プログラミングコンテスト2024（AtCoder Beginner Contest 355）に参加したので記録を残します。
https://atcoder.jp/contests/abc355

今回は遅め3完です。DはAIにも訊いてみたけど解けず。

A - Who Ate the Cake?

$A$ と $B$ が同じなら特定できず、異なるなら特定できます。異なる場合は、1, 2, 3のうち入力値の中にないものが答えです。
なんか面倒だったので $A$ と $B$ を分けず、入力値を配列としてそのまま使いました。

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

    if(a.distinct().size == 2) {
        for(i in listOf(1, 2, 3)) {
            if(i !in a) {
                println(i)
                return
            }
        }
    } else {
        println(-1)
    }
}

B - Piano 2

実際に数列 $C$ を作ってから、 $C$ の中の連続する2つの数がどちらも $A$ にあるかどうかを一通り調べます。条件を満たす組み合わせが1つでもあればYesですね。
Setにしているけど別にそのままでもよかったかも。

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

    val c = (a + b).sorted()

    for(i in 0 until c.size - 1) {
        val n1 = c[i]
        val n2 = c[i+1]

        if(n1 in a && n2 in a) {
            println("Yes")
            return
        }
    }

    println("No")
}

C - Bingo 2

ちょっと悩みました。ターン数ではなく達成するかどうかだけ調べるなら、全部埋めた後に全列と全行と対角線2つを一通り見て、全て埋まっているところが1箇所でもあればいいとわかるんだけどなー、と思いました。
それから、埋める値を真偽値ではなくターン数にすればほぼ同じ発想で解けることに気づきました。任意の揃った列について、全て埋まっているならそのうちの最大値がその列におけるビンゴを達成したターン数なので、それを全部見て最小値を見つければいいですね。

実装にあたっては、宣言された $A_i$ をもとにマス目を求めるのがちょっと面倒でした。結局、マス目は2次元配列ではなく1次元配列で表現しました。そしたら $A_i$ で埋める時は特に計算しなくていいですし、 $i, j$ から位置を求める際も問題文の式の通りやればいいので。斜めは若干面倒でしたが。
各列の最大値を求めるのはTreeSetに任せました。

import java.util.TreeSet
import kotlin.math.truncate

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

    val bingo = IntArray(n * n + 1)

    for(i in a.indices) {
        val turn = i + 1
        val ai = a[i]

        bingo[ai] = turn
    }

    val sets = mutableListOf<TreeSet<Int>>()

    for(i in 1..n) {
        val treeSet = TreeSet<Int>()
        for(j in 1..n) {
            val num = n * (i - 1) + j
            if(bingo[num] == 0) {
                break
            } else {
                treeSet.add(bingo[num])
            }
        }
        if(treeSet.size == n) {
            sets.add(treeSet)
        }
    }

    for(j in 1..n) {
        val treeSet = TreeSet<Int>()
        for(i in 1..n) {
            val num = n * (i - 1) + j
            if(bingo[num] == 0) {
                break
            } else {
                treeSet.add(bingo[num])
            }
        }
        if(treeSet.size == n) {
            sets.add(treeSet)
        }
    }

    var treeSet = TreeSet<Int>()
    for(i in 1..n * n step n + 1) {
        if(bingo[i] == 0) {
            break
        } else {
            treeSet.add(bingo[i])
        }
    }
    if(treeSet.size == n) {
        sets.add(treeSet)
    }

    treeSet = TreeSet<Int>()
    for(i in n..n*n - (n - 1) step n - 1) {
        if(bingo[i] == 0) {
            break
        } else {
            treeSet.add(bingo[i])
        }
    }
    if(treeSet.size == n) {
        sets.add(treeSet)
    }

    if(sets.isEmpty()) {
        println(-1)
    } else {
        println(sets.minOfOrNull { it.last() })
    }
}

遅くないか少し心配でしたが全然問題有りませんでした。

D - Intersecting Intervals

問題文はシンプルですが全然わかりませんでした。全組み合わせを調べるのが無理というのは一応確認しましたが、それ以上は考察が進まず。
区間の苦手意識が強いのもあって早々にあきらめて、あとはAIに投げて遊んでいました。良くないですねこれは…

感想

良い結果ではないのですが、Cでけっこう（自分基準では）ややこしい計算をしているのにノーペナで通せたのが嬉しくて、意外と満足感がありました。Dは解ける気がしなかったので…

ここのところは精進できていないので、当分は問題セットの相性次第で上がったり下がったりしつつトータルでは停滞となりそうです。すごく簡単な問題を埋めるのはしていましたがさすがにそれだけでは実力はつかず。（それはそう）
結局それなりに時間を投下して現状解けない問題を解けるように解説を読み込んだりしないと実力アップできないのですが、いまいちモチベが上がらず。解説を読んでも理解できないことが多いことが続いて、そうやって解説にかじりつくことを最近しなくなっちゃいましたねぇ。時間がとれないというのもありますが。
精進のモチベは上がらないけど、コンテストには参加したいので競プロ自体のモチベはあるんですよね。精進のモチベというか、何をしたらいいのかわからなくなっているのかも。やるべきことは明らかにあるんだけど、現実的に自分の理解に落とし込めるかは別の問題で。
ひとまず、来月くらいに懸案が片付くのでそれで時間をとれるようになったら考えればいいか、くらいに思っておきます。
（執筆時間: 28分46秒）

A - Who Ate the Cake?

B - Piano 2

C - Bingo 2

D - Intersecting Intervals

感想

Discussion