AtCoder ABC 128 B - Guidebook (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。D問題を記事にする予定でしたがB問題が結構難しかったので取り上げてみました。

簡単なC問題（ex.ABC127C）より難しい気がします。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

type restaurant struct {
    i int
    s string
    p int
}

type restaurants []restaurant

func (r restaurants) Len() int {
    return len(r)
}

func (r restaurants) Swap(i, j int) {
    r[i], r[j] = r[j], r[i]
}

func (r restaurants) Less(i, j int) bool {
    if r[i].s != r[j].s {
        return r[i].s < r[j].s
    }
    return r[i].p > r[j].p
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    var rest restaurants = make([]restaurant, n)
    for i := range rest {
        sc.Scan()
        rest[i].i, rest[i].s, rest[i].p = i+1, sc.Text(), nextInt()
    }
    sort.Sort(rest)

    for _, r := range rest {
        fmt.Println(r.i)
    }
}

問題の条件として、

市名が辞書順で早いものから紹介していく。

同じ市に複数レストランがある場合は、点数が高いものから紹介していく。

というものがあるため、直感的に解く場合にはソートが必要不可欠となります。そして市名の昇順ソートと点数の降順ソートの両方が求められること、最終的な出力として要求されるレストランの番号も保持しておかなければならないことにより複雑さが増しています。

とりあえずソートにより解く場合について考えます。この場合の方法としては大きく3通り考えられ、

市名（昇順）と点数（降順）との複合条件でソートを実装する。
まず点数（降順）でソートを行い、その後安定なソートアルゴリズムで市名（昇順）についてソートを行う。
市名に辞書順で昇順になるように文字列と対応させた点数を結合させてそれについてソートを行う。
- 例えば、0点→100、1点→099、…、100点→000といったように100の補数表現を3桁表記にする形で実装可能。

といった方法になります。公式解説や上記のコードは1つ目の複合条件によるソートとなります。~~思いついたから書いてみましたが3つ目の方法は説明が難しいですね。~~

公式解説によるとPair型を適切に使えば単純なソートで実装できるようですが、それを含めてもB問題の範疇を大きく超えてしまっているとは思います。

なお、別解としてソートを使わずひたすらループを回して次に出力するレストランを探し続けるやり方（計算量 $O(N^2)$ ）が紹介されています。こちらのやり方はまだB問題らしいと思いますが、問題文がソートを使うよう誘導してくる上に解説もソートで解くことを前提としているので、やはりC問題と間違えてるような気がします。

雑記

D問題も一応解いてはいますが、あまりにもゴリ押しが過ぎる~~のと対談記事も上げたい~~ので記事にするかは未定です。