AtCoder が提供しているABC（AtCoder Beginner Contest）348 のB問題をC++とPythonで解いてみました。ABC348は、2024年4月6日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Farthest Point（Difficulty : 79）
問題はリンク先をご覧ください。
すべての相異なる点の距離を求めて、解くことができます。AtCoder Problems による Difficulty は 79 でした。
解答案
C++ プログラム例（ABC348B）
$i$ 番目の点に対して、それと異なるすべての $j$ 番目の点に対して距離を求めて、その最大値を表示します。
距離を求めるために sqrt 関数は呼び出していません。逆に呼び出すのは好ましくありません。浮動小数点の演算には、誤差が発生するためです。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> x(n), y(n);
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
}
for (int i = 0; i < n; ++i) {
int max_index = -1;
int max_dis2 = -1;
for (int j = 0; j < n; ++j) {
if (i == j) {
continue;
}
int dis2 = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
if (dis2 > max_dis2) {
max_index = j + 1;
max_dis2 = dis2;
}
}
cout << max_index << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC348B）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 348 B"""
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
x[i], y[i] = map(int, input().split())
for i in range(n):
max_index = -1
max_dis2 = -1
for j in range(n):
if i == j:
continue
dis2 = (x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2
if dis2 > max_dis2:
max_index = j + 1
max_dis2 = dis2
print(max_index)こちらも「AC」と判定されました。
最後に
A問題やB問題は、すべての場合について計算できる場合が多いようです。
引き続き ABC の問題を紹介していきます。
