AtCoder Beginner Contest 308 C - Standings

AtCoderをやり始めた。 全然問題が解けないので、復習する。

atcoder.jp

問題

$1$から$N$の番号が付いた$N$人がコイントスを何回かしました。人$i$は$A_i$回表を出し、$B_i$回裏を出したことが分かっています。 人$i$のコイントスの成功率は$\dfrac{A_i}{A_i+B_i}$で定義されます。人$1,...,N$の番号を、成功率の高い順に並び替えよ。 成功率が同じ人が複数いる場合、その中では人の番号が小さい順になるように並び替えよ。

制約

• $ 2 \leq N \leq 2 \times 10^{5} $
• $ 0 \leq A_i、B_i \leq 10^{9} $
• $ A_i + B_i \geq 1 $
• $ 入力される数値はすべて整数 $

解き方

この問題、簡単そうに見えて難しい。実際、解けなかった。。。

素直に、成功率を$\dfrac{A_i}{A_i+B_i} \lt \dfrac{A_j}{A_j+B_j}$で比較すると、まず通らない。。。

floatで比較すると落ちるケースが入っているため、分母を落として、int64で比較するのが良いらしい。

分母を落とすと$A_i({A_j+B_j}) \lt A_j({A_i+B_i})$で比較できる。

あとは、成功率が同じ場合、番号で比較した結果を入れることに注意する。

標準入力もbufio.Scannerを使う方がfmt.Scanfより早いとのことなので、今後はこちらを使っていくようにする。

正しい解

package main

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

var sc *bufio.Scanner

type person struct {
    id, a, b int
}

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

    N := scanInt()
    p := make([]person, N)
    for i, _ := range p {
        p[i].id = i + 1
        p[i].a, p[i].b = scanInt(), scanInt()
    }

    sort.Slice(p, func(i, j int) bool {
        n := p[i].a*(p[j].a+p[j].b) - p[j].a*(p[i].a+p[i].b)
        if n == 0 {
            return p[i].id < p[j].id
        }
        return n > 0
    })

    ans := make([]string, 0, N)
    for _, v := range p {
        ans = append(ans, strconv.Itoa(v.id))
    }
    fmt.Println(strings.Join(ans, " "))
}

func scanInt() int {
    sc.Scan()
    i, _ := strconv.Atoi(sc.Text())
    return i
}