競技プログラミングなんでもカレンダー開始(ABC382振り返り)

今日からアドベントカレンダー開始ということで
意気込みとか予定とか色々まとめたり

自己紹介

改めて自己紹介

• AtCoderを2024年3月に始めた(初参加はABC343)
• 使用言語はPython(使用歴7年前後)
• 動的計画法とセグ木が好き(解けるとは言っていない)

よく使う実装は以下の過去記事見てください

予定

土曜日のABCは必ず出るとして、振り返りの記事を作る

それ以外はABCの当日にACできなかった問題や過去問を解いたり、
勉強の記録をまとめたりする予定

ABC382振り返り

上記の内容では短いのでABC382参加結果を振り返る

前回の振り返り

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

• 10分後にDを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, D = rLI()
    S = rS()
    ans = S.count(".")+D
    print(ans)
    
if __name__ == '__main__':
    main()

B

後ろから食うだけ

ソースコード

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, D = rLI()
    S = [s for s in rS()]
    c = [i  for i,s in enumerate(S) if s == "@"]
    
    for _ in range(D):
        i = c.pop()
        S[i] = "."
    print("".join(S))
    
if __name__ == '__main__':
    main()

C

最小値更新しないと手に取らないので、それ以外は除外
あと念の為二分探索

ソースコード

main.py

import sys
from bisect import bisect_right

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, M= rLI()
    
    A = rLI()
    B = rLI()
    
    L = []
    K = 0
    d = {}
    mA = float("inf")
    for i,a in enumerate(A,start=1):
        if mA <= a: continue
        mA=a
        L.append(a)
        d[a]=i
        K+=1
    R = L[::-1]
    for b in B:
        # err(b)
        if b >= mA:
            a_i = bisect_right(R,b)
            # err(a_i,R[a_i-1],d[R[a_i-1]])
            print(d[R[a_i-1]])
        else:
            print(-1)
    
if __name__ == '__main__':
    main()

D

数列を小さい順から列挙するのはうまくいった。
しかし、再帰関数の実装でうまくいかずTLE…
解説みたらrangeの設定ミスっていたっぽい

ソースコード

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)

X = 0

def main():
    N, M = rLI()
    k = M%10
    if k == 0:
        k = 10
    
    Y = []
    
    cur = []
    
    def find(i,a):
        global X
        # err(i,a,a+10,M-10*(N-i)+1,cur)
        for b in range(a+10,M-10*(N-i)+1):
            cur.append(b)
            if i==N:
                X+=1
                Y.append(cur[:])
            else:
                find(i+1,b)
            cur.pop()
    for i in range(1,k+1):
        cur.append(i)
        find(2,i)
        cur.pop()
    
    print(X)
    for y in Y:
        print(*y)
if __name__ == '__main__':
    main()

E

内容は面白そうだけど期待値ですか…

F

E問題よりこっちのほうが解いてないか定期

G

前出たゲキムズ問題の強化版じゃないですか…

まとめ

また茶色に戻ってしまいました

• 日和らずにratedでやったので許してください←

再帰関数とかよく使う実装のはずなのにうまくいかったのは反省点すぎる。
明日からの精進頑張ります…