Kotlin Heroes 2 writeup

Dashboard - Kotlin Heroes: Episode 2 - Codeforces

これに参加した。日本時間では23:35分スタートという過酷なコンテストだったが、最後まで粘った。 結果は画像の通り3完で133位だった。D, E共に考察を最後まで詰め切れず、とても悔しい。

順位

ちなみに、このコンテストは上位3名に賞金が、上位50人にTシャツとバッジがもらえるというもので、私も上位50位に入ろうと必死だったができなかった。

画像の通り、ボーダーは1h50m以内に5完という、比較的簡単なものだった。

ボーダーであるA-Eまでの問題についてコードと共に考察や解法を書いていこうと思う。というのも、公式の解法が見つからなかったからだ。(知っている方はコメントなどで教えてください)

なお、Kotlinバージョンは1.3を想定している。

A Three Problems

Problem - A - Codeforces

問題概要

問題の数nと、n個続く問題の難易度が与えられる。 うまく3つ問題を選ぶことで、1問目の難易度<2問目の難易度<3問目の難易度 とできるなら選んだ問題の1-indexedのインデックスを出力せよ。 複数ある場合はどれでもよい。 不可能なら"-1 -1 -1"を出力せよ。

サンプル

9
10 10 11 10 10 10 10 10 1

たとえば"9 1 3"が答えになる。意味は、1問目に9番目の問題、2問目に1番目の問題、3問目に3番目の問題を選ぶと、難易度が1<10<11となる。

解法

問題の難易度を、重複を取り除いてソートしてリストに入れる。 そのリストのサイズが3未満、つまり難易度の種類が3種類未満なら不可能。 リストのサイズが3以上なら前から3つの"インデックスを"を出力。

fun main() {
    val n = readLine()!!.toInt()
    val distinctList = readLine()!!.split(" ")
        .map { it.toInt() }
        .mapIndexed { index, complexity ->
            Problem(complexity, index + 1)
        }
        .distinctBy { it.complexity }
        .sortedBy { it.complexity }
    if (distinctList.size < 3) {
        println("-1 -1 -1")
    } else {
        println(distinctList.take(3).joinToString(" ") { it.index.toString() })
    }
}

data class Problem(val complexity: Int, val index: Int)

B Traveling Around the Golden Ring of Berland

Problem - B - Codeforces

問題概要

町の数nと、それぞれの町に何回以上行きたいかが与えられる。 町は1-nまで番号が割り振られており、町iからは町i+1にしかいけない。町nからは町1にいける。 町1の手前からスタートして、町に何回以上行きたいという要望を全て満たすとき最低いくつ町を訪れることになるか出力せよ。

サンプル

5
0 3 1 3 2

1-nを2周して、3周目で町1から町4まで訪れていけばいいので5+5+4で14つ訪れることになる。

3
1 0 0

町1の手前からスタートなので、答えは1である。

解法

ある町iをk回訪れるには、町1-nを(k-1)回訪れる必要がある。 そして最後の一回の訪問に町1からiまでiつの町を訪れるので、n * (k-1) + i訪れる。 答えは一番訪れる回数が多い町の中で、一番町1から離れているものを計算するだけ。

fun main() {
    val n = readLine()!!.toLong()
    val a = readLine()!!.split(" ").map { it.toInt() }
    val maxVisit = a.max()!!
    val maxIndex = a.lastIndexOf(maxVisit)
    println(n * (maxVisit - 1) + maxIndex + 1)
}

C Ice Cream

Problem - C - Codeforces

問題概要

夏の日がn日あります。i日目のアイス1個の価格はc_iです。 n日間を通して、トータルでちょうどk個アイスクリームを食べたいです。 i日目には最低a_i個、最高b_i個のアイスを食べます。 各日、何個食べれば一番安く、丁度k個食べれるか出力せよ。 不可能な場合、-1を出力せよ。

サンプル

3 7
3 5 6
0 3 4
3 3 3

3日あって、7個食べたい。 1日目には3つ、2日目には1つ、3日目には3つ食べれば6*3+4*1+3*3=31の価格で食べられる。 各日に最低限食べなければいけない量があることに注意！

解法

各日最低購入数の和がkを超えていたら不可能。 各日最高購入数の和がkを下回っていたら不可能。 それ以外の場合、丁度k個買うことは可能。 最低購入数よりも、(k - 各日最低購入数の和)個のアイスn日を通して買う必要がある。 あと追加で買える個数(最高購入数-最低購入数)と値段のペアを使って、貪欲に安いものから買っていけばOK。

import java.lang.Math.min

fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map { it.toLong() }
    val data = Array(n.toInt()) {
        readLine()!!.split(" ").map { it.toLong() }
    }.sortedBy { it[2] }

    var cost = data.map { it[0] * it[2] }.sum()
    var ice = data.map { it[0] }.sum()

    if (ice < k) {
        data.forEach {
            val eat = min(it[1] - it[0], k - ice)
            cost += eat * it[2]
            ice += eat
        }
    }

    println(if (ice == k) cost else -1)
}

D Teams

Problem - D - Codeforces

問題概要

n個の整数がある。 ある数をa個と、そのk倍の数をb個のペアをできるだけ作れ。 作れるペアの最大数を出力せよ。

サンプル

12 1 2 2
1 1 2 2 2 2 2 3 3 4 6 6

(3, 6, 6), (1, 2, 2), (1, 2, 2)の3つのペアが最大。

解法

ある数は、それをa個の方のグループとして使われるときと、b個の方のグループとして使われるときとの2パターンがある。 ここで、a < bのときはaとして使うのをひとつ我慢して、bとして使ってもペアを作れる個数が前より真に増えない。 a > bのときbとして使うのをひとつ我慢しても、aとして使ってもペアは真に我慢する前より増えない。 よって小さいほうを使うべきで、それによって大きい方から見るのか小さい方から見るのか変わってくる。

説明がよくわからないと思うが、コードを見てわかってほしい。

fun main() {
    val MAX_NUM = 1000000
    val (n, a, b, k) = readLine()!!.split(" ").map { it.toInt() }
    val r = readLine()!!.split(" ").map { it.toInt() }
    val map = Array(MAX_NUM + 10) { 0 }
    for (x in r) map[x]++
    var ans = 0
    if (a <= b) {
        for (i in MAX_NUM downTo 1) {
            if(i % k != 0) continue
            val q = Math.min(map[i / k] / a, map[i] / b)
            ans += q
            map[i / k] -= q * a
            map[i] -= q * b
        }
    } else {
        for (i in 1..MAX_NUM) {
            if(i * k > MAX_NUM) break
            val q = Math.min(map[i] / a, map[i * k] / b)
            ans += q
            map[i] -= q * a
            map[i * k] -= q * b
        }
    }
    println(ans)
}

E Double Permutation Inc.

Problem - E - Codeforces

問題概要

n個の数を含む数列を、RGBの3パターンのどれかに分類する。 この数列は数の順番や個数に対して全く制約がない。つまり、すべて同じ数などの場合もある。

• R: Rに分類された数を数列の左から右に見ていくと、1から適当な数kまでがちょうど1つづつ出現する。
• G: Gに分類された数を数列の左から右に見ていくと、1から適当な数k(Rのkと同じ)までがちょうど一つずつ出現する。ただし、Rと同じ相対順序を保たなければならない。
• B: Bに分類された数と同じ値の数はR, Gには出現しない。

nつの数列を、できるだけ多く赤と緑に分類した時の、数列をRGBで表して出力せよ。

サンプル

5
1 2 3 2 1

答えは"RBBBG"。2は1との相対関係をRとGで同じにすることができないのでR, Gに選べない。 "GBBBR"も正解。

3
1 1 1

"BBB"が正解。どれか2つをRとGに分類すると、「Bに分類された数と同じ値の数はR, Gには出現しない」という制約を守れない。

10
3 9 3 1 2 1 2 4 4 4

"RBGRRGGBBB"が正解。

解法

まず、数をRまたはGに分類できる条件として、同じ値の数がちょうど2つである必要がある。 RやGに分類するのは1~kまでがそれぞれちょうど1種類しかでないようにしなければならない。 2つより多いと1つ以上をBに分類しなければいけないが、Bに分類する条件より、RやGに分類できないからである。 同じ値の2つの数字をRとGに分類するには左の数字をRに、右の数字をGにするなど左右とRGを一貫させればよい。 あとは、どの数kまでならRやGに分類しても大丈夫かを探す。 これを1から一つずつ試していると間に合わないので、二分探索で探す。

fun main() {
    readLine()
    val a = readLine()!!.split(" ").map { it.toInt() }
 
    /**
     * @param k 1からどの値までRとGに分類するか
     */
    fun solve(k: Int): Pair<Boolean, String> {
        val count = IntArray(k)
        val ans = CharArray(a.size) { 'B' }
        val rPermutation = mutableListOf<Int>()
        val gPermutation = mutableListOf<Int>()
        for ((index, v) in a.withIndex()) {
            if (v > k) continue
            if (count[v - 1] == 0) {
                ans[index] = 'R'
                rPermutation.add(v)
            } else if (count[v - 1] == 1) {
                ans[index] = 'G'
                gPermutation.add(v)
            }
            count[v - 1]++
        }
        return if (count.all { it == 2 } && rPermutation == gPermutation) true to String(ans)
        else false to ""
    }
 
    var low = 0
    var high = a.size / 2 + 1
    while (high - low > 1) {
        val mid = (low + high) / 2
        if (solve(mid).first) low = mid else high = mid
    }
    println(solve(low).second)
}

最後に

長い記事を最後まで読んでくださりありがとうございました！ もしKotlin Heroes 3が開催されたら、Tシャツが欲しいですね。

気づいたことなどあればTwitter(@naoppyj)まで連絡をください。