LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@comet725

ABC388振り返り

Last updated at Posted at 2025-01-11

前回の振り返り

今日はABC388開催日だったので参加結果を振り返る

今週はA,B,C,Dの4完(0ペナ)

A

f-stringは便利

ソースコード

main.py
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():
    S = rS()
    ans = f"{S[0]}UPC"
    print(ans)
    
if __name__ == '__main__':
    main()

B

for文で全計算

ソースコード

main.py
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, D = rLI()
    
    s = []
    
    for i in range(N):
        s.append(rLI())
    
    for i in range(D):
        ans = 0
        for T,L in s:
            w = (L+-~i)*T
            # err(w)
            ans = max(ans,w)
        print(ans)
    
if __name__ == '__main__':
    main()

C

最低限大きければそれ以降は全部乗せられる

尺取法で乗せられる大きさまで見つけたら
それ以上の大きさの個数を足す

ソースコード

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()
    
    ans = r = 0
    
    for i in range(N):
        a = A[i]
        while r<N and 2*a>A[r]:r+=1
        if r==N:break
        # err(i,a,r,A[r])
        # err(ans, N-r)
        ans += N-r
    print(ans)
    
if __name__ == '__main__':
    main()

D

各々で何個リリースするかを考える

渡すべき石の数は自分より後ろの人の人数
それより持ってる石の数が少なければ後ろの人はもらえない

順番に渡すと時間かかりそうなので遅延セグ木でゴリ押し

なぜか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)

#lazy_segtreeの実装略

# 操作の定義
def op(a, b):
    return a + b

def mapping(f, x):
    return f + x

def composition(f, g):
    return f + g

ID = 0
E = 0

def main():
    N = rI()
    A = rLI()
    B = lazy_segtree(A, op, E, mapping, composition, ID)

    for i in range(N):
        b = B.get(i)
        r = min(b,N--~i)
        # err(b,r)
        if r > 0:
            B.apply_point(i,-r)
            B.apply(i+1,i+1+r,1)
        
    ans = [B.get(i) for i in range(N)]
    print(*ans)
    
if __name__ == '__main__':
    main()

E

Cのプログラムいじって貪欲法でやったがWA
反対側でやった場合をやってみたがWA

乗せられる餅の組み合わせをグラフの辺に見立てて一般最大マッチング？とか思ったけど無茶だった

ソースコード

WAコード
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()
    
    ansl = 0
    r = 1
    
    usedl = defaultdict(lambda: False)
    for i in range(N):
        if usedl[i]:continue
        a = A[i]
        while r<N and (2*a>A[r] or usedl[r]):r+=1
        if r==N:break
        usedl[i] = True
        usedl[r] = True
        ansl += 1
        # err(ansl,i,a,r,A[r])
        # err(*[k for k,v in usedl.items() if v])
    ansr = 0
    usedr = defaultdict(lambda: False)
    # err("-------------------------")
    l = N-2
    for i in range(N-1,1,-1):
        if usedr[i]:continue
        a = A[i]
        while l>=0 and (2*A[l]>a or usedr[l]):l-=1
        if l==-1:break
        usedr[i] = True
        usedr[l] = True
        ansr += 1
        # err(ansr,i,a,l,A[l])
        # err(*[k for k,v in usedr.items() if v])
        
    print(max(ansl,ansr))
    
if __name__ == '__main__':
    main()

F

動的計画法したくなるけど
N成約が巨大過ぎてきつい…

G

Eの強化版ですね。

まとめ

久々の4完だけどEの壁は厚い…

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?