AtCoder Beginner Contest 285 A～Cのメモ

AtCoder Beginner Contest 285（ABC285）に参加したので記録を残します。
https://atcoder.jp/contests/abc285

A - Edge Checker 2

これグラフを探索しないといけないのか？とちょっと悩みましたが、$b$は$2a$または$2a+1$という法則が見えたのでそれで計算しました。

$a < b$という法則があることはちゃんと確認しました。

fun main() {
    val (a, b) = readLine()!!.split(" ").map { it.toInt() }

    if(a * 2 == b || a * 2 + 1 == b) {
        println("Yes")
    } else {
        println("No")
    }
}

B - Longest Uncommon Prefix

愚直も愚直な実装をしたところTLEになりました…
厳しいと思って一旦捨ててCに行き、Cが解けたので戻ってきて解きました。

まずTLE解法です。

3重ループでダメでした。

fun main() {
    val n = readLine()!!.toInt()
    val s = "." + readLine()!!

    for(i in 1 until n) {
        var ans = 0
        for(l in 1 until n) {
            if(i + l > n) {
                break
            }

            var flg = true
            for(k in 1..l) {
                if(s[k] == s[k+i]) {
                    flg = false
                    break
                }
            }
            if(flg) {
                ans = l
            }
        }
        println(ans)
    }
}

$l$を全部列挙して、それぞれについて$1 <= k$を探索するのは完全に無駄な探索と気づいて$l$のループを消してACです。

import java.io.PrintWriter

fun main() {
    val n = readLine()!!.toInt()
    val s = "." + readLine()!!

    val out = PrintWriter(System.out)
    for(i in 1 until n) {
        var ans = 0
        for(k in 1..n) {
            if(i + k > n) {
                break
            }

            if(s[k] != s[k+i]) {
                ans++
            } else {
                break
            }
        }
        out.println(ans)
    }
    out.flush()
}

C - abc285_brutmhyhiizp

$10 ^ {16}$問も解かされるのか…というか作問するのか。大変そう。
それはさておき、これは要するに26進数だなとすぐに気づきました。
まあ「すぐに」は嘘ですが、とにかく気づきました。

N進数を10進数に変換する一般的な計算を26進数に対して行なっています。
Aは文字コードとしては65なので、A～Zは1～26として扱います。一般的な26進数は0～25なので、その点は少し違います。
下の桁からなので文字列を逆順にして見ています。

import kotlin.math.pow

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

    var ans = 0L
    var i = 0
    for(c in s.reversed()) {
        val num = c.toInt() - 64
        ans += 26.toDouble().pow(i.toDouble()).toLong() * num
        i++
    }
    println(ans)
}

D - Change Usernames

グラフっぽいと思ったり、いやそれとは違う解法で解けるかも、とか思ったり迷走していたら時間がなくなりました。
悔しいので後で解きます。

感想

Dが解けなかったのは残念ですが、それ以上に残念なのはBですね。TLEは全然思いもよらなかったのではなく、これ厳しくない？と思いつつお祈り提出してしまったんですよね。
計算量を見積もれよと、何度同じミスを繰り返すんだという点でガックリしました。
まあ、コンテスト中の時間が刻一刻となくなっていく状況に未だに慣れていないのかもですね。
今回のミスは忘れないようにします。

（執筆時間：15分52秒）