👌

AtCoder Beginner Contest 307参加記（A～D）

2023/06/25に公開

AtCoder

競プロ

tech

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

今回は残念ながら2完ですが、Cが難しくて解けなかった人が多くて、レートとしては若干上がりました。
なのでCとDはコンテスト後に通した結果となります。

A - Weekly Records

最初、問題文をちゃんと読まずに全ての合計値を出す実装をしました…
出力例を見て、慌てて添字を計算する実装をしました。

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

    var ans = mutableListOf<Long>()
    for(i in 0 until n) {
        var sum = 0L
        for(j in 0 until 7) {
            sum += a[j + i * 7]
        }
        ans.add(sum)
    }
    println(ans.joinToString(" "))
}

Longでなくてもよかったかもしれませんが、なんか怖かったのでそうしていました。

B - racecar

$i$ と $j$ が同じ場合だけスキップして全探索です。回文判定はreversed()を使って楽をしました。

fun main() {
    val n = readLine()!!.toInt()
    val s = List(n) {
        readLine()!!
    }

    for(i in 0 until n) {
        for(j in 0 until n) {
            if(i == j) {
                continue
            }

            val ss = s[i] + s[j]

            if(ss == ss.reversed()) {
                println("Yes")
                return
            }
        }
    }

    println("No")
}

C - Ideal Sheet

さて解けなかったC問題です。最近グリッド系の問題に立て続けに殺されましたが、またしてもグリッド系です。嫌な予感しかしなかったのでとりあえずD問題も見てみましたが、そちらはそちらで苦手そうな雰囲気を感じました。
それで迷って、（今思えば血迷ったとしか言えないですが）Cのほうを頑張ろうと思って着手し、見事に討ち死にしました。

とりあえず、考えたこととしては以下のとおりです。
まず、制約からして全探索でいけそうですが、シート $C$ の大きさが無限なので何らかの条件で範囲を絞る必要があります。
そのために必要な考え方として、この問題は黒マスの位置だけが重要で、最も外側にある黒マスよりも先の透明マスは無視していいといえます。
なのでそのような外側の透明マスは全て取り除いて、シート $X$ の実質的な範囲と同じ大きさのシートを作って、その中でシート $A$ とシート $B$ を動かしてシート $X$ と一致するかどうかを一通り調べればいいと思いました。
そのためには、シート $A$ の実質範囲とシート $B$ の実質範囲の両方がシート $X$ の実質範囲のうちに収まる大きさである必要があります。収まらない場合はその時点で答えはNoとなります。

結果としては一応方針としては正しくて、しかし実装力が追いつかなくて時間内に実装しきることができなかったです…
サンプルが通る実装まではできたものの、WAを取り切ることができず。

一応、上記の方針のまま突っ切ってコンテスト後に通った実装が以下です。

import kotlin.math.max
import kotlin.math.min

fun main() {
    val (ha, wa) = readLine()!!.split(" ").map { it.toInt() }
    val a = List(ha) {
        readLine()!!
    }.toMutableList()

    val (hb, wb) = readLine()!!.split(" ").map { it.toInt() }
    val b = List(hb) {
        readLine()!!
    }.toMutableList()

    val (hx, wx) = readLine()!!.split(" ").map { it.toInt() }
    val x = List(hx) {
        readLine()!!
    }.toMutableList()

    // 黒範囲の高さ
    var ar = realRange(a)
    var br = realRange(b)
    var xr = realRange(x)

    if(ar.height() > xr.height() || ar.weight() > xr.weight() || br.height() > xr.height() || br.weight() > xr.weight()) {
        println("No")
        return
    }

    // 切り詰め
    for(i in 0 until ar.hStart) {
        a.removeAt(0)
    }
    ar = realRange(a)

    for(i in ar.hEnd + 1 until a.size) {
        a.removeAt(a.size - 1)
    }
    ar = realRange(a)

    for(i in 0 until a.size) {
        val t = a[i].toMutableList()
        for(j in 0 until ar.wStart) {
            t.removeAt(0)
        }
        a[i] = t.joinToString("")
    }
    ar = realRange(a)

    for(i in 0 until a.size) {
        val t = a[i].toMutableList()
        for(j in ar.wEnd + 1 until t.size) {
            t.removeAt(ar.wEnd + 1)
        }
        a[i] = t.joinToString("")
    }
    ar = realRange(a)

    for(i in 0 until xr.hStart) {
        x.removeAt(0)
    }
    xr = realRange(x)

    for(i in xr.hEnd + 1 until x.size) {
        x.removeAt(x.size - 1)
    }
    xr = realRange(x)

    for(i in 0 until x.size) {
        val t = x[i].toMutableList()
        for(j in 0 until xr.wStart) {
            t.removeAt(0)
        }
        x[i] = t.joinToString("")
    }
    xr = realRange(x)
    for(i in 0 until x.size) {
        val t = x[i].toMutableList()
        for(j in xr.wEnd + 1 until t.size) {
            t.removeAt(xr.wEnd + 1)
        }
        x[i] = t.joinToString("")
    }

    xr = realRange(x)

    for(i in 0 until br.hStart) {
        b.removeAt(0)
    }
    br = realRange(b)

    for(i in br.hEnd + 1 until b.size) {
        b.removeAt(b.size - 1)
    }
    br = realRange(b)

    for(i in 0 until b.size) {
        val t = b[i].toMutableList()
        for(j in 0 until br.wStart) {
            t.removeAt(0)
        }
        b[i] = t.joinToString("")
    }
    br = realRange(b)
    for(i in 0 until b.size) {
        val t = b[i].toMutableList()
        for(j in br.wEnd + 1 until t.size) {
            t.removeAt(br.wEnd + 1)
        }
        b[i] = t.joinToString("")
    }
    br = realRange(b)

    val compX = x.map { it.toCharArray() }.toMutableList()

    for(i in 0 until xr.height() - ar.height() + 1) {
        for(j in 0 until xr.weight() - ar.weight() + 1) {
            val rect = emptyRange(xr.height(), xr.weight())

            for(m in 0 until ar.height()) {
                for(n in 0 until ar.weight()) {
                    val mm = m + i
                    val nn = n + j

                    rect[mm][nn] = a[m][n]
                }
            }
            for(k in 0 until xr.height() - br.height() + 1) {
                for(l in 0 until xr.weight() - br.weight() + 1) {
                    val copyRect = rect.map { it.clone() }.toMutableList()

                    for(m in 0 until br.height()) {
                        for(n in 0 until br.weight()) {
                            val mm = m + k
                            val nn = n + l

                            if(b[m][n] == '#') {
                                copyRect[mm][nn] = b[m][n]
                            }
                        }
                    }

                    if(copyRect.map { it.joinToString("") } == compX.map { it.joinToString("") }) {
                        println("Yes")
                        return
                    }
                }
            }
        }
    }

    println("No")
}

fun emptyRange(h: Int, w: Int): MutableList<CharArray> {
    return MutableList(h) { CharArray(w) { '.' } }
}

fun realRange(s: List<String>): RealRange {
    val hStart = s.indexOfFirst { it.contains('#') }
    val hEnd = s.indexOfLast { it.contains('#') }

    val h = s.size
    val w = s[0].length

    var wStart = Int.MAX_VALUE
    var wEnd = 0
    for(i in 0 until h) {
        if(!s[i].contains('#')) {
            continue
        }

        val start = s[i].indexOf('#')
        val end = s[i].lastIndexOf('#')
        wStart = min(wStart, start)
        wEnd = max(wEnd, end)
    }

    return RealRange(hStart, hEnd, wStart, wEnd)
}

data class RealRange(
    val hStart: Int, val hEnd: Int, val wStart: Int, val wEnd: Int
) {
    fun height(): Int {
        return hEnd - hStart + 1
    }

    fun weight(): Int {
        return wEnd - wStart + 1
    }
}

けっこうエグい実装になりました。外側の透明マスを除去する部分が長いので、それを関数に切り出せばだいぶましになりそうですが、それでも長い。
実装しきれなかったのは、そもそもこのように冗長な実装となってしまって考慮が必要なことが膨れ上がったのが最大の理由です。以前も同じようなことを書いた気がしますね。やはり重実装系を、いかにシンプルに実装するかという練習が必要そうです。
（一応やっていたけど不十分すぎた）

さすがに通ったとはいえ上記の実装のままでOKとは思えないので、解説も見てみました。
evimaさんの別解のほうを主に参照しました。（evimaさんの実装のほうが自分としてはわかりやすいことが多いため）

この解説だと、グリッドを直接処理するのではなく、黒マスの位置を記録した集合を使って判定する方法が示されていました。なるほど… 黒マスの位置だけが重要なので、たしかにその情報さえあれば判定できますね。
それぞれのシートを比較するためにはそのままだとダメなので補正すると。たしかに、複雑なことをして外側を削除するとかするよりもそちらのほうがはるかに簡単ですね。言われてみればそうなんですが、これを自力で思い付ける力がなく。悲しいですね。

こちらの方針でやってみたのがこちら。

fun main() {
    val (ha, wa) = readLine()!!.split(" ").map { it.toInt() }
    val a = List(ha) {
        readLine()!!.toCharArray()
    }

    val (hb, wb) = readLine()!!.split(" ").map { it.toInt() }
    val b = List(hb) {
        readLine()!!.toCharArray()
    }

    val (hx, wx) = readLine()!!.split(" ").map { it.toInt() }
    val x = List(hx) {
        readLine()!!.toCharArray()
    }

    val normalizedA = normalize(blackPositionSet(a))
    val normalizedB = normalize(blackPositionSet(b))
    val normalizedX = normalize(blackPositionSet(x))

    for(i in -hx..hx) {
        for(j in -wx..wx) {
            val set = normalizedA + normalizedB.map { it.first + i to it.second + j }
            if(normalize(set) == normalizedX) {
                println("Yes")
                return
            }
        }
    }

    println("No")
}

fun blackPositionSet(s: List<CharArray>): MutableSet<Pair<Int, Int>> {
    val set = mutableSetOf<Pair<Int, Int>>()
    for(i in s.indices) {
        for(j in s.first().indices) {
            if(s[i][j] == '#') {
                set.add(i to j)
            }
        }
    }
    return set
}

fun normalize(s: Set<Pair<Int, Int>>): Set<Pair<Int, Int>> {
    val dy = s.map { it.first }.min()!!
    val dx = s.map { it.second }.min()!!

    return s.map { it.first - dy to it.second - dx }.toSet()
}

だいぶシンプルになりました。自力で思い付けるようになりたい・・・

追記

後日、上記をさっぱり忘れた後に再度解き直してみた結果。方針としては前者に近いけど、関数に切り出したりして、だいぶマシになっています。

const val black = '#'
const val white = '.'

var ha = 0
var wa = 0
var hb = 0
var wb = 0
var hx = 0
var wx = 0

fun main() {
    val (_ha, _wa) = readln().split(" ").map { it.toInt() }
    ha = _ha
    wa = _wa
    val a = List(_ha) {
        readln()
    }.trimmed()

    val (_hb, _wb) = readln().split(" ").map { it.toInt() }
    hb = _hb
    wb = _wb
    val b = List(_hb) {
        readln()
    }.trimmed()

    val (_hx, _wx) = readln().split(" ").map { it.toInt() }
    hx = _hx
    wx = _wx
    val x = List(_hx) {
        readln()
    }

    for(i in 0 until hx) {
        for(j in 0 until wx) {
            for(k in 0 until hx) {
                for(l in 0 until wx) {
                    if(isComplete(a, b, x, i, j, k, l)) {
                        println("Yes")
                        return
                    }
                }
            }
        }
    }
    println("No")
}

fun List<String>.trimmed(): List<String> {
    val rowStart = this.indexOfFirst { it.contains(black) }
    val rowEnd = this.indexOfLast { it.contains(black) }

    val rows = this.subList(rowStart, rowEnd + 1)

    val findList = BooleanArray(rows.first().length)
    for(j in rows.first().indices) {
        for(i in rows.indices) {
            if(rows[i][j] == black) {
                findList[j] = true
                break
            }
        }
    }
    val columnStart = findList.indexOfFirst { it }
    val columnEnd = findList.indexOfLast { it }

    return rows.map { it.substring(columnStart, columnEnd + 1) }
}

fun isComplete(a: List<String>, b: List<String>, x: List<String>, si: Int, sj: Int, sk: Int, sl: Int): Boolean {
    val sheet = List(hx) { CharArray(wx) { white } }

    if(!fill(a, sheet, si, sj)) {
        return false
    }
    if(!fill(b, sheet, sk, sl)) {
        return false
    }

    return sheet.map { it.joinToString("") } == x
}

fun fill(fromSheet: List<String>, sheet: List<CharArray>, si: Int, sj: Int): Boolean {
    for(i in fromSheet.indices) {
        for(j in fromSheet.first().indices) {
            val di = i + si
            val dj = j + sj

            if(di !in 0 until hx) {
                return false
            }
            if(dj !in 0 until wx) {
                return false
            }

            if(sheet[di][dj] == black) {
                continue
            }

            sheet[di][dj] = fromSheet[i][j]
        }
    }
    return true
}

D - Mismatched Parentheses

Dはコンテスト中にコードを書いていないですが、見てみました。

これって、あれなんですよね。以前似たような問題がありました。

というわけで以下の実装であっさり解けました。~~（1ペナ出したのは内緒）~~

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

    val stack = java.util.ArrayDeque<Char>()

    var count = 0
    for(i in 0 until n) {
        if(s[i] == '(') {
            count++
        }
        if(s[i] == ')' && count != 0) {
            do {
                val c = stack.removeLast()
                if(c == '(') {
                    break
                }
            } while (true)

            count--
        } else {
            stack.add(s[i])
        }
    }

    println(stack.joinToString(""))
}

')'を見つけたら、直近の'('までの文字を除去するのをただスタックでやるだけという。こちらを解いておけばよかったのに、無念。

感想

なんか同じことを何度も書いてしまっている気がしますが、Cを捨てる決断か、もしくはCを捨てないで実装しきることのどちらかができればよかったのですが、どちらもできす。

悩ましいところではあるんですけどね。Cは決して解けないほどの問題ではなかったはずなので、Cを捨てるべきだったという気持ちよりも、Cを実装しきることができるべきだったという気持ちのほうが強いです。どちらかといえば。

重実装系の問題を延々と解く練習をしたほうがいいかもしれないですね。

（執筆時間: 37分1秒）

A - Weekly Records

B - racecar

C - Ideal Sheet

追記

D - Mismatched Parentheses

感想

Discussion