AtCoder ABC 261 参戦記

前回の記事から3年近くたち、rated参加自体も2年ぶりくらいになりました。

一応青だったのですが、当然パフォーマンスも出ず水色に落ちる結果に。

500点が解けなくなっているので要復習です。

今回はDまでの4完(※いつの間にかABCが8問構成になっていました)

A問題 (Intersection)

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    l1, r1, l2, r2 = map(int, input().split())
    if l1 <= l2:
        print(max(min(r1, r2) - l2, 0))
    else:
        print(max(min(r1, r2) - l1, 0))
    return 0
  
if __name__ == "__main__":
    solve()

被っている区間の長さを出力します。

If分岐しなくてもかけそう、かつ、ループ処理で実際に被っている区間を計算すれば良さそうですが、久しぶりすぎて自分のコードに自信がなかったため安定をとるために左端の大小で場合分けしました。

B問題 (Tournament Result)

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    N = int(input())
    A = [input() for _ in range(N)]
    for i in range(N):
        for j in range(i + 1, N):
            if A[i][j] == "W":
                if A[j][i] != "L":
                    print("incorrect")
                    return 0
            elif A[i][j] == "L":
                if A[j][i] != "W":
                    print("incorrect")
                    return 0
            else:
                if A[j][i] != "D":
                    print("incorrect")
                    return 0
    print("correct")
    return 0
  
if __name__ == "__main__":
    solve()

愚直に全結果を確認しました。

ただし、２重に確認するのを避けるため、ループ処理はi < jとなる組み合わせのみ確認するようにしました。

一つでも不正な結果があれば即時returnで後続の処理もさぼるようにしています。

C問題 (NewFolder(1))

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    N = int(input())
    sm = dict()
    ans = []
    for _ in range(N):
        s = input().strip("\n")
        if s in sm:
            ans.append(s + "(" + str(sm[s]) + ")")
            sm[s] += 1
        else:
            ans.append(s)
            sm[s] = 1
    print(*ans, sep="\n")
    return 0
  
if __name__ == "__main__":
    solve()

辞書ですでに出てきた文字列のcountを持っておきます。

入力で改行文字列を取り除くのを忘れて1敗。

D問題 (Flipping and Bonus)

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    N, M = map(int, input().split())
    X = list(map(int, input().split()))
    C= dict()
    for _ in range(M):
        c, y = map(int, input().split())
        C[c] = y
    for i in range(N + 1):
        if i not in C: C[i] = 0
    point = [[0 for _ in range(N + 1)] for i in range(N)]
    point[0][1] = X[0] + C[1]
    for i in range(N - 1):
        for j in range(i + 2):
            point[i+1][0] = max(point[i+1][0], point[i][j])
            point[i+1][j+1] = max(point[i][j] + C[j+1] + X[i+1], point[i+1][j+1])
    print(max(point[N-1]))
    return 0
  
if __name__ == "__main__":
    solve()

比較的素直なDP。

連続ボーナスを辞書で保持しておき、i回目のコイントスでj連続表→j+1連続表になるときの加算点数をX[i] + j+1回目連続ボーナスとしてやればよいです。

連続ボーナスのないカウントも、0点のボーナスとして持っておけば考える箇所が減ってよいです。

TLEとi < j + 1となるような条件も計算してしまったことで2敗。