前回の振り返り
今日はABC開催日だったので参加結果を振り返る
今週はD,Eの2完(!?)
A
剰余の計算ミスってWAして後回しにしたらとき損ねた
B
愚直にBFSもどきしたらTLEだした
C
D,E解いたあとに
愚直回答つくった瞬間にのこり30秒となって慌てて提出した
当然TLEだった
D
A,B,Cの累積和sA,sB,sCをつかって考えると切る位置x,yを使って
A[0..x] = sA[x]
B[x+1..y] = sB[y] - sB[x]
C[y+1..] = sC[N-1] - sC[y]（ここを tC - sC[y] と置く）
をまとめると
s=sA[x]+(sB[y]−sB[x])+(tC−sC[y])
が建てられる
これを並べ替えると
s=tC+(sA[x]−sB[x])+(sB[y]−sC[y])
ここで、x と y が 足し算で分離できる点に注目する。
y を固定すると、必要なのはx<yの中で(sA[x]−sB[x])の最大値だから、
D[x] = sA[x] - sB[x]
xD[i] = max(D[0..i])
を作っておけば、
各 y で xD[y−1]+sB[y]+tC−sC[y]
の最大値を探索するループを回せばOK。
ソースコード
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
N = rI()
A = rLI()
B = rLI()
C = rLI()
sA = list(accumulate(A))
sB = list(accumulate(B))
sC = list(accumulate(C))
tC = sC[-1]
xD = [0]*(N)
xM = -float('inf')
for i in range(N):
d = sA[i] - sB[i]
err(d,sA[i],sB[i])
xM = max(xM,d)
xD[i] = xM
ans = 0
for y in range(1,N-1):
x = xD[y-1] + sB[y]
c = tC - sC[y]
s = x + c
ans = max(ans,s)
print(ans)
if __name__ == '__main__':
main()
E
バケツの行方とバケツの水の量をダブリングで管理する。
10＾9オーダーなのでKは30ぐらいでも良かったかも
ソースコード
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import math
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
N, Q = rLI()
A = rLI1()
K = 60
db = [[0]*N for _ in range(K)]
dv = [[0]*N for _ in range(K)]
db[0] = A[:]
dv[0] = list(range(1,N+1))
for k in range(1,K):
for n in range(N):
db[k][n] = db[k - 1][db[k - 1][n]]
dv[k][n] = dv[k - 1][n] + dv[k - 1][db[k - 1][n]]
# for k in range(K):
# err(k)
# err(db[k])
# err(dv[k])
for _ in range(Q):
t, b = rLI()
b -= 1
now = b
ans = 0
i = 0
while t:
if t & 1:
ans+= dv[i][now]
now = db[i][now]
t >>= 1
i += 1
print(ans)
if __name__ == '__main__':
main()
感想
A,Bを軽く沼りかけて即ブッチして
Cも一旦とばしてD,Eを解いたら
D,Eの2完とかいう訳解んない成績になってしまった。
即ブッチの判断は是非もそうだし
CはともかくA,Bももうすこし丁寧にやり直せたら時間内に解けたかもしれないと考えると
この判断ってどっちが良かったのだろうか。