【AtCoder】PythonでABC328を解く

はじめに

abc328のA,B,C,D,E問題をPython3で解きます。

A問題

atcoder.jp

問題の概要

配点が以下である問題すべての配点の合計を出力せよ。

問題の考察

リスト内包表記とsum関数を使うと楽に実装できます。

コード

def main():
    N, X = map(int, input().split())
    S = list(map(int, input().split()))
    ans = sum(s for s in S if s <= X)
    print(ans)


if __name__ == "__main__":
    main()

B問題

atcoder.jp

問題の概要

月日 ()がゾロ目になる日付の日数を数えよ。

問題の考察

日付を全探索し、各日付を文字列に直して集合のサイズが1か調べることでゾロ目を判定します。

コード

def solve(N, D):
    repdigit_dates = []
    for i, d in enumerate(D, 1):
        for j in range(1, d + 1):
            date = f"{i}{j}"
            if len(set(date)) == 1:
                repdigit_dates.append(date)

    return repdigit_dates


def main():
    N = int(input())
    D = list(map(int, input().split()))
    ans = solve(N, D)
    print(len(ans))


if __name__ == "__main__":
    main()

C問題

atcoder.jp

問題の概要

文字列が与えられる。の文字目から文字目までからなる部分文字列において、同じ文字が2つ隣り合う箇所はいくつあるか、という個の質問に答えよ。

問題の考察

2つ隣り合う箇所の累積和を事前に求めておくことで、各質問にで答えます。

コード

from itertools import pairwise


def solve(N, Q, S, LR):
    X = [0, 0]
    for s1, s2 in pairwise(S):
        X.append(X[-1] + int(s1 == s2))

    ans = []
    for left, right in LR:
        z = X[right] - X[left]
        ans.append(z)

    return ans


def main():
    N, Q = map(int, input().split())
    S = input()
    LR = [list(map(int, input().split())) for _ in range(Q)]
    ans = solve(N, Q, S, LR)
    print(*ans)


if __name__ == "__main__":
    main()

D問題

atcoder.jp

問題の概要

A,B,Cの3種類の文字からなる文字列が与えられる。連続な部分文字列としてABCを含む限りから削除するというのを繰り返すとき、最終的なを出力せよ。

問題の考察

の先頭の文字から順にスタックに積んでいき、スタックの後ろ3文字がABCだった場合はスタックから3文字分だけpopします。Pythonの場合、スライスを使って後ろ3文字を調べることで、現在のスタックのサイズが3未満だったとしてエラーなく判定できます。

コード

def solve(S):
    lifo = []
    for s in S:
        lifo.append(s)
        S3 = "".join(lifo[-3:])
        if S3 == "ABC":
            lifo.pop()
            lifo.pop()
            lifo.pop()

    return "".join(lifo)


def main():
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == "__main__":
    main()

E問題

atcoder.jp

問題の概要

頂点辺の重み付き単純連結無向グラフと正整数が与えられる。このグラフの全域木に対して、含まれる辺の重みの総和をで割った余りをその全域木のコストとするとき、このグラフの全域木のコストの最小値を求めよ。

問題の考察

制約より最大で頂点数が8で辺数が28であることから、このグラフから作れる全域木の数は高々と分かるため、全探索しても間に合いそうです。辺の集合から個の辺を取り出す組合せを全探索します。各組合せでは、UnionFindを使ってサイズがであるかを調べることで、全域木になっているかを判定します。

コード

from itertools import combinations

from atcoder.dsu import DSU


def solve(N, M, K, edges):
    ans = float("inf")
    for sub_edges in combinations(edges, N - 1):
        uf = DSU(N)
        total = 0
        for u, v, w in sub_edges:
            uf.merge(u, v)
            total += w
            total %= K
        if uf.size(0) == N:
            ans = min(ans, total)

    return ans


def main():
    N, M, K = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edges.append((u, v, w))
    ans = solve(N, M, K, edges)
    print(ans)


if __name__ == "__main__":
    main()