全国統一プログラミング王決定戦予選 C Different Strokes をKotlinで

irisruneです。どのくらいの重さの問題を扱えばいいか毎回悩みどころです。

今回は趣向を変えまして1月開催の企業コンについて、C問題までは解けたのでC問題を。

atcoder.jp

個人的な感触では400点にしては簡単な方でしょうか。 ABC121 Cと比べるとソートの実装力よりは発想力の方に比重があると思います。

fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val ll = mutableListOf<List<Long>>()
    for(i in 0..(n - 1)){
        val (a, b) = readLine()!!.split(" ").map(String::toLong)
        val l = listOf(a, b, a + b)
        ll.add(l)
    }
    ll.sortBy{it[2] * -1}
    var aSum = 0L
    var bSum = 0L
    for(i in 0..(n - 1)){
        if(i % 2 == 0) aSum += ll[i][0]
        else bSum += ll[i][1]
    }
    println(aSum - bSum)
}

解法としては大体解説と同じなので、そこに至った経緯について。

「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値（以下スコアと呼ぶ） を最大化したいので、相手が幸福度を得るとその幸福度分スコアが下がるとみなすことができます。

一方、ルール上自分が食べた料理を相手が食べることはできないので自分が料理を食べることで 相手がその料理から得る幸福度を0にすることができます。

以上のことから、料理を食べることで自分が得る幸福度と相手が得るはずだった幸福度の和を 疑似的なスコアとみなすことができます。そのため、自分と相手の幸福度の和が高い料理を食べるのが 高橋くんと青木さん双方にとって最適戦略となります。

あとは幸福度の和で料理をソートし、それに対して愚直に最適戦略をとった際のスコアの計算を行えば解答を導き出すことができます。

ゲーム理論的に説明したかったのですが少し本を読んだ程度なのであまりうまくいかないですね。

今回のコードレビューについてですが、配列インデックスの0や1がマジックナンバーっぽくなってるので 辞書型を使えば可読性が上がるかもしれないです。

雑記

• 最近忙しいため更新日を守れない可能性があります（予防線）。
• ABC117のC問題もD問題も解けなくてつらい。