前回の振り返り
今日はABC441開催日だったので参加結果を振り返る
今週はA,B,C,Dの4完(0ペナ)
A
ansの条件式がちょっと難しいかも
ソースコード
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():
P, Q = rLI()
X, Y = rLI()
ans = P <= X <= P+99 and Q <= Y <= Q+99
print('Yes' if ans else 'No')
if __name__ == '__main__':
main()
B
文字列探索して該当しない文字列があるならその言語ではないから除外
どっちも除外できなかったら不明。
実装に微妙に時間かかった
ソースコード
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, M = rLI()
S = rS()
T = rS()
Q = rI()
for _ in range(Q):
w = rS()
f1 = f2 = True
for c in w:
if f1 and c not in S:
f1 = False
if f2 and c not in T:
f2 = False
if f1 and f2:
print("Unknown")
elif f1:
print("Takahashi")
elif f2:
print("Aoki")
else:
print("Unknown")
if __name__ == '__main__':
main()
C
最悪ケースでは液体量が少ない順に入っていることを想定して累積和でどれだけ呑むことができたか計算。
最初わからなくてFで沼ったあと時間ギリギリに解き直してなんとか提出。
コンテスト終了後にソースコード
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, K, X = rLI()
A = rLI()
A.sort()
S = [0]+list(accumulate(A))
i0 = max(1,N-K+1)
for i in range(i0,N+1):
j = i - (N-K)
l = N - i
r = l + j
s = S[r]-S[l]
# err(i,s)
if s >= X:
print(i)
break
else:
print(-1)
if __name__ == '__main__':
main()
D
愚直にBFSして該当するノードをチェックする
ソースコード
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, M, L, S, T = rLI()
G = [[] for _ in range(N)]
for _ in range(M):
a, b, w = rLI()
a -= 1
b -= 1
G[a].append((b, w))
approved = set()
queue = deque([(0,0,0)])
while queue:
cur,d,c = queue.popleft()
if d == L and (cur+1) not in approved and S <= c <= T:
err("ok", cur,d,c)
approved.add(cur+1)
elif d < L:
for nxt in G[cur]:
x, w = nxt
nc = c+w
nd = d+1
err(x,nc,nd)
if nc <= T:
queue.append((x,nd,nc))
print(*sorted(approved))
if __name__ == '__main__':
main()
E
セグ木…？とかおもったけど
転倒数チックに解くらしい→BITだったというオチ。
この問題けっこう穴場だったみたい…
F
C,E問題飛ばしてここで沼ったけど解けなかった。
DPを組んだけど解の復元どうすればいいんだろとなって終了。
G
問題見る時間なかったけど
遅延セグ木で頑張るやつでしたかー
感想
Dを早めに解くことはできたが
Fで沼る前にCを先に消化すべきだったのが反省