[ABC425] ABC 425(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
合計回答時間：80分
A問題
自分の回答
かかった時間：2分
N = int(input())
result = 0
for i in range(1,N+1):
result += (-1)**i * i**3
print(result)
終了後考えた最適な回答
N = int(input())
result = 0
for i in range(1,N+1):
result += (-1)**i * i**3
print(result)
B問題
自分の回答
かかった時間：40分
permutationを知らなくてかなり時間がかかってしまった
N = int(input())
A = list(map(int,input().split()))
# -1でない数字の部分はA[i] = P[i]にする
P = [0]*N
for i in range(N):
if A[i] != -1:
P[i] = A[i]
# リスト内に重複がある場合は即座にNoを出力
for i in range(1,N+1):
count_P = P.count(i)
if count_P > 1:
print('No')
exit()
# すでに存在する数字の部分はそのままで他のところに先頭から数字を追加
check = []
for i in range(1,N+1):
if i not in P:
check.append(i)
for i in range(N):
if P[i] == 0 and len(check) >= 1:
P[i] = check[0]
check.pop(0)
print('Yes')
print(*P)
終了後考えた最適な回答
from itertools import permutations
n = int(input())
a = list(map(int, input().split()))
# [(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)]
for p in permutations([i + 1 for i in range(n)]):
ok = True
for i in range(n):
ok = ok and a[i] == -1 or p[i] == a[i]
if ok:
print("Yes")
print(*p)
break
else:
print("No")
C問題
自分の回答
TLEを無視した実装は素早くできたが、考慮した実装が最後まで完成できなかった。
for文のO(Q)と配列のコピーO(N)で(2×10^5)×(2×10^5)＝(4×10^10)となり、TLEとなる。
かかった時間：40分
N,Q = map(int,input().split())
A = list(map(int,input().split()))
for i in range(Q):
q = list(map(int,input().split()))
# q[0]が1の場合はAの先頭の要素を末尾に移動させる操作をc回行う。
if q[0] == 1:
c = q[1]
A = A[c:N]+A[0:c]
if q[0] == 2:
l = q[1]
r = q[2]
print(sum(A[l-1:r]))
終了後考えた最適な回答
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
a = list(map(int, input().split()))
# 4回転すると元の配列にもどるため、２倍にすることで回転を開始位置のシフトとして表現することができる
b = a + a
print(b)
# 後ろから回すことでi移行の要素の合計を知れる
for i in range(2 * n - 1, 0, -1):
print(b[i - 1],b[i])
b[i - 1] += b[i]
print(b)
# [26, 23, 22, 18, 13, 10, 9, 5]
rui_c = 0
for _ in range(q):
query = list(map(int, input().split()))
if query[0] == 1:
c = query[1]
rui_c = c
rui_c %= n
else:
l, r = query[1] - 1, query[2]
# l = 1-1,r = 3
# b[0] = 26,
# b[3] = 18
print(b[l + rui_c] - b[r + rui_c])
次に向けてやること
・425 C問題の復習
・累積和の勉強
感想
B問題に実装がかかっているは良くない、知らない文法やライブラリが出てきたら勉強する