ABC369振り返り

前回の振り返り

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

今週も無事A,B,Cの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 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():
    A, B = rLI()
    ans = 0
    for x in range(-200,201):
        L = [x,A,B]
        L.sort()
        p,q,r=L
        if q-p==r-q:
            # err(L)
            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 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()
    pos= {"L":-1,"R":-1}
    ans = 0
    for _ in range(N):
        A, S = rLS()
        A = int(A)
        if pos[S] != -1:
            ans += abs(pos[S]-A)
        pos[S] = A

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

C

まず明らかに2項以下のときは等差数列確定なので
その組み合わせは2N-1通りあるので加算

Aの前項の差分を取った配列d0と
更にd0の前項の差分を取ったd1を作る

3項以上の場合はd1の値が0のときのみあり得るので
d1が連続した数を覚え、それぞれ加算

ソースコード

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 = rLI()
    
    ans = 2*N-1
    d0 = [0]+[A[i]-A[i-1]for i in range(1,N)]
    d1 = [d0[i]-d0[i-1]for i in range(1,N)]
    d2 = [0] * (N-1)
    
    for i in range(1,N-1):
        if d1[i] == 0:
            d2[i] = d2[i-1]+1
            ans += d2[i]

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

D

動的計画法を使い
DP[i][j]i番目の敵をj番目に倒したときの最大値
としたけどTLE

テーブルを奇数偶数に分ける発想なんて出なかったYO

ソースコード

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 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 = rLI()
    
    
    dp = [0] * (N + 1)
    ndp = [0] * (N + 1)
    for i, a in enumerate(A):
        
        for j in range(i+1):
            p = dp[j]
            ndp[j] = max(ndp[j], p)
            q = dp[j] + a
            if (j + 1) % 2 == 0:
                q += a
            ndp[j + 1] = max(ndp[j+1],q)
        # err(a,ndp)
        dp,ndp=ndp,dp
    
    print(max(dp))
    
if __name__ == '__main__':
    main()

E

問題の頭3行読んでグラフぽいと思ったから無視

F

座標系の問題もグラフ並に苦手なので無視

G

「木が与えられます」て来た時点でグラフかなって思ったけど
更にそれを使ってゲームするってすごいね

まとめ

D問題がDPなのに解けなかったのが非常にもったいない、
以前はDPの発想すら出なかったので多少はマシになっているが、
解けないことには意味がないので、
もっと実装を工夫できるようになりたい。