AtCoder

ABC281 C問題(Circular Playlist)を解く

AtCoder_ABC281_C

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

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

C問題 Circular Playlist(Difficulty : 131)

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

ABC281 C問題 Circular Playlist

数列の合計の剰余を使って計算する問題です。AtCoder Problems による Difficulty は、131 でした。ABC C問題としては、取り込みやすい難易度の問題です。

解答案

問題を解く方針を書きだします。

  • N と T 、数列 A を読み込む。
  • 数列 A のすべての合計を求めて、T との剰余を求める。
  • 剰余から数列の各項 Ai を引いて、解答を求める。

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

数列全体の合計、および求めた剰余から数列の各項を引く代わりに、累積和を求めて解きました。計算量的には、一度しか計算しないため、各項を引いていく場合と差はありません。累積和はパターンを決めて書いているため、速く書けました。

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

typedef unsigned long long int ull;

int main()
{
	ull n, t;
	cin >> n >> t;
	vector<ull> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<ull> s(n+1, 0);
	for (int i = 0; i < n; ++i) {
		s[i+1] = s[i] + a[i];
	}

	ull result = t % s[n];
	for (int i = 1; i <= n; ++i) {
		if (result < s[i]) {
			cout << i << " " << result - s[i - 1] << endl;
			break;
		}
	}

	return 0;
}

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

Python プログラム例(ABC281C)

Python 版も、累積和を使った C++ 版をそのまま書き直しました。

"""AtCoder Beginner Contest 281 C"""
n, t = map(int, input().split())
a = list(map(int, input().split()))
s = []
s.append(0)
for i in range(n):
    s.append(s[i] + a[i])

result = t % s[n]
for i in range(1, n + 1):
    if result < s[i]:
        print(i, result - s[i - 1])
        break

こちらも「AC」と判定されました。Python らしい書き方になっているか自信はありません。

最後に

C問題としては、やや簡単な問題だと思います。計算量的には、累積和を使う必要はなかったのですが、決まったコードパターンを使うことにより、添え字の1個違いなどのミスを減らすことができると考えています。

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

COMMENT

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

CAPTCHA