AtCoder

ABC308 C問題(Standings)を解く

AtCoder_ABC308_C

AtCoder が提供しているABC(AtCoder Beginner Contest)308 のC問題をC++とPythonで解いてみました。ABC308は、2023年7月1日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Standings(Difficulty : 605)

問題はリンク先をご覧ください。

ABC308 C問題 Standings

仮数部が大きい浮動小数点数を使うかソートで工夫する問題です。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 を使って解きました。この記事を書くことで、ソートの比較関数について学ぶことができました。

ABC308 について、引き続き問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA