ABC375振り返り

前回の振り返り

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

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

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 = rI()
    S = rS()
    
    ans = 0
    for i in range(N-2):
        if S[i:i+3] == "#.#":
            ans+=1
    
    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 = rI()
    ans = x = y = 0
    for _ in range(N):
        xi, yi = rLI()
        ans += ((x-xi)**2+(y-yi)**2)**0.5
        x,y=xi,yi
    ans+=(x**2+y**2)**0.5
    print(ans)
    
if __name__ == '__main__':
    main()

C

どんな操作要求してるかわからんまんま
適当に配列いじっても答え出なかったYO

30分くらい悩んで飛ばしました

D

i番目とk番目の文字が同じになる組み合わせを探す
でその範囲でjを何個挿入できるか加算すればいい

まず適当にやったら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)

def main():
    A2Z = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    A2i = {a:i for i,a in enumerate(A2Z)}
    S = rS()
    N = len(S)
    d = [[] for _ in range(26)]
    for i,s in enumerate(S):
        d[A2i[s]].append(i)
    ans = 0
    # err(d)
    for i in range(N-2):
        s = A2i[S[i]]
        K = list(k for k in d[s] if k>i+1)
        # err(K)
        for k in K:
            # err(i,k,k-i-1)
            ans += k-i-1
    print(ans)

if __name__ == '__main__':
    main()

そしてTLEしたコードを眺めながら
for文なしで計算するように式をこねくり回したら
なんとか通った

説明エターなったので生成AIさんの解説置いときます

初期設定:
A2Z、大文字の英文字列を定義します。
各文字をアルファベットのインデックスにマッピングする辞書A2iを作成します。
文字列Sを読み取り、その長さNを計算します。
各文字のカウントと累積位置を保存する26要素のリストdを初期化します（各要素はリスト[0,0]）。
dを埋める:
文字列Sを走査し、各文字のカウントと累積位置を更新します。
ansを計算:
文字列を走査し、長さN-2の部分文字列を考慮します。
各文字について、その文字のカウントnと累積位置kを取得します。
文字カウントが1の場合、次のループに進みます。
調整後の位置差pを計算し、文字が連続している場合、xでpを調整します。
p - xでansを更新します。
カウントを減少させ、累積位置を調整するようにdを更新します。

ソースコード

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():
    A2Z = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    A2i = {a:i for i,a in enumerate(A2Z)}
    S = rS()
    N = len(S)
    d = [[0,0] for _ in range(26)]
    for i,s in enumerate(S):
        d[A2i[s]][0] += 1
        d[A2i[s]][1] += i
    ans = 0
    for i in range(N-2):
        n,k = d[A2i[S[i]]]
        if n == 1:continue
        # K = list(k for k in d[s] if k>i+1)
        p = k-(i+1)*(n-1)-i
        x = 0
        if S[i] == S[i+1]:
            x = max(0,(i+1)-i-1)
        # err(i,n,k,p,x,p-x)
        ans += p-x
        d[A2i[S[i]]] = [n-1,k-i]

    print(ans)
    
if __name__ == '__main__':
    main()

まとめ

Cの実装が面倒すぎたのでDを解こうとしたが沼った
なんとか時間ギリで3完できたが今回難易度高くない？