AtCoder が提供しているABC（AtCoder Beginner Contest）352 のC問題をC++とPythonで解いてみました。ABC352は、2024年5月4日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Standing On The Shoulders（Difficulty : 136）
問題はリンク先をご覧ください。
ABC352 C問題 Standing On The Shoulders
一番頭（？）が大きい巨人を探すことに帰着します。AtCoder Problems による Difficulty は 136 でした。
解答案
一番上にいる巨人の肩の高さは、巨人の積み上げ順に関係ありません。結果的に頭の高さ $B_i$ と肩の高さ $A_i$ の差が一番大きい巨人が一番上になった場合に、最大の高さとなります。
C++ プログラム例（ABC352C）
頭の高さを読みながら、肩の高さの合計 a_sum を求めておきます。この高さに b[i] – a[i] の最大値を加えたものが解となります。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<ll> a(n), b(n);
ll a_sum = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
a_sum += a[i];
}
ll result = 0;
for (int i = 0; i < n; ++i) {
result = max(result, a_sum - a[i] + b[i]);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC352C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 352 C"""
n = int(input())
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
for i in range(n):
a[i], b[i] = map(int, input().split())
a_sum = sum(a)
result = 0
for i in range(n):
result = max(result, a_sum - a[i] + b[i])
print(result)こちらも「AC」と判定されました。
最後に
最大で20万人の巨人が肩に立つと、まぁ崩れると思います。設定が面白い問題でした。
引き続き ABC の問題を紹介していきます。
