ARC 008 C - THE☆たこ焼き祭り2012(Go) - あるエンジニアのAtCoder奮闘記

irisruneです。明日からGWです、休みの人もそうでない人も充実した10日間を過ごせればよいですね。

なんと6年以上前の問題です。タイトルから問題文まで突っ込みどころが多すぎますが、推定難易度532点相当らしいです。

package main

import (
    "fmt"
    "math"
    "sort"
)

const INF = 1000000000.0

type person struct {
    x float64
    y float64
    t float64
    r float64
}

func time(thrower, receiver person) float64 {
    d := math.Sqrt(math.Pow((thrower.x-receiver.x), 2.0) + math.Pow((thrower.y-receiver.y), 2.0))
    v := math.Min(thrower.t, receiver.r)
    return d / v
}

func dijkstra(adj [][]float64, dt []float64, n int) {
    visited := make([]bool, n)
    s := 0
    dt[s] = 0.0
    visited[s] = true
    for {
        for i, v := range visited {
            if v {
                continue
            }
            dt[i] = math.Min(dt[i], dt[s]+adj[s][i])
        }

        next := -1
        minT := INF
        for i, v := range visited {
            if v {
                continue
            }
            if dt[i] < minT {
                next = i
                minT = dt[i]
            }
        }

        if next == -1 {
            break
        }
        visited[s] = true
        s = next
    }
}

func main() {
    var n int
    fmt.Scan(&n)
    people := make([]person, n)
    for i := range people {
        fmt.Scan(&people[i].x, &people[i].y, &people[i].t, &people[i].r)
    }

    adj := make([][]float64, n)
    for i := range adj {
        adj[i] = make([]float64, n)
    }

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            adj[i][j] = time(people[i], people[j])
        }
    }

    dt := make([]float64, n)
    for i := range dt {
        dt[i] = INF
    }
    dijkstra(adj, dt, n)

    sort.Sort(sort.Reverse(sort.Float64Slice(dt)))
    maxT := 0.0
    for i, t := range dt {
        if i == n-1 {
            break
        }
        maxT = math.Max(maxT, t+float64(i))
    }
    fmt.Println(maxT)
}

問題文や制約は少し長いですが解き方は単純で、

たこ焼きを投げる人と受け取る人のペアすべてについて、たこ焼きを投げるのにかかる時間を求める。
『あなた』から他の参加者すべてに対して、（他の参加者を経由して）たこ焼きを投げるのにかかる時間を求める。
2.の結果を降順にソートする。
3.についてたこ焼きを投げるのにかかる時間が長い人から順番にたこやきを投げるシミュレーションを行う。

つまり（有向）グラフの最短経路問題に集約されます。同じ人はたこ焼きを1秒に1個しか投げられないという条件はありますが、『あなた』からある参加者にたこ焼きを投げるのにかかる時間は（最短経路を使う限り）常に一定のため、この条件は『あなた』についてのみ考えればよいです。

計算量についてですが、今回のグラフは有向多重完全グラフとでもいうべき代物なので（有向）辺の本数が $N(N-1)$ 本にも及びます。そのためダイクストラ法などで最短経路を求めるのに $O(N^2)$ 時間かかってしまいます。そもそも（有向）辺の長さを求める（隣接行列を作成する）時点で $O(N^2)$ 時間かかるとは思いますが…

間違っても最短経路の最大値をそのまま解としてはいけません（親切にも入力例1が反例となっています）。

コードレビュー

ダイクストラ法のループ回数はで決まっているはずなので無限ループを使うのはあまりよくないと思う。
- この書き方すると割とよくbreak忘れます。
- アルゴリズムだけ覚えて自己流でコード書いてるので他の人の実装を参考にしてもよさそうですね。
『あなた』から他の参加者にたこ焼きを投げるシミュレーションを行う部分で『あなた』自身へ投げる手順を除外する処理について。
- 末尾要素をスキップするためだけに毎回条件分岐をかけるのはあまりよくはないですね。
  - rangeを使わずにループ幅を決める
  - ループの前に末尾要素（『あなた』自身へ投げる時間）を除外する
    - Goのスライスを使っているので計算コストもかからないしこっちの方がわかりやすいですね。

雑記

GW中はブログの更新を停止します。
GW中は螺旋本や蟻本辺りをやるかRustをやるかKaggleに取り組んでみるか考え中です。