AtCoderBeginnerContest308 C 問題 300 点 「Standings」

問題リンク

問題概要

制約

解法

単純に$\frac{A\i}{A_i + B_i}$でソートしようとすると，浮動小数点数の誤差でエラーになる。 そのため，問題文を以下のように考えて並べ替えることで，誤差を気にする必要がなくなる。 \(A_i(A_j + B_j) \le A_j(A_i + B_i)\) このような比較時の関数は Python だと作るのが面倒だと思っていたが，functool.cmp_to_keyで結構簡単にできた。

お気持ち

AC コード

from functools import cmp_to_key


def cmp(a, b):
    if a[0] * (b[0] + b[1]) <= b[0] * (a[0] + a[1]):
        return 1
    else:
        return -1


N = int(input())
AB = [list(map(int, input().split())) + [i] for i in range(N)]
AB.sort(key=cmp_to_key(cmp))
ans = []
for *_, i in AB:
    ans.append(i + 1)
print(*ans)

Rust 版

#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(dead_code)]
#![recursion_limit = "1024"]
use std::collections::{vec_deque, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::f64::consts::PI;
use std::mem::swap;
use std::process::exit;
use std::{isize, println};

use itertools::{CombinationsWithReplacement, Itertools};
use num::{integer::Roots, traits::Pow, ToPrimitive};
use num_integer::{div_ceil, Integer};
use num_traits::{abs_sub, Float};
use permutohedron::Heap;
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::io::*;
use whiteread::parse_line;
//

fn solve() {
    input! {
        N:usize,
        AB:[(isize, isize); N]
    }
    let mut V = vec![];
    for (i, &(a, b)) in AB.iter().enumerate() {
        V.push((a, a + b, i));
    }
    V.sort_by(|a, b| (-a.0 * b.1).cmp(&(-a.1 * b.0)));
    println!("{}", V.iter().map(|a| a.2 + 1).join(" "));
}

fn main() {
    // input! {N:usize}
    // for _ in 0..N {
    //     solve();
    // }
    solve();
}