def yasuharu519(self):

日々の妄想

ユニークビジョンプログラミングコンテスト2024 春(AtCoder Beginner Contest 346)振り返り

はじめに振り返り

一度ミスはあったものの、スムーズに A~E の5問解けた。ミスも防げたミスだったように感じているので、ちょっと悔しい。 F はなんとなく解き方は想像できたものの、すぐに正しい実装までたどり着くことができなかったので練習あるのみですね。

A - Adjacent Product

問題の指示通り出力すればOK。A の配列の最後の一つ前まで走査して結果を計算して出力する形に。

#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[int]"):
    result = []
    for i in range(N-1):
        result.append(A[i] * A[i+1])
    print(" ".join([str(x) for x in result]))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

B - Piano

難しく考えて地味に時間をかけてしまった。白鍵 と黒鍵の数は繰り返しになるので、辞書配列で保持してアップデートする形に。 解説でもあったが、入力が W も B も 100 程度なので、文字列展開したうえで、1オクターブ分ループするだけで良さそう。

#!/usr/bin/env python3
import sys
import math
from collections import Counter

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(W: int, B: int):
    length = W + B
    blocks = math.ceil(length / 12)
    s = "wbwbwwbwbwbw"
    S = s * 2

    div, mod = divmod((length - 1), 12)
    left = 0
    right = mod

    count_w = 7 * div
    count_b = 5 * div

    count_mod = Counter(S[:right+1])
    for k, v in count_mod.items():
        if k == "w":
            count_w += v
        else:
            count_b += v
    
    if count_w == W and count_b == B:
        print(YES)
        return
    
    for i in range(1, 12):
        left_c = S[(left+i-1)%12]
        if left_c == "w":
            count_w -= 1
        else:
            count_b -= 1
        
        right_c = S[(right+i)%12]
        if right_c == "w":
            count_w += 1
        else:
            count_b += 1

        if count_w == W and count_b == B:
            print(YES)
            return
        
    print(NO)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    W = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(W, B)

if __name__ == '__main__':
    main()

C - Σ

1~ K のうち、数列 A に含まれない整数の合計値を計算せよというもの。 1~K の合計値を先に計算しておき、数列 A をひと通り見て、 1~K に含まれるものの場合は合計値から差し引くことで対応

#!/usr/bin/env python3
import sys

def solve(N: int, K: int, A: "List[int]"):
    total = K*(1+K)//2
    passed = set()

    for a in A:
        if a > K:
            continue
        if a in passed:
            continue
        passed.add(a)
        total -= a
    print(total)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

D - Gomamayo Sequence

01 からなる文字列が与えられ、 01 が2文字並ぶ部分が1つだけ含まれるような文字列を作るためのコストの最小値を計算するといったもの。 - 最後の値が 0 で、まだ2文字の並びを作れていない - 最後の値が 0 で、すでに並びを作れている - 最後の値が 1 で、まだ2文字の並びを作れていない - 最後の値が 1 で、すでに並びを作れている の4つのパターンに分けて状態遷移させ、最小値を計算するようにした。

文字列を走査したとき、"今の値を変更するか" 次第でコストを追加する必要があるか分かれるだけで、状態遷移は同じになる。なので、分岐の部分はもう少しシンプルに書けそう。

#!/usr/bin/env python3
import sys

def solve(N: int, S: str, C: "List[int]"):
    dp = [[float('inf')] * 4 for _ in range(N)]
    s = S[0]
    if s == "0":
        dp[0][0] = 0
        dp[0][2] = C[0]
    else:
        dp[0][0] = C[0]
        dp[0][2] = 0
    
    for i in range(1, N):
        s = S[i]
        if s == "0":
            dp[i][0] = dp[i-1][2]
            dp[i][1] = min(dp[i-1][0], dp[i-1][3])
            dp[i][2] = dp[i-1][0] + C[i]
            dp[i][3] = min(dp[i-1][1], dp[i-1][2]) + C[i]
        else:
            dp[i][0] = dp[i-1][2] + C[i]
            dp[i][1] = min(dp[i-1][0], dp[i-1][3]) + C[i]
            dp[i][2] = dp[i-1][0]
            dp[i][3] = min(dp[i-1][1], dp[i-1][2])
    print(min(dp[N-1][1], dp[N-1][3]))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, C)

if __name__ == '__main__':
    main()

E - Paint

1行もしくは、1列同じ色で塗る操作を繰り返して、最後に残った色と個数を答えるもの。 最終的に塗った色で上書きされていくので、色の塗り順を逆から見ていき、色を塗る際にはまだ塗られていないマスの個数を数えることで解決した。

最初、連想配列ではなくただの配列で記録していってしまい、逆順に見て色を塗った時点で確定としてしまっており、同じ色のマス目を結果として合計できずに WA になってしまった。

#!/usr/bin/env python3
import sys
from collections import defaultdict

def solve(H: int, W: int, M: int, T: "List[List[int]]"):

    passed_row = set()
    passed_col = set()
    total = H * W
    result = defaultdict(int)
    result[0] = total

    for t, a, x in reversed(T):
        if t == 1:
            if a in passed_row:
                continue
            passed_row.add(a)
            res = W - len(passed_col)
            if res:
                result[0] -= res
                result[x] += res
        else:
            if a in passed_col:
                continue
            passed_col.add(a)
            res = H - len(passed_row)
            if res:
                result[0] -= res
                result[x] += res
    
    for_print = []
    for k, v in sorted(result.items()):
        if v == 0:
            continue
        for_print.append((k, v))
    
    print(len(for_print))
    for k, v in for_print:
        print(k, v)
    return

def main():
    H, W, M = list(map(int, input().strip().split()))
    T = []
    for _ in range(M):
        T.append(list(map(int, input().strip().split())))
    solve(H, W, M, T)

if __name__ == '__main__':
    main()