AtCoder が提供しているABC（AtCoder Beginner Contest）281 のC問題をC++とPythonで解いてみました。ABC281は、2022年12月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Circular Playlist（Difficulty : 131）
問題はリンク先をご覧ください。
数列の合計の剰余を使って計算する問題です。AtCoder Problems による Difficulty は、131 でした。
解答案
問題を解く方針を書きだします。
- 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 の問題を紹介していきます。
