PG BATTLE 2019 に参加しました

私は明石高専チームで参加し、難易度ましゅまろを担当しました。 余裕やろ～と思っていたら割とDが難しくてびっくりしました。

結果は3完です。4問目なのですが、Kotlinが使うJava-runtimeのバージョンが手元の環境と違っており、CEで通りませんでした。 CE回避したら通ったのでコードテストをしなかった(する時間が無かった)ことを悔やんでいます。

問題一覧ページ

PG BATTLE 2019問題一覧

難易度1 Jump

問題

https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-1.pdf

解法

境界判定をバグらせないように注意するだけ

fun main(args: Array<String>) {
    val (w, k, d) = readLine()!!.split(" ").map { it.toInt() }

    if(k <= d && w - k <= d) {
        println("Yes")
    } else {
        println("No")
    }
}

難易度2 AtCoder

問題

https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-2.pdf

解法

文字列を全部小文字か大文字にそろえて比べることでMaybeの判定をする。

fun main(args: Array<String>) {
    val s = readLine()!!
    println(
        when {
            s == "AtCoder" -> "Yes"
            s.toLowerCase() == "atcoder" -> "Maybe"
            else -> "No"
        }
    )
}

上のコードでもいいのだが、実はString.equalsメソッドにはignoreCaseというオプションがあるので、それで大文字小文字の区別なく比較することができる。

fun main(args: Array<String>) {
    val s = readLine()!!
    println(
        when {
            s == "AtCoder" -> "Yes"
            s.equals("AtCoder", ignoreCase = true) -> "Maybe"
            else -> "No"
        }
    )
}

難易度3

問題

https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-3.pdf

解法

変な風に解いてしまった。 ピンm本が立っているか倒れているかの配列を作り、シュミレーションするだけ。

j回目に投げる人はレーンjで投げて、開始からa+b秒後にボールがレーンに通達する。 倒れるピンの番号は、ピン番号+経過時間 = レーン番号より求まる。 後は倒れるピンの番号が1-mの間にあれば、配列を更新すればよい。

最後に配列を見て、倒れている個数をカウントする。

fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val isPinArrive = BooleanArray(m) { true }
    for (j in 1..n) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() }
        val reachTime = a + b
        val lane = j
        val pinNumber = lane - reachTime
        if(pinNumber in 1..m) {
            isPinArrive[pinNumber - 1] = false
        }
    }
    println(isPinArrive.count { !it })
}

難易度4

問題

https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-4.pdf

解法

各都市で暇をつぶすのは無限時間できる。 すると、各都市に対してできるだけ早く着いた方が選択支が増えるので嬉しいということがわかる。

また、ある都市を出てからもう一度同じ都市に回ってくるということはありえないこともわかる。それをするなら、その都市で同じ時間暇をつぶして待機すればいいだけだからである。

各都市に対して一番早く着く時間を求めるのはダイクストラ法でできるのだが、辺のコストを算出する処理がちょっとめんどくさい。 通る辺が通れない場合も考える必要がある。

コードはこちら、書いてるとき自分でも頭が混乱したのでコメントモリモリになってる。 答えがIntの範囲を越えそうだったのでLongを使ってる。

大きな流れとしては、まず隣接リストの構築をする。次にダイクストラ法で更新をしていく。最後に出力。 ダイクストラ法での更新時の、コスト算出が複雑なのでcalcCost関数に切り出した。

import java.util.*
import kotlin.comparisons.compareBy

const val INF = Long.MAX_VALUE / 2

fun main(args: Array<String>) {
    val (n, m, t, k) = readLine()!!
        .split(" ")
        .map { it.toInt() }
    //隣接リスト
    val edges = Array(n) {
        ArrayList<Edge>()
    }
    //隣接リストを構築
    repeat(m) {
        val (a, b, c, d) = readLine()!!
            .split(" ")
            .map { it.toLong() }
        edges[a.toInt() - 1].add(Edge((b - 1).toInt(), c, d))
        edges[b.toInt() - 1].add(Edge((a - 1).toInt(), c, d))
    }
    //(dijkstra中は推定値)最短時間
    val dist = LongArray(n)

    //fromReachTimeで頂点に到着し、そこからedgeを通る場合、一番早く渡れる時間を計算する
    fun calcCost(fromReachTime: Long, toEdge: Edge): Long {
        val moveCost = toEdge.cost
        val di = toEdge.di
        //いつでも通れる場合、すぐ通る
        if (di <= k) {
            return fromReachTime + moveCost
        }
        //tからどれだけ離れればギリギリ通れるか
        val outTime = di - k
        //混んで通れなくなる前に通る場合、一番遅い出発時間
        val leftLatest = t - outTime - moveCost
        //混んで通れなくなった後、一番最初に通れる時間
        val rightFastest = t + outTime

        return if (fromReachTime <= leftLatest) {
            fromReachTime + moveCost
        } else {
            Math.max(rightFastest, fromReachTime) + moveCost
        }
    }

    //start: 開始頂点
    //O(M log N)
    fun dijkstra(start: Int) {
        //distを初期化
        Arrays.fill(dist, INF)
        dist[start] = 0
        //キュー初期化
        val candidateQueue = PriorityQueue<Candidate>(1, compareBy { it.time })
        candidateQueue.add(Candidate(0, start))
        //最小値更新開始
        while (candidateQueue.isNotEmpty()) {
            val (c_time, c_v) = candidateQueue.poll()
            //意味のない情報を捨てる
            if (dist[c_v] < c_time) {
                continue
            }

            val toEdges = edges[c_v]
            for (e in toEdges) {
                val cost = calcCost(c_time, e)
                if (dist[e.to] > cost) {
                    dist[e.to] = cost
                    candidateQueue.add(Candidate(dist[e.to], e.to))
                }
            }
        }
    }

    dijkstra(0)
    if (dist[n - 1] == INF) {
        println(-1)
    } else {
        println(dist[n - 1])
    }
}

data class Candidate(val time: Long, val nodeNum: Int)
data class Edge(val to: Int, val cost: Long, val di: Long)