前回の振り返り
今日はABC440開催日だったので参加結果を振り返る
今週はA,B,C,Dの4完(0ペナ)
A
Xに2のY乗をかける
ソースコード
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():
X, Y = rLI()
ans = X * 2 ** Y
print(ans)
if __name__ == '__main__':
main()
B
TをkeyにしてA=[1,2,...,N]をソート
ソースコード
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()
T = rLI()
A = list(range(1,N+1))
B = list(sorted(A,key=lambda x:T[x-1]))
ans = B[:3]
print(*ans)
if __name__ == '__main__':
main()
C
0<=x<2*Wのなかで
C[i]が加算されるのは区間として決められるので
imos法をやる
ソースコード
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():
T = rI()
for _ in range(T):
N, W = rLI()
C = rLI()
M = 2 * W
D = [0] * (M + 1)
for i, c in enumerate(C):
l = (-i) % M
r = (l + W - 1) % M
if W == 0:
continue
if l <= r:
D[l] += c
D[r + 1] -= c
else:
D[l] += c
D[M] -= c
D[0] += c
D[r + 1] -= c
S = list(accumulate(D[:-1]))
ans = min(S)
print(ans)
if __name__ == '__main__':
main()
D
Aをソートして
適当な値を選び
X以上でAで含まれない数を二分探索で探す
また更に、その数がYになるように二分探索。
ソースコード
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, Q = rLI()
A = rLI()
A.sort()
for _ in range(Q):
X, Y = rLI()
l = X
r = X+Y+N+100
mx = bisect_left(A, X)
while l<r:
m = (l+r)//2
mi=bisect_right(A,m)
c = mi-mx
d = m-X+1-c
if d >= Y:
r = m
else:
l = m+1
ans = l
print(ans)
if __name__ == '__main__':
main()
E
N <= 50だからDP行けるかもとか思いつつ
普通にKとかXが大きい数だったので
計算量を減らすことができず時間切れ
全然見当違いだったようだ
F
配列の値1つだけ書き換えるならセグ木？でもどう乗せるかは思いつかなかった
G
あけましてハッピーハロウィン🎃は笑う
感想
今回も無事にD問題まで解くことができた
なにげに初の水perf取った