どうもこんにちは！
今週のコンテストはCまで完答、振り返りもCまで。
Bまで解き終わるにも30分かかるわ、C問題は難しく考えすぎて解けたのは終了3分前という感じでした。。
問題と公式の解説のリンク
問題は以下のリンクから。
A - Sigma Cubes -
問題
与えられたnに対して、$\sum^n_{i=1}(-1)^i * i^3$を出力する問題。
考え方とコード
for文でそのまま計算しました。
n = int(input())
ans = 0
for i in range(1,n+1):
ans += (-1)**i * i**3
print(ans)
B - Find Permutation 2 -
問題
長さNの数列が与えられます。この数列の値は-1か1以上N以下の整数です。
この数列の-1の値を1以上N以下でかつ数列に含まれていない値に置き換えたとき、数列は1,2,3,…,Nを並び替えた数列になるかを判定し、並び替えた数列になるなら1例を出力する問題。
考え方とコード
1からNの値を並び替えた数列になるということは、数列内に-1以外の値が1つだけある場合です。
まずはこれを判定し、あとは数列内に含まれている数字をピックアップして、-1のところに含まれていない数字を埋めていくとしました。
n = int(input())
s = [int(x) for x in input().split()]
for i in range(1,n+1):
if s.count(i) > 1:
print("No")
exit(0)
count = []
for i in range(n):
if s[i] != -1:
count.append(s[i])
for i in range(n):
if s[i] == -1:
for j in range(1,n+1):
if j not in count:
s[i] = j
count.append(j)
break
if s.count(-1) > 0:
print("No")
else:
print("Yes")
print(*s)
C - Rotate and Sum Query -
問題
長さNの数列とQ個のクエリが与えられます。クエリの内容は以下です。
- 与えられたcを使って、数列の先頭の要素を末尾に移動させる操作をc回行う
- 与えられたl,rを使って、$\sum^r_{i=l}A_i$を出力する
数列の要素数の最大とクエリ数の最大はともに$2×10^5$です。
考え方とコード
まず、数列を2つつなぎあわせて累積和を作ります。例えば数列が3 1 4 5なら、3 1 4 5 3 1 4 5の累積和を作ります。
先頭要素を末尾に移動させるクエリが来るたびに、最新の数列の先頭位置を保持します。
値を出力するクエリが来るたびに、この累積和から計算して出力するとしました。別のクエリにより先頭がずれているぶんだけ、累積和の取る位置もずらせばOKです。
・・・と思いついたのが終了5分ほど前でした。。
それまではクエリが来るたびに累積和を作るようにしていたのでTLEになっていて、どつぼにはまっていました。
n,m = map(int,input().split())
a = [int(x) for x in input().split()]
a *= 2
s = [0] * (2*n+1)
for i in range(n*2):
s[i+1] = s[i] + a[i]
l = 0
for _ in range(m):
tmp = [int(x) for x in input().split()]
if tmp[0] == 1:
l = (l + tmp[1]) % n
else:
print(s[tmp[2]+l]-s[tmp[1]+l-1])
ではでは。