AtCoder が提供しているABC（AtCoder Beginner Contest）308 のC問題をC++とPythonで解いてみました。ABC308は、2023年7月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Standings（Difficulty : 605）
問題はリンク先をご覧ください。
仮数部が大きい浮動小数点数を使うかソートで工夫する問題です。AtCoder Problems による Difficulty は 605 でした。
解答案
この問題は、(ai/(ai+bi), i) をソートすれば解決します。
- 解法1
浮動小数点数としてソートします。倍精度浮動小数点数の仮数部は53ビットです。この精度では、足りないように問題の制約が設定されています。それより仮数部が大きい浮動小数点数を使います。 - 解法2
有理数としてソートします。ソート関数の比較関数を設定します。
C++ プログラム例（ABC308C）
解法1 long doule を使う。
double では仮数部（53ビット）の精度が足りません。AtCoder の環境では、long double の仮数部は64ビットです。long double を使えば精度が足ります。浮動小数点数の精度については、このユーザ解説で詳しく説明されています。
実際のプログラムでは、ソートの替わりに set を使いました。成功率の高い順に並べる必要があるため、マイナスをつけて set コンテナに格納しています（19行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long double ld;
int main()
{
int n;
cin >> n;
vector<ull> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
set<pair<ld, int>> s;
for (int i = 0; i < n; ++i) {
ld p = (ld)a[i] / ((ld)a[i] + (ld)b[i]);
s.insert(make_pair(-p, i + 1));
}
for (auto e : s) {
cout << e.second << " ";
}
cout << endl;
return 0;
}解法2 比較関数を作って有理数をソートする。
有理数として比較すれば、浮動小数点数のような評価が難しい精度の問題は発生しません。
sort 関数の第3引数に、比較する関数を指定することができます。
- 配列の型 pair<pair<ull, ull>, int> を pp として型定義しておきます（5行目）。
- 関数 cmp が比較関数です。引数として要素を2つ取ります（7ー21行目）。
- 有理数として等しければ、添え字の大きさを比較する（17行目）。
- 有理数として異なれば、その大きさを比較する（19行目）。
- 補足：有理数は降順で、添え字は昇順となるように評価式を設定しています。
- sort の第3引数で比較関数 cmp を指定します（36行目）。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef pair<pair<ull, ull>, int> pp;
bool cmp(pp d1, pp d2)
{
ull a1 = d1.first.first;
ull b1 = d1.first.second;
ull a2 = d2.first.first;
ull b2 = d2.first.second;
int i1 = d1.second;
int i2 = d2.second;
if (a1 * b2 == a2 * b1) {
return i1 < i2;
} else {
return a1 * b2 > a2 * b1;
}
}
int main()
{
int n;
cin >> n;
vector<ull> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
vector<pp> d;
for (int i = 0; i < n; ++i) {
d.push_back(make_pair(make_pair(a[i], a[i] + b[i]), i + 1));
}
sort(d.begin(), d.end(), cmp);
for (int i = 0; i < n; ++i) {
cout << d[i].second << " \n"[i == n - 1];
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC308C）
Python の内部表現を把握できていないため、比較関数を使って有理数をソートします。
functools.cmp_to_key で比較関数を指定できます（2、23行目）。ソートするリストの要素はタプルにしました。
Python（3.8.2）では、実行時間が1900msecより大きくなりました。この問題の時間実行制限は2000msecなので、時間的に余裕がありませんでした（PyPy3（7.3.0）の実行時間は1600msec前後でした）。
"""AtCoder Beginner Contest 308 C"""
from functools import cmp_to_key
def cmp(d1, d2):
a1, b1, i1 = d1
a2, b2, i2 = d2
if a1 * b2 == a2 * b1:
return i1 - i2
return a2 * b1 - a1 * b2
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
a[i], b[i] = map(int, input().split())
d = []
for i in range(n):
d.append((a[i], a[i] + b[i], i + 1))
d.sort(key=cmp_to_key(cmp))
print(*[i for a, b, i in d])こちらも「AC」と判定されました。
最後に
この問題は、やりたいことは明確でした。一方、浮動小数点数の精度の知識、または sort の比較関数を自分で実装する必要があるため、難易度が上がった気がします。
コンテストでは long double を使って解きました。この記事を書くことで、ソートの比較関数について学ぶことができました。
引き続き ABC の問題を紹介していきます。
