ABC379振り返り

前回の振り返り

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

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

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():
    S = rS()
    a= S[0]    
    b= S[1]    
    c= S[2]    
    
    print(f"{b}{c}{a} {c}{a}{b}")
    
    
if __name__ == '__main__':
    main()

B

先週１ペナ食らった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, K = rLI()
    S = rS()
    
    L = [len(s) for s in S.split("X")]
    # err(L)
    print(sum(l//K for l in L if l >= K))
        
if __name__ == '__main__':
    main()

C

等差数列の和の公式を使いそうな気配をしたが
初項と交差、項数の設定がうまくいかない

そしてごちゃごちゃこねくり回してサンプルケース通して提出したが
WAだったからパス

D

今回もdefaultdict君大活躍

defaultdictのキーを植物の高さとして
値に植物の個数を管理

クエリ来る度新しい高さに値を加えて元の高さを消してを繰り返す

念の為高さ一覧は別個で管理

ソースコード

main.py

import sys
from collections import defaultdict
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():
    Q = rI()
    d = defaultdict(lambda: 0)
    K = set()
    for _ in range(Q):
        q = rLI()
        if q[0] == 1:
            d[0] += 1
            K.add(0)
        elif q[0] == 2:
            T = q[1]
            nK = set()
            for k in K:
                v = d[k]
                del d[k]
                d[k+T] += v
                nK.add(k+T)
            K = nK
        elif q[0] == 3:
            H = q[1]
            ans = 0
            nK = K.copy()
            for k in K:
                v = d[k]
                if k >= H:
                    del d[k]
                    ans += v
                    nK.remove(k)
            print(ans)
            K = nK
if __name__ == '__main__':
    main()

E

まずこれを忘れて一回REした

sys.set_int_max_str_digits(0)

あと巨大数の掛け算が遅いの気づかずTLE

工夫して掛け算の回数を減らそうとしたが
依然としてTLE解消せず時間切れ

桁一つずつ計算するのね…

TLEコード

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)
sys.set_int_max_str_digits(0)

from collections import defaultdict
d = defaultdict(lambda: 0)

def main():
    N = rI()
    S = rS()
    m = "1"*N
    for i,s in enumerate(S):
        if s=="0":continue
        x = int(m[i:])
        # err(i,s,x)
        d[s] += x*(i+1)
        
    print(sum(i*d[str(i)] for i in range(10)))
    
if __name__ == '__main__':
    main()

F, G

E問題のTLEと格闘して読む時間無かったorz

まとめ

CをパスしてD問題を解けたのはよかったがまだまだE問題の壁が厚い…

宣伝

競技プログラミングのアドベントカレンダー作ったので参加者募集中です(言語不問)