ABC 085-D Katana Thrower (Kotlin/Go)

irisruneです。この問題を選んだ理由は最近発売された某ゲームを連想したからです。

今回は構造体の配列が作れなくてGoを断念したのでKotlinで解いていましたが、 後でGoで解き直したので両方のコードを掲載します。

atcoder.jp

初見だとそれほど難しくなさそうに見えたのですが、1回目のACまでに2WAしたりと結構苦戦しました。 まずは解説を見ずに解いたKotlinのコードです。

class Katana(val at : Int, val th : Int)

fun ceilDiv(t : Int, d : Int) : Int{
    return if(t % d > 0) t / d + 1 else t / d
}

fun thrower(attacker : Katana, lKatana : MutableList<Katana>, h : Int, n : Int) : Pair<Int, Int>{
    var cnt = 0
    var hp = h
    for(i in 0..(n - 1)){
        if(hp <= attacker.th) return Pair(cnt, hp)
        if(lKatana[i].th <= attacker.at) return Pair(cnt, hp)
        hp -= lKatana[i].th
        cnt++
        if(hp <= 0) return Pair(cnt, hp)
    }
    return Pair(cnt, hp)
}

fun battle(attacker : Katana, lKatana : MutableList<Katana>, h : Int, n : Int) : Int{
    var (cnt, hp) = thrower(attacker, lKatana, h, n)
    if(hp <= 0) return cnt
    hp -= attacker.th
    cnt++
    if(hp <= 0) return cnt

    return cnt + ceilDiv(hp, attacker.at)
}

fun main(args: Array<String>){
    val (n, h) = readLine()!!.split(" ").map(String::toInt)

    val lKatana = mutableListOf<Katana>()
    for(i in 0..(n-1)){
        val (at, th) = readLine()!!.split(" ").map(String::toInt)
        lKatana.add(Katana(at, th))
    }

    lKatana.sortByDescending { it.at }
    val attacker = lKatana[0]
    lKatana.removeAt(0)

    lKatana.sortByDescending { it.th }
    println(battle(attacker, lKatana, h, n - 1))
}

基本方針としては、

• 振る用の武器を予め確保しておく。
• それ以外の武器で、振る用の武器を振るより投げる攻撃力の高い武器を投げる攻撃力が高い順に投げる。
• 最後の一撃として振る用の武器を仮想的に投げておく。
• 振る用の武器を振って魔物を倒す。

という形で、途中で魔物が倒れたり振る用の武器を投げて倒せる状態になったりした場合には処理を中断します。 2WAしたのは振る用の武器以外を投げた後に魔物が倒れているかどうかの判定をしていなかったためです。

反省点としては、

• 制約条件を読み飛ばしていたため、振る攻撃力より投げる攻撃力が必ず高いことに途中で気付いた。
  • 問題文はしっかり読みましょう。
• 振る用の武器とそれ以外の武器を区別した結果処理が煩雑になっている。
  • 振る用の武器を投げて倒せるかどうかの判定を毎回入れたりしている点など。
• 振る用の武器を振る前に投げていることから、振る用の武器とそれ以外の武器を区別する意味がないことに気付いておきたかった。
  • そればかりか、振る攻撃力と投げる攻撃力を個別に考えることができるので処理が簡略化できる。

…というのを解説を読んだ時点では理解していなくて、翌朝になって突然理解しました。 その結果Goでもなんとか実装できるようになったのでGoで解き直したのがこちらです。

package main

import (
    "fmt"
    "sort"
)

func ceilDivInt(end int, div int) int {
    if end%div > 0 {
        return end/div + 1
    }
    return end / div
}

func battle(h int, attack int, arrB []int) int {
    var cnt = 0
    for i := range arrB {
        if arrB[i] < attack {
            break
        }
        h -= arrB[i]
        cnt++
        if h <= 0 {
            break
        }
    }
    if h <= 0 {
        return cnt
    }
    return cnt + ceilDivInt(h, attack)
}

func main() {
    const nCity = 5
    var n, h int
    fmt.Scan(&n, &h)
    var arrA, arrB []int
    for i := 0; i < n; i++ {
        var a, b int
        fmt.Scan(&a, &b)
        arrA = append(arrA, a)
        arrB = append(arrB, b)
    }
    sort.Sort(sort.Reverse(sort.IntSlice(arrA)))
    sort.Sort(sort.Reverse(sort.IntSlice(arrB)))

    var attack = arrA[0]

    fmt.Println(battle(h, attack, arrB))
}

関数が1個減ったり、構造体（クラス）を使わなくてよくなったりと簡略化されました。

こちらの反省点として、早期returnのために除算の切り上げ処理を関数化したりしているのですが、 Goはif文の処理部分で1文のみであっても中括弧が必須なためreturn文のみにしても簡略化しきれておらず、 あまり関数化の恩恵が大きくないような気はします。 関数名で処理を説明できたりするので恩恵がないこともないはずですが。

雑記

• 多少アルゴリズムが違いますが、Kotlinの方がGoより速いですね…
  • KotlinとGoで時間のかかる問題が違うのがよくわからないです。

追記

• Kotlinでも2回目と同じアルゴリズムで解いてみたところもっと速くなりました。
  • Goの方がパッケージ提供されてるソートが弱かったりするんでしょうか。

さらに追記

• 下から順に、
  • 配列（のスライス）を初めから容量nで生成して拡張処理を行わないようにした。
  • 入力の際に振る攻撃力の最大値を求めることでソートする配列を2個から1個に減らした。
  • 除算して切り上げる処理を関数でなく直接行うようにした。
• わけなのですが、あまり計算時間が変わらないですね…
  • 入力処理の問題だとしても、Kotlinより遅いのはよくわからないですね。