トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）振り返り

最初にまとめ

先週に引き続き Rated で参加。前回スコアがあまり伸びなかったので今日こそ伸ばすぞ！という気持ちで望んだ。 ABC 344 は今までの ABC に比べると解けそうな問題が多かったのだけど、実装ミスを多く出してしまってペナルティを多く食らってしまったのがショック。 久々? というか初? の A~E の5完で、今回は比較的解きやすい問題が多かったのもあるかもしれないのだけど素直に嬉しい。

D 問題は再帰か DP かとなったときにどうしても再帰のほうが理解しやすくてそちらにしがち。今回は再帰でも書けたのだけど、DPでしか解けない問題も多いのでそちらの練習もせねば。

A - Spoiler

英小文字と | が2つ含まれた文字列を渡されるので、 | で囲まれた文字列を除いて残りの文字列を出力せよという問題。

start, end のフラグを使うようにしたけど、もっと簡単に書けそう。

#!/usr/bin/env python3
import sys

def solve(S: str):
    res = ""
    begin = False
    end = False
    for c in S:
        if c == "|":
            if begin:
                end = True
            else:
                begin = True
        else:
            if begin and not end:
                pass
            else:
                res = res + c
    print(res)
    return

# Generated by 2.12.0 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

B - Delimiter

0 が入力されるまで整数を受取り、最後に逆順にして print せよという問題。

While で取って最後に reverse してから出力するようにした。

#!/usr/bin/env python3

def main():
    res = []
    while True:
        n = input().strip()
        res.append(n)
        if n == "0":
            break
    print("\n".join(reversed(res)))
    return

if __name__ == '__main__':
    main()

C - A+B+C

A, B, C の数列が与えられる。X のそれぞれの要素について、A, B, C からそれぞれ１つずつ要素を取ることで実現できるか答えるもの。

最初愚直に多重ループにして解こうとしたりして実装ミスを繰り返してしまった。

自分の解答だと A, B の合計だけ先に計算するようにしていたけど、解説にある通り A, B, C の結果をすべて先に計算しておくことでより簡潔になりそう。

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

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

def solve(N: int, A: "List[int]", M: int, B: "List[int]", L: int, C: "List[int]", Q: int, X: "List[int]"):
    ab_sum = defaultdict(int)
    for a in A:
        for b in B:
            ab_sum[a+b] += 1
    
    for x in X:
        found = False
        for c in C:
            if x - c in ab_sum:
                found = True
                break
        
        if found:
            print(YES)
        else:
            print(NO)
    return

def main():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    M = int(input().strip())
    B = list(map(int, input().strip().split()))
    L = int(input().strip())
    C = list(map(int, input().strip().split()))
    Q = int(input().strip())
    X = list(map(int, input().strip().split()))
    solve(N, A, M, B, L, C, Q, X)

if __name__ == '__main__':
    main()

D - String Bags

DFS で解こうとして TLE になってしまうので、DP で書こうとするも間違ってしまい、何度もペナルティをもらってしまう。DP 苦手だ…

結果 5回もペナルティをもらってしまったけど、 DFS の処理の見直しと結果をキャッシュするようにしてAC

#!/usr/bin/env python3

from collections import Counter
from functools import cache

def main():
    T = input().strip()
    N = int(input().strip())
    A = []
    for _ in range(N):
        line = input().strip().split()
        c = Counter(line[1:])
        A.append(c.keys())

    @cache
    def dfs(index: int, rest_str: str) -> int:
        if len(rest_str) == 0:
            return 0
        if index >= N:
            return float('inf')
        
        tmp = float('inf')
        candidates = A[index]
        for candidate in candidates:
            if rest_str.startswith(candidate):
                length = len(candidate)
                tmp = min(1 + dfs(index + 1, rest_str[length:]), tmp)
        tmp = min(tmp, dfs(index+1, rest_str))
        return tmp

    score = dfs(0, T)
    print(-1) if score == float('inf') else print(score)

if __name__ == '__main__':
    main()

E - Insert or Erase

Doubly Linked List を実装すれば OK な問題。ちゃんと実装できれば D とかよりも簡単な気がする。

最初に head と tail をダミーな Node として追加しておくと、実際の値を追加するときや削除するときに常に前後に Node がある状態になり、実装が簡単になりました。

#!/usr/bin/env python3

class Node:
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

def main():
    N = int(input())
    A = list(map(int, input().strip().split()))
    tail = Node(-1)
    head = Node(-1)
    head.next = tail
    tail.prev = head
    current = head

    nodemap = {}

    for a in A:
        node = Node(a)
        nodemap[a] = node
        node.prev = current
        node.next = current.next
        current.next.prev = node
        current.next = node

        current = current.next
    
    Q = int(input())
    for _ in range(Q):
        line = input().strip().split()
        if line[0] == "1":
            x, y = list(map(int, line[1:]))
            x_node = nodemap[x]

            y_node = Node(y, x_node.next, x_node)

            x_node.next.prev = y_node
            x_node.next = y_node
            nodemap[y] = y_node
        else:
            x = int(line[1])
            node = nodemap[x]
            node_next = node.next
            node_prev = node.prev

            node_prev.next = node_next
            node_next.prev = node_prev
            del nodemap[x]
    
    tail.prev.next = None
    current = head.next
    res = []
    while current:
        res.append(current.val)
        current = current.next
    
    print(" ".join([str(x) for x in res]))

if __name__ == '__main__':
    main()