AtCoder ABC 308: C - Standings を解く書き方8+1個(PythonとC++) ソート比較演算子あれこれ

Pypy3: Classを作って解く

classに__lt__を作ります。

class frac:
    def __init__(self, a, b, ind):
        self.a, self.b, self.ind = a, b, ind
    def __lt__(self, other): #<
        if(self.a * other.b > other.a * self.b): return True
        if(self.a * other.b < other.a * self.b): return False
        return self.ind <= other.ind
import sys
read = sys.stdin.read
n = int(input())
dat, ans = [], []
for i in range(n):
    a, b = map(int, input().split())
    dat.append( frac(a, b, i+1))
dat.sort()
for x in dat: ans.append(x.ind)
print(*ans)

Python: Decimalで解く(Pypy3はTLE)

decimal --- 十進固定及び浮動小数点数の算術演算は小数をfloatより正確に扱えます。
ただし、遅いことと、Pypyでは極端に遅くなることに注意します。

同じコードでPypy3でTLEする例

import decimal
n = int(input())
dat,ans = [], []
for i in range(n):
    a, b = map(decimal.Decimal, input().split())
    dat.append( (-a / (a+b), i+1) )
dat.sort()
print(*[dat[i][1] for i in range(n)])

Pypy3: Fractionで解く(input高速化, sort手抜き)

Fractionで解きます。ただし、私の場合は以下の高速化をしないとTLEしてしまいました。

• 入力をsys.readによる高速一括読み込み
• sortで0だけを評価対象にする。もともとのデータがlistでindexはsortedなので[0]だけ評価すれば[1]もsortedになっている
  後者は不本意なのですがいろいろ試してもsortを[0]だけにしないと通りませんでした。

C++: 実はlong doubleで良い

    vector<pair<long double, int>> d;
    REP(i, n){
        long double a, b; cin >> a >> b;
        d.push_back({-a/(a+b), i+1});
    }
    sort(d.begin(), d.end());

C++: structを定義し、struct内でoperatorを定義

struct frac{
    long long a, b, i;
    inline bool operator<(const frac &r){
        if( (a * r.b - b * r.a) < 0) return false;
        if( (a * r.b - b * r.a) > 0) return true;
        return i < r.i;
    }
};

C++: structを定義し、外でoperatorを定義

struct frac{ long long a, b, i; };
bool operator<(const frac &l, const frac &r){
    if( (l.a * r.b - l.b * r.a) < 0) return false;
    if( (l.a * r.b - l.b * r.a) > 0) return true;
    return l.i < r.i;
}

C++: structを定義し、sortにユーザ定義ソート関数を渡す

    struct frac{ long long a, b, i; };
    auto cmp = [](const frac &l, const frac &r){
        if( (l.a * r.b - l.b * r.a) < 0) return false;
        if( (l.a * r.b - l.b * r.a) > 0) return true;
        return l.i < r.i;
    };
    sort(d.begin(), d.end(), cmp);

C++: structを定義し、sortにラムダ式を直接書く

    struct frac{ long long a, b, i; };
    sort(d.begin(), d.end(), [](const frac &l, const frac &r){
        if( (l.a * r.b - l.b * r.a) < 0) return false;
        if( (l.a * r.b - l.b * r.a) > 0) return true;
        return l.i < r.i; });

供養: C++: __int128でstructを作って解く

問題を勘違いしlong longに収まらない演算だと思ったので__int128で扱うことにしました。供養のために置いておきます。