[AtCoder] AtCoder Beginner Contest 337 E. Bad Juice

문제풀이

1. 현재 구간에서 왼쪽 절반을 검사하면 구간의 왼쪽에 있는지 오른쪽에 있는지 알 수 있다.
2. depth가 같은 구간끼리 묶어서 검사한다.

---

주의사항

---

소요시간

1시간

---

package AtCoder.ProblemList.Difficulty800_1199.BadJuice

fun main() {
    val N = readln().trim().toInt()
    val arr = Array(4 * N) { IntArray(2) }
    fun search(start: Int = 1, end: Int = N, idx: Int = 1) {
        arr[idx][0] = start
        arr[idx][1] = end
        if (start != end) {
            val mid = (start + end) / 2
            search(start, mid, idx * 2)
            search(mid + 1, end, idx * 2 + 1)
        }
    }
    search()
    var count = 0
    val map = mutableMapOf<Int, Int>()
    var mapIdx = 0
    var log = 0
    var result = List(arr.size.toString(2).length + 1) { StringBuilder() }
    for (i in 2 until arr.size step 2) {
        if (arr[i][0] == 0) continue
        val (l, r) = arr[i]
        if (i.toString(2).length > log) {
            if (count > 0) {
                result[log].insert(0, count)
                mapIdx++
            }
            log = i.toString(2).length
            count = 0
        }
        count += (r - l + 1)
        map[i] = mapIdx
        result[log].append(" ${(l..r).joinToString(" ")}")
    }
    if (count > 0) result[log].insert(0, count)
    result = result.filter { it.isNotEmpty() }
    println(result.size)
    println(result.joinToString("\n"))
    val S = readln().trim()
    var idx = 2
    while (true) {
        if (S[map[idx]!!] == '0') idx++
        if (arr[idx][0] == arr[idx][1]) break
        else idx *= 2
    }
    println(arr[idx][0])
}

---

문제링크

https://atcoder.jp/contests/abc337/tasks/abc337_e

---

회고

이분 탐색 하면 최소값이 되겠다는 아이디어는 금방 떠올랐지만 구현이 조금 어려웠다.