2019年度ICPC国内予選参加記
2019/07/12にICPC国内予選に参加して敗北しました。
チーム kani
名前を凝ろうとしていた結果期日寸前にまで迫り、結局3秒で思いついたものになりました。
別大学にも大文字違いのKani
というチームがいたみたいです。
- しのみー@1125__rui: 顔と頭は良いが人の心を失ってしまった考察班。Rustが好きで、このチームで唯一競技プログラミングに取り組んでいる。
- Hibiki@4afS_: ハッパとHaskellが好きな考察班。数学メイン。物理攻撃力が高い。
- くろわらび@black_bracken: 色々書く実装班。予選直前にヒモQ*1を20m分ぐらい購入したら3mで飽きた。
結果は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)では使わないほうが良いかも。
では。