AtCoder

ABC362 C問題(Sum = 0)を解く

AtCoder_ABC362_C

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

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

C問題 Sum = 0(Difficulty : 521)

問題の詳細は、リンク先をご覧ください。

ABC362 C問題 Sum = 0

初期値を最小値として、各要素を可能な限り増やしていきます。AtCoder Problems による Difficulty は 521 でした。

解答案

$\sum L_i > 0$ であれば、明らかに解はありません。同じように $\sum R_i < 0$ である場合も解はありません。

$\sum L_i \leqq 0 \leqq \sum R_i$ であることを前提とします。この場合、$X_i$ の初期値を $L_i$ とします。初期値では、$\sum X_i$ は 0 以下となります。それぞれの $X_i$ について、$\sum X_i$ が 0 になるまで値を増やします。それぞれの要素は、$R_i – L_i$ より値が増やせないことに注意します。

C++ プログラム例(ABC362C)

上記の考察をプログラムに変換します。

  • L[i]の総和が0を超えている、またはR[i]の総和が0未満の場合は、”No” を出力して終了します。
  • “Yes” を出力した後、配列 result の初期値を L にする。L の総和を remain とする(30ー32行目)。
    • result[i] に -remain を加える。ただし、R[i] – L[i] を上限とする。
    • remain を更新する。
  • 最後に result を出力します。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

int main()
{
	int n;
	cin >> n;
	vector<ll> L(n);
	vector<ll> R(n);
	ll sum_L = 0;
	ll sum_R = 0;
	for (int i = 0; i < n; ++i) {
		cin >> L[i] >> R[i];
		sum_L += L[i];
		sum_R += R[i];
	}

	if ((0 < sum_L)||(sum_R < 0)) {
		cout << "No" << endl;
		return 0;
	} else {
		cout << "Yes" << endl;
	}

	ll remain = sum_L;
	vector<ll> result = L;
	for (int i = 0; i < n; ++i) {
		ll d = min(R[i] - L[i], -remain);
		result[i] += d;
		remain += d;
	}

	for (int i = 0; i < n; ++i) {
		cout << result[i] << " \n"[i == n - 1];
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC362C)

Python版も基本的な考え方は同じです。プログラムを途中で終了するために sys.exit を呼び出しています。以下がプログラムです。

"""AtCoder Beginner Contest 352 C"""
import sys

n = int(input())
L = [0] * n
R = [0] * n
for i in range(n):
    L[i], R[i] = map(int, input().split())
sum_L = sum(L)
sum_R = sum(R)

if 0 < sum_L or sum_R < 0:
    print("No")
    sys.exit()
else:
    print("Yes")

remain = sum_L
result = L.copy()
for i in range(n):
    d = min(R[i] - L[i], -remain)
    result[i] += d
    remain += d

print(*result)

こちらも「AC」と判定されました。

最後に

この問題は、1時間程度考えましたが、結果的に解くことができませんでした。貪欲法に近いことを考えていましたが、いろいろ考えすぎていました。

引き続き ABC の問題を紹介していきます。

COMMENT

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

CAPTCHA