今回はPythonでABC425をABCまで解くことができたので、その備忘録を纏めます。
コンテスト概要
AtCoder Beginner Contest 425
開催日:2025年9月27日 21:00-22:40
A - Sigma Cubes
入力Nに対して下記の場合を求める問題。
\sum^{N}_{i=1}(-1)^i × i^{3}
Nが偶数の場合と奇数の場合で場合分けを実施。
N = int(input().strip())
if N % 2 == 0:
k = N // 2
ans = k*k*(4*k + 3)
else:
k = (N - 1) // 2
ans = - (k+1)*(k+1)*(4*k + 1)
print(ans)
B - Find Permutation 2
N人の中でM問の問題全て解けた人の人数を解けた人の順番で出力する問題。
入力の形式が、『人Aが問題Bに正解した』という様に与えられる。
方針📝
入力値$P_{i}$が-1ではなかった場合、入力値$P_{i}$はすでにリスト$P$として使われているとする。そうした場合にリスト$P$が条件を満たせるかを考える。
N = int(input())
A = list(map(int,input().split()))
used = [False] * (N + 1)
for x in A:
if x != -1:
if used[x]:
print("No")
exit()
used[x] = True
re = [i for i in range(1, N+1) if not used[i]]
ri = 0
P = []
for x in A:
if x == -1:
P.append(re[ri])
ri += 1
else:
P.append(x)
print("Yes")
print(*P)
C - Rotate and Sum Query
方針📝
1. 回転操作(1 c：先頭を末尾へc回転移動)
配列全体を物理的に動かす必要はなく、配列の先頭が元の配列のどのインデックスを指しているかを記録
2.累積和の活用（prefix sum）
preを先に作っておくことで、任意の「元配列における連続区間」の和を$O(1)$でも止めることができる。
3.回転による区間の特定
回転によって現在のl..rが元配列上で連続区間になるかどうかを判定して、preを使って和を計算する。
累積和の算出
pre[k]をA[0]+...+A[k-1]にする。長さはN+1(pre[0]=0)
pre = [0] * (N+1)
for i in range(N):
pre[i+1] = pre[i] + A[i]
shiftの算出と更新
shiftは左回転（先頭を末尾へ）した合計回数＝mod N
shift = 0
ans = []
クエリ処理①
回転クエリ
左にc回回すのでオフセットを増やす。
%Nとすることでc>=Nでも正しく扱う。
for _ in range(Q):
query = list(input().split())
if query[0] == "1":
c = int(query[1])
shift = (shift + c) % N
クエリ処理②
出力クエリ
現在の配列の位置lが元配列のどの index かを計算する。
-
start <= endのときは元配列上で連続区間なので通常のpre差で求める。 -
start > endのときは区間が末尾 → 先頭に跨っているので、
pre[N] - pre[start]＋pre[end+1]で合算する。pre[0]は 0 なので省略可。
else:
l, r = int(query[1]), int(query[2])
start = (shift + l - 1) % N
end = (shift + r - 1) % N
if start <= end:
res = pre[end+1] - pre[start]
else:
res = (pre[N] - pre[start]) + (pre[end+1]-pre[0])
ans.append(res)
全体像
N, Q = map(int,input().split())
A = list(map(int, input().split()))
pre = [0] * (N+1)
for i in range(N):
pre[i+1] = pre[i] + A[i]
shift = 0
ans = []
for _ in range(Q):
query = list(input().split())
if query[0] == "1":
c = int(query[1])
shift = (shift + c) % N
else:
l, r = int(query[1]), int(query[2])
start = (shift + l - 1) % N
end = (shift + r - 1) % N
if start <= end:
res = pre[end+1] - pre[start]
else:
res = (pre[N] - pre[start]) + (pre[end+1]-pre[0])
ans.append(res)
for i in range(len(ans)):
print(ans[i])
結果
ABC 3完
順位 3937th / 10211
パフォーマンス 763
レーティング 1048 → 1017 (-31)
感想
またしてもパフォーマンスが茶色となってしまいました。このままだと緑維持も危うい…。今週はpaizaの基礎的な問題に手をつけていたので、早解きはできるんじゃないかと思います。一旦緑パフォを目指します。