前回の振り返り
今日はABC383開催日だったので参加結果を振り返る
今週はA,B,Dの3完(1ペナ)…終了直後にCをAC😅
A
水がマイナスにならないように減らしながら加える。
最後水足したあとは減らないので注意。
ソースコード
main.py
import sys
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())
def err(*args): print(*args, file=sys.stderr)
def main():
N = rI()
T0, V0 = rLI()
ans = V0
for _ in range(N-1):
T, V = rLI()
ans = max(0,ans-(T-T0))
ans += V
T0 = T
print(ans)
if __name__ == '__main__':
main()
B
grid問題つらい…
まだB問題だから総当たりで解いても大丈夫
しかし実装に時間かかった😇
ソースコード
main.py
from itertools import combinations, product
import sys
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())
def err(*args): print(*args, file=sys.stderr)
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
def out_of_bounds(y, x, h, w):
return y < 0 or y >= h or x < 0 or x >= w
def main():
H, W, D = rLI()
grid = [[] for i in range(H)]
floors = []
for i in range(H):
grid[i] = list(rS())
# err(grid[i])
for j,s in enumerate(grid[i], start=0):
if s==".":
floors.append((i,j))
ans = 2
X = [(i,j) for i, j in product(range(-D,-~D),repeat=2) if abs(i) + abs(j) <= D]
# for x in X:
# err(x,sum(map(abs,x)))
# err(floors)
for a0,b0 in combinations(floors,2):
humided = {a0,b0}
cnt = 2
for c0 in [a0,b0]:
for i,j in X:
ci0,cj0 = c0
ci, cj = (ci0+i,cj0+j)
c = ci,cj
if out_of_bounds(ci,cj,H,W) or grid[ci][cj] == "#": continue
if c not in humided:
cnt += 1
humided.add(c)
if cnt > ans:
# err(a0,b0,cnt,humided)
ans = cnt
print(ans)
if __name__ == '__main__':
main()
C
またgrid問題…やめてください4んでしまいます
Hが入っている頂点からBFSをする発想はできたんですよ？
しかしTLEが解消できなかったorz
最初にHの頂点全部入れる発想があれば解けたんだけどなあ😢
余談だけど公式解説がいつものフレーズ書いていて草生えそうになったのは内緒
この問題は多始点BFSの練習問題です。
ソースコード
競技時間TLEコード
main.py
from collections import deque, defaultdict
import sys
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())
def err(*args): print(*args, file=sys.stderr)
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
dd = defaultdict(lambda: float("inf"))
def out_of_bounds(y, x, h, w):
return y < 0 or y >= h or x < 0 or x >= w
def main():
H, W, D = rLI()
grid = [[] for i in range(H)]
floors = set()
humids = []
humided = set()
ans = 0
for i in range(H):
grid[i] = list(rS())
# err(grid[i])
for j,s in enumerate(grid[i], start=0):
if s==".":
floors.add((i,j))
if s=="H":
humids.append((i,j))
for h in humids:
queue = deque([(h,0)])
while queue:
cur, d = queue.popleft()
if cur not in humided:
humided.add(cur)
dd[cur]=d
ans+=1
if d < D:
ci,cj = cur
for i,j in zip(dy,dx):
nxt = ci+i,cj+j
if out_of_bounds(nxt[0],nxt[1],H,W):continue
if nxt in floors:
queue.append((nxt,d+1))
elif d<dd[cur]:
ci,cj = cur
for i,j in zip(dy,dx):
nxt = ci+i,cj+j
if out_of_bounds(nxt[0],nxt[1],H,W):continue
if nxt in floors:
queue.append((nxt,d+1))
print(ans)
if __name__ == '__main__':
main()
競技終了後ACコード
main.py
from collections import deque, defaultdict
import sys
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())
def err(*args): print(*args, file=sys.stderr)
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
dd = defaultdict(lambda: float("inf"))
def out_of_bounds(y, x, h, w):
return y < 0 or y >= h or x < 0 or x >= w
def main():
H, W, D = rLI()
grid = [[] for i in range(H)]
floors = set()
humids = []
humided = set()
ans = 0
for i in range(H):
grid[i] = list(rS())
# err(grid[i])
for j,s in enumerate(grid[i], start=0):
if s==".":
floors.add((i,j))
if s=="H":
humids.append((i,j))
queue = deque([(h,0) for h in humids])
while queue:
cur, d = queue.popleft()
if cur not in humided:
humided.add(cur)
dd[cur]=d
ans+=1
if d < D:
ci,cj = cur
for i,j in zip(dy,dx):
nxt = ci+i,cj+j
if out_of_bounds(nxt[0],nxt[1],H,W):continue
if nxt in floors:
queue.append((nxt,d+1))
print(ans)
if __name__ == '__main__':
main()
D
C問題を一回TLEしたあとギリギリまでここに取り掛かっていた。
N^(0.5)以下の素数を列挙した場合をp,q(p<q)とした場合
p^8もしくはp^2*q^2がN以下の場合その値は条件を満たすのでカウントする。
前者は一つずつチェックすればいいが、後者の組み合わせが多いので尺取法で頑張る。
解のカウント方法ミスって1ペナもらってしまった。
ソースコード
main.py
import sys
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())
def err(*args): print(*args, file=sys.stderr)
def sieve(n):
is_prime = [True for _ in range(n+1)]
is_prime[0] = False
for i in range(2, n+1):
if is_prime[i-1]:
j = i * i
if j > n:break
while j <= n:
is_prime[j-1] = False
j += i
table = [ i for i in range(1, n+1) if is_prime[i-1]]
return is_prime, table
def main():
N = rI()
p,t= sieve(int(N**(1/2)))
x= sum(p)
# err(x)
ans = 0
for x in t:
if x**8 <= N:
ans+=1
p2 = list(map(lambda p:p*p,t))
l=0
r=len(p2)-1
while l < r:
m = N//p2[l]
while p2[r] > m: r-=1
# if N==200:err(l,r,p2[l],p2[r])
ans += max(0,r-l)
l+=1
print(ans)
if __name__ == '__main__':
main()
E
グラフはまだまだ慣れません
F
解説によると動的計画法で行けるらしい
時間あれば解きたい
G
解説は何かdpとか記号あったけど
分割統治法でやるとかどうとか。
アルゴリズムの授業で聞いたことあるワードだけど
G問題なのでやることは複雑ですねぇ…
まとめ
BFSの感覚が足りていないのが残念なところ
グリッド問題苦手すぎて逃げてきたツケが回ってきたという話。
当たり前だが好みのジャンルばかりしないで
苦手な分野も解けるようにしないと地力はつかないね