ABC365振り返り

前回の振り返り

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

今回も3完、D,E問題は一歩及ばず解けなかった。

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 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():
    Y = rI()
    is_leap = Y % 4 ==0
    if Y % 100 == 0:

        is_leap = Y % 400 == 0
        
    ans = 366 if is_leap else 365
    print(ans)
if __name__ == '__main__':
    main()

B

2次元配列のソートって一番最初の要素を使ってソートするので
そこから値を引っ張る。

ソースコード

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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()
    A = [(a,i)for i, a in enumerate(rLI())]
    
    A.sort()
    
    ans = A[-2][1]+1
    print(ans)
    
    
if __name__ == '__main__':
    main()

C

金額の上限と下限をある程度絞ってから二分探索
ここで2ペナ食らった…

ソースコード

main.py

import sys
from collections import Counter
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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, M = rLI()
    A = rLI()
    
    if sum(A) <= M:
        print("infinite")
        return
    
    C = Counter(A)
    C = [(k,v) for k,v in C.items()]
    C.sort()
    L = len(C)
    S = [0] * L
    T = [0] * L 
    for i,c in enumerate(C):
        k,v = c
        S[i] = k*v
        T[i] = v
        if i > 0:
            S[i] += S[i-1]
            T[i] += T[i-1]
    left = 0
    j = -1
    for i in range(L):
        k = C[i][0]
        x = S[i] + k*(N-T[i])   
        if x <= M:
            j = i
            err(x)
            left = k
        else:
            right = k
            break
    err(left,right)
    while left+1 < right:
        mid = (left+right)//2
        if j == -1:
            x = mid*N
        else:
            x = S[j] + mid*(N-T[j])
        if x <= M:
            left = mid
        else:
            right = mid
        err(mid)
    print(left)        
    
if __name__ == '__main__':
    main()

D

最善手しか出さない前提で作ってた。
普通にDPでよかったっていう。

ソースコード

WAなので折りたたみ

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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)

win = {"R":"P","P":"S","S":"R"}
lose = {"R":"S","P":"R","S":"R"}

def main():
    N = rI()
    S = rS()
    
    H =[win[s] for s in S]
    
    ans = 1
    for i in range(1,N):
        h,s = H[i],S[i]
        p = H[i-1]
        w = win[s]
        l = lose[s]
        if h != p and h == w:
            ans += 1
        elif h == p and h == w:
            H[i] = s
        elif h == p and h != w:
            H[i] = w
            ans += 1
        elif h != p and h != w:
            if p == w:
                H[i] = s
            if p != w:
                H[i] = w
                ans += 1
            
    print(ans)
    
if __name__ == '__main__':
    main()

E

残り20分くらいでbit毎に計算する発想はでたけど
どう詰めればいいか間に合わなかった…

ソースコード

WAなので折りたたみ

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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)

M = 32

def main():
    N = rI()
    A = rLI()
    
    S = [[0]*M for _ in range(N)]
    for i, a in enumerate(A):
        s = format(a, f'0{M}b')
        bin = [int(bit) for bit in s]
        err(s)
        for j,b in enumerate(reversed(bin)):
           S[i][j] = b
           if i>0:
               S[i][j] += S[i-1][j]
        err(S[i])
    ans = 0
    for i in range(N):
        x = []
        y = []
        for j in range(M):
            k = S[N-1][j]
            if i > 0:
                k -= S[i-1][j]
            y.append(k)
            if k % 2 == 0:
                m = k // 2
            else:
                m = (N + 1) // 2
            ans += m * 2**j
            x.append(m * 2**j)
        err("x:",x)
        err("y:",y)
    print(ans-sum(A))
    
if __name__ == '__main__':
    main()

F

問題のページでマス目の画像出た瞬間そっ閉じ

G

セグメント木N個とか思ったけど全然違った

まとめ

D問題のDPすればいいのに気づかなかったのは致命的ミス。
あとC問題で2ペナも結構つらい。

最近精進をサボりがちのでもう少しトレーニングを積みたい。