🙌

AtCoder Beginner Contest 264の総括

2022/08/14に公開

freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）に出場して、振るわなかったので反省記事を書いておきます。
（今のところABCが満足できる結果で終わったことは一度もないのですが…ｗ）
https://atcoder.jp/contests/abc264

B - Nice Grid

Aは特に書くことがないので省略します。

Bは一応ACだったのですがけっこう時間をとられてしまいました。
提出コードはこちら。

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

    if(r == 1 || r == 15 || c == 1 || c == 15) {
        println("black")
        return
    }
    if(((r == 3 || r == 13) && c != 2 && c != 14) || ((c == 3 || c == 13) && r != 2 && r != 14)) {
        println("black")
        return
    }
    if((((r == 5 || r == 11) && c != 2 && c != 14) && c != 4 && c != 12)
        || ((c == 5 || c == 11) && r != 2 && r != 14) && r != 4 && r != 12) {
        println("black")
        return
    }
    if(((((r == 7 || r == 9) && c != 2 && c != 14) && c != 4 && c != 12) && c != 6 && c != 10)
        || (((c == 7 || c == 9) && r != 2 && r != 14) && r != 4 && r != 12) && r != 6 && r != 10) {
        println("black")
        return
    }

    println("white")
}

ヤバいですね。これをよくバグらせずに済んだものです。運が良かったですね…
Twitterを見ていると、グリッドの状態を表す配列を決め打ちで作ってそれをもとに求めるというやり方をとった人が多かったようです。私もそうすればよかったですが、思いつきもしませんでした。頭が固すぎるんですね…
計算が苦手なのに計算で求めようとしてしまったのが敗因なので、現時点ではいかに計算せずに実装できるかを考えたほうがよさそうです。

C - Matrix Reducing

これはコンテスト中には提出ができませんでした。コンテスト終了後にTwitterで見た「bit全探索」というキーワードをもとに解説を（ほぼ）見ずに再度実装をやってみました。
実装ミスでグダりつつも最終的には通せたのでうれしかったです。
提出コードはこちら。

fun main() {
    val (h1, w1) = readLine()!!.split(" ").map { it.toInt() }
    val a = (0 until h1).map {
        readLine()!!.split(" ").map { it.toInt() }.toMutableList()
    }

    val (h2, w2) = readLine()!!.split(" ").map { it.toInt() }
    val b = (0 until h2).map {
        readLine()!!.split(" ").map { it.toInt() }
    }

    val hDelFlags = mutableListOf<String>()
    val wDelFlags = mutableListOf<String>()
    for(i in 0 until 1.shl(h1)) {
        val hFlag = Integer.toBinaryString(i).padStart(h1, '0')
        if(hFlag.filter { it == '1' }.length == h1 - h2) {
            hDelFlags.add(hFlag)
        }
    }
    for(j in 0 until 1.shl(w1)) {
        val wFlag = Integer.toBinaryString(j).padStart(w1, '0')
        if(wFlag.filter { it == '1' }.length == w1 - w2) {
            wDelFlags.add(wFlag)
        }
    }

    for(hFlag in hDelFlags) {
        val copyA = a.map { it.toMutableList() }.toMutableList()
        for(i in hFlag.indices.reversed()) {
            if(hFlag[i] == '1') {
                copyA.removeAt(i)
            }
        }

        for(wFlag in wDelFlags) {
            val copyA2 = copyA.map { it.toMutableList() }.toMutableList()
            for(i in wFlag.indices.reversed()) {
                if(wFlag[i] == '1') {
                    copyA2.forEach {
                        it.removeAt(i)
                    }
                }
            }

            if(copyA2.size == h2 && copyA2 == b && copyA2.first().size == w2 && copyA2 == b) {
                println("Yes")
                return
            }
        }
    }

    println("No")
}

bit全探索と言いつつ、ビット演算ではなくStringでやっています。最初にそういうやり方を覚えてしまったのでそうなっていますが、たぶん遅いのでそのうちちゃんとしたやり方を覚えたいと思います。

map { it.toMutableList() }.toMutableList() はちょっとわかりづらいですがリストのコピーを行う処理です。
reversed() を使ってフラグを後ろから見ているのは、リストの要素の削除は後ろからやらないと順番がずれて面倒なためです。

残念だったポイントは色々あります。まず、若干変なやり方とはいえ一応知っているアルゴリズムで解ける問題だったということ、しかもコンテスト中に「これbit全探索で解けるんじゃね？」って思ったのにそうしなかったということです。
前回、bit全探索ではないですがそれの亜種で解こうとしてTLEだったのが気になっていて、別のやり方を模索してしまったのがダメでした。そういうふわっとした判断ではなく、制約を見てちゃんと計算量を見積もるべきでした。今回の問題は制約が緩く、あまり計算量を考えなくても解ける問題だったので、計算量を見積もってそのことに気づいていればコンテスト中に解くことができた可能性もあります。解けたかもしれない問題を落としたということでまたもや悔しい結果となりましたね…
まあ、コンテスト後に実装したらすごく時間がかかってしまったので、どちらにせよ無理だった可能性が高いですが。
時間がかかったのは、アルゴリズムとしては知っていても実装に慣れていなかったからですね。知らなければどうしようもないけど、知っているだけではダメというのも教訓ですね。

教訓

できるだけ計算しないで求める方法を考えるようにする
- 長期的には、計算力を高めていったほうがいいかもしれないが…
bit全探索は正しいやり方（？）をちゃんと覚える
ちゃんと計算量を見積もる
よく使うアルゴリズムは覚えておくだけでなく実装に慣れておく
- もしくは、ググって実装例をパクればいいのかも…

悔しい日々が続きますが、涙（WA、TLE）の数だけ強くなれるはずなので頑張りますね。

B - Nice Grid

C - Matrix Reducing

教訓

Discussion