AtCoder が提供しているABC（AtCoder Beginner Contest）389 C問題をC++とPythonで解いてみました。ABC389は、2025年1月18日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Snake Queue（Difficulty : 255）
問題の詳細は、リンク先をご覧ください。
累積和の値を更新することによってクエリを処理します。AtCoder Problems による Difficulty は 255 でした。
解答案
ヘビは最後尾に要素を追加するか、先頭の要素を削除する操作のみを行うため、要素の順序自体は変わりません。このため、ヘビの先頭の位置を累積和で求めておきます。
各クエリの処理は以下の通りです。
- クエリ1：累積和の末尾を更新します。
- クエリ2：累積和の左端のインデックス
leftを増やします。 - クエリ3：区間
[left, left + k - 1)の累積和を求めます。kの値を1減らしているのは、ヘビの先頭の位置を求めるためです（kの値は、ヘビの末尾の位置になります）。
C++ プログラム例（ABC389C）
上記の考察を実装しました。累積和の左端のインデックスを left、末尾のインデックスを right としました。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int q;
cin >> q;
vector<ll> s(q + 1, 0);
int left = 0;
int right = 0;
for (int i = 0; i < q; ++i) {
int type;
cin >> type;
if (type == 1) {
ll L;
cin >> L;
s[right + 1] = s[right] + L;
++right;
} else if (type == 2) {
++left;
} else if (type == 3) {
int k;
cin >> k;
cout << s[left + k - 1] - s[left] << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC389C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 389 C"""
q = int(input())
s = [0] * (q + 1)
left = 0
right = 0
for i in range(q):
queue = list(map(int, input().split()))
type = queue[0]
if type == 1:
L = queue[1]
s[right + 1] = s[right] + L
right += 1
elif type == 2:
left += 1
elif type == 3:
k = queue[1]
print(s[left + k - 1] - s[left])こちらも「AC」と判定されました。
最後に
累積和の応用問題でした。簡単ではありませんが、灰色レートに設定されていました。ABC参加者のレベルが高いことが伺えます。
引き続き ABC の問題を紹介していきます。
