ABC 012 D - バスと避けられない運命(Go)

irisruneです。GW中はJuliaについて色々調べたりしていました、その辺の諸々は雑記に。

atcoder.jp

少し忙しいので解説が難しくない問題を選びました。GW前の記事とジャンルが一緒ですね。

package main

import (
    "fmt"
)

const INF = 1000000000

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func dijkstra(adj [][]int, s int, n int) {
    dist := make([]int, n)
    for i := range dist {
        switch {
        case i == s:
            dist[i] = 0
        default:
            dist[i] = INF
        }
    }
    visited := make([]bool, n)
    visited[s] = true

    base := s
    for {
        next := -1
        minD := INF
        for i := range dist {
            if visited[i] {
                continue
            }
            dist[i] = minInt(dist[i], dist[base]+adj[base][i])
            if dist[i] < minD {
                next = i
                minD = dist[i]
            }
        }
        if next == -1 {
            break
        }
        base = next
        visited[next] = true
    }
    for i, d := range dist {
        adj[s][i] = d
        adj[i][s] = d
    }
}

func main() {
    var n, m int
    fmt.Scan(&n, &m)

    adj := make([][]int, n)
    for i := range adj {
        line := make([]int, n)
        for j := range line {
            switch {
            case i == j:
                line[j] = 0
            default:
                line[j] = INF
            }
        }
        adj[i] = line
    }

    for i := 0; i < m; i++ {
        var a, b, t int
        fmt.Scan(&a, &b, &t)
        adj[a-1][b-1] = t
        adj[b-1][a-1] = t
    }

    for i := 0; i < n; i++ {
        dijkstra(adj, i, n)
    }

    ans := INF
    for i := 0; i < n; i++ {
        maxD := 0
        for j := 0; j < n; j++ {
            maxD = maxInt(maxD, adj[i][j])
        }
        ans = minInt(ans, maxD)
    }
    fmt.Println(ans)
}

制約条件が非常に緩いため、実装自体はダイクストラ法を知っていれば難しくないと思います。どちらかといえば国語の問題と言えそうなくらいに問題文がややこしく、

高橋君は、バスに乗っている時間が最も長くなってしまうような、最悪のケースを常に想定します。 この、最悪なケースのバスに乗っている時間が、出来るだけ短くなるような場所に引っ越そうと思っています。

追記：なお、最悪のケースとは、バスに乗る時間の合計が最も短くなるように、乗るバスを選択した時に、最もバスに乗る時間の合計が長くなってしまうような位置に会社があるケースのことを指します。また、自宅から会社に行く際に、高橋君が乗るバスを選ぶことができ、高橋君はバスに乗る時間の合計が最も短い経路を選択するものとします。

このような文となっており、何を求めればよいかがよくわからなくなりがちです。 これは問題文を逆に辿っていけば多少わかりやすくなり、

• 高橋君はバスに乗る時間の合計が最も短い経路を選択する→最短経路を求める
  • バスに乗る時間の合計が最も短くなるように→同上
• 最もバスに乗る時間の合計が長くなってしまう→最短経路の最大値（ある地点から最も遠い場所までの最短経路）を求める
• 最悪のケースのバスに乗っている時間が、できるだけ短くなるような場所→最短経路の最大値が最小になる出発点を求める

といった形でそれぞれのバス停を始点としたときの最短経路をダイクストラ法で求めればよいことがわかります。

なお、隣接行列を用いると時間かかりますが、優先度付きキューを用いると計算量を減らすことができそうです。制約条件がなのでどちらにせよ問題なく間に合いますが。

コードレビュー

• 計算結果を記録する（2次元）配列を用意するのが面倒だったため隣接行列に計算結果を記録しているが、少しわかりにくくなっていると思われる。
  • 計算量の削減になるかという思いもあったが、おそらく変わらないと思われる。

雑記

• 機械学習に使えそうな言語として割と新しい言語であるJuliaに目を付けて文法や特徴など調べていました。結論としては今は使う理由がなさそうという残念な結果でした。
  • 競プロに使うという点では、実行時間にコンパイル時間が含まれるなどの理由で不利がついてしまう。
    • TLEしない程度の差なら使えないこともない…？
  • また、VSCodeのJuliaプラグインがあまり高性能ではなくテスト実行などが上手くできなかった。
    • Atomプラグインについては試していないのでそちらなら上手くいくかもしれない。
  • Kaggle（機械学習）に使うという面では、（ある程度以上の計算を行うなら）実行速度が速いらしいこと、PycallでPythonのライブラリを呼び出せることなどからソロでやるならば使い勝手は悪くなさそう。
    • KaggleのカーネルでJuliaがサポートされていないので自前の環境でなんとかする必要がある。
      • Google ColabでJuliaが使えたりするらしいので意外とどうにかなりそう。
      • カーネルのみ使用可能なコンペもあるようなのでその場合当然使えない。
    • チームでやる場合どうしてもPythonに比べてマイナーな言語なので問題が出ると思う。
      • 学習コストは高くなさそうなので頑張って布教すればチームでJuliaを使うことも可能…？