BlogBracken

FOR_MYSELF

2019年度ICPC国内予選参加記

雑記

2019/07/12にICPC国内予選に参加して敗北しました。

チーム kani

名前を凝ろうとしていた結果期日寸前にまで迫り、結局3秒で思いついたものになりました。 別大学にも大文字違いのKaniというチームがいたみたいです。

結果は2完30分ぐらいでした。役割分けとして実装はKotlinで僕が、考察班はABと、Cの考察をしのみーが、Dの考察をHibikiが担当しました。*2

A問題

最初に軽いミスをして15分くらいだった気がする。

private fun readInts() = readLine()!!.split(" ").map(String::toInt)

fun main() {
    while (true) {
        val (n, m) = readInts()
        if (n == 0 && m == 0) return

        val p = (0 until m).map { readInts() }

        (0 until n)
            .map { people -> (0 until m).map { subject -> p[subject][people] }.sum() }
            .max()
            ?.also { max -> println(max) }
    }
}

B問題

abs(nowX - keyX) + abs(nowY - keyY) + 1で距離ができるので回して合計。ここで30分過ぎぐらい?

private fun readInts() = readLine()!!.split(" ").map(String::toInt)

fun main() {
    while (true) {
        val (h, w) = readInts()
        if (h == 0 && w == 0) return

        val r = (0 until h)
            .map { y ->
                val line = readLine()!!
                line.mapIndexed { x, char -> Triple(char, x, y) }
            }
        val s = readLine()!!

        var cost = 0
        var nowX = 0
        var nowY = 0
        for (query in s) {
            val (_, keyX, keyY) = r
                .find { yLine -> yLine.any { triple -> triple.first == query } }
                ?.let { it.find { triple -> triple.first == query } }
                ?: return

            cost += Math.abs(nowX - keyX) + Math.abs(nowY - keyY) + 1
            nowX = keyX
            nowY = keyY
        }

        println(cost)
    }
}

C問題

大惨事。考察版から降ってきた考察は合っていて、実装バグらせたり*3競技中にコンビネーションやbit全探索*4を作ったりした。 ソースから悲惨具合がわかると思う。

private fun readInts() = readLine()!!.split(" ").map(String::toInt)
private fun readLongs() = readLine()!!.split(" ").map(String::toLong)

private infix fun Int.pow(power: Int): Int = Math.pow(this.toDouble(), power.toDouble()).toInt()

fun main() {
    while (true) {
        val (n, m) = readLongs()
        if (n == 0L && m == 0L) return
        val a = readLongs()
        val w = readLongs()

        val operationSymbolList = (0..((2 pow w.size - 1)))
            .asSequence()
            .map { bin -> bin.toString(2) }
            .map { binary -> (0 until (w.size - binary.length)).joinToString(separator = "") { "0" } + binary }
            .toList()

        val weightCombinationList = (0..((2 pow w.size) - 1))
            .asSequence()
            .map { bin -> bin.toString(2) }
            .map { binary -> (0 until (w.size - binary.length)).joinToString(separator = "") { "0" } + binary }
            .map { binary -> w.filterIndexed { index, _ -> (binary.getOrNull(index) ?: '0') != '0' } }
            .toList()

        println(operationSymbolList)

        val combinationSet = mutableListOf<Long>()
        weightCombinationList.forEach { weights ->

            weights.forEach { weight ->
                combinationSet += setOf(weight)
            }

            operationSymbolList.forEach { operationSymbols ->
                combinationSet +=
                    (0 until weights.size - 1)
                        .map { weightIndex ->
                            if (operationSymbols[weightIndex] != '0') {
                                weights[weightIndex] + weights[weightIndex + 1]
                            } else {
                                weights[weightIndex] - weights[weightIndex + 1]
                            }
                        }
                        .map(Math::abs)
                        .sum()
            }

        }
        combinationSet.remove(0)

        println("the size is ${combinationSet.size}")

        val requests = a - combinationSet

        if (requests.isEmpty()) {
            println(0)
        } else {
            var ans = -1L
            val x = mutableListOf<Long>()

            requests.forEach { request ->
                combinationSet.forEach {
                       x += request + it
                       x += Math.abs(request - it)
                }
            }

            x.sort()
            println("combinationSet ${combinationSet.sorted()}")
            println("requests       $requests")
            println(x)
            //for (i in requests.size until x.size) {
            //    if ((0 until requests.size - 1).all { sub -> x[i - sub] == x[i - sub + 1] }) {
            //        ans = x[i]
            //        break
            //    }
            //}

            for (i in x) {
                if (x.count { it == i } == requests.size) {
                    ans = i
                    break
                }
            }


            //for (i in 2 until x.size) {
            //    if (x[i - 2] == x[i - 1] && x[i - 1] == x[i]) {
            //        ans = x[i]
            //        break
            //    }
            //}

            //val map = mutableMapOf<Long, Int>()
            //requests.forEach { request ->
            //    combinationSet
            //        .filter { request > it }
            //        .map { Math.abs(request - it) }
            //        .forEach { map[it] = (map[it] ?: 0) + 1 }
            //}
//
            //val count = map.values.count { value -> value == requests.size }

            //var intersected = combinationSet
            //    .filter { requests[0] > it }
            //    .map { Math.abs(requests[0] - it) }
            //    .toSet()
            //requests.drop(1).forEach { request ->
            //    intersected = combinationSet
            //        .filter { request > it }
            //        .map { Math.abs(request - it) }
            //        .intersect(intersected)
            println(ans)
        }

        //println(if (intersected.isEmpty()) -1 else intersected.size)
    }
}

D問題

Cに時間を食われた。

まとめ

無刻印HHKBはチーム戦(かつICPC)では使わないほうが良いかも。

では。

*1:マスカット&ぶどう味、美味しいシャンプーみたいな味がする

*2:多分

*3:最後までincrease/decreaseのバグ修正に辿り着けなかった、申し訳ない

*4:後々分かったがここはDFSで良かった