【AtCoder】PythonでABC318を解く

はじめに

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

A問題: Full Moon

atcoder.jp

問題の概要

満月が日目に初めて見られて、以後は日ごとに見られる。1日目から日目までの間に満月が見られる回数を答えよ。

問題の考察

range(M, N + 1, P)の回数だけ数えます。

コード

def solve(N, M, P):
    ans = 0
    for _ in range(M, N + 1, P):
        ans += 1

    return ans


def main():
    N, M, P = map(int, input().split())
    ans = solve(N, M, P)
    print(ans)


if __name__ == "__main__":
    main()

B問題: Overlapping sheets

atcoder.jp

問題の概要

座標平面上に長方形が個ある。番目の長方形は、軸のと軸のをみたす領域を覆っている。1個以上の長方形に覆われている領域の面積を求めよ。

問題の考察

二次元配列で各グリッドを表し、そのグリッドが覆われていればTrue(1)を、そうでなければFalse(0)を代入し、最後に総和を取ります。

コード

from itertools import chain


def solve(N, A, B, C, D):
    X = [[False] * 100 for _ in range(100)]
    for a, b, c, d in zip(A, B, C, D):
        for x in range(a, b):
            for y in range(c, d):
                X[x][y] = True

    ans = sum(chain.from_iterable(X))

    return ans


def main():
    N = int(input())
    A, B, C, D = list(zip(*[list(map(int, input().split())) for _ in range(N)]))
    ans = solve(N, A, B, C, D)
    print(ans)


if __name__ == "__main__":
    main()

C問題: Blue Spring

atcoder.jp

問題の概要

日間だけ鉄道で旅行する。日目の通常運賃は円である。通常運賃とは別に1日周遊パスがあり、枚セットで円で売られている。旅行で掛かるお金の最小値を求めよ。

問題の考察

通常運賃の高い日は周遊パスを使うのがよさそうです。通常運賃を降順に並び替えて日間分ずつの通常運賃合計をみていき、それが円以上ならば周遊パスを買い、未満ならば通常運賃で支払います。

ソートが必要になるため、計算量はとなります。

コード

from heapq import heappop, heappush


def solve(N, D, P, F):
    heap = []
    for f in F:
        heappush(heap, -f)

    ans = 0
    cnt = 0
    total = 0
    while heap:
        f = heappop(heap)
        f = -f
        cnt += 1
        total += f
        if cnt >= D:
            if total >= P:
                ans += P
            else:
                ans += total
            cnt = 0
            total = 0

    if total >= P:
        ans += P
    else:
        ans += total

    return ans


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


if __name__ == "__main__":
    main()

D問題: General Weighted Max Matching

atcoder.jp

問題の概要

頂点の重み付き無向完全グラフがある。頂点と頂点を結ぶ辺の重みはである。選んだ辺の端点はどの2個も相異なるように辺を選ぶとき、選んだ辺の重みの総和の最大値を求めよ。

問題の考察

は最大でも16であるため、全探索する方針を考えます。

①未使用頂点集合から最小の頂点番号を取り出し、②それを残ったに含まれる頂点との全てのペアを考えてペアになった頂点を取り出す、という①と②をが空になるまで続けると、の計算量で解けそうです。

なお、頂点の数が奇数だと未使用頂点集合が空になることがなくて処理が面倒なため、頂点の数が奇数の場合は各頂点と重み0で繋がった頂点を1つ追加することで、奇数か偶数かに関係なく同じように処理できるようになります。

コード

def solve(N, G):
    def dfs(total=0):
        if not not_used:
            yield total
            return

        u = min(not_used)
        not_used.discard(u)
        for v in list(not_used):
            not_used.discard(v)
            yield from dfs(total + G[u][v])
            not_used.add(v)
        not_used.add(u)

    not_used = set(range(N))
    ans = 0
    for total in dfs():
        ans = max(ans, total)

    return ans


def main():
    N = int(input())
    if N % 2 == 0:
        G = [[0] * N for _ in range(N)]
        for u in range(N - 1):
            D = list(map(int, input().split()))
            for v, w in enumerate(D, u + 1):
                G[u][v] = w
    else:
        N += 1
        G = [[0] * N for _ in range(N)]
        for u in range(N - 2):
            D = list(map(int, input().split()))
            D.append(0)
            for v, w in enumerate(D, u + 1):
                G[u][v] = w

    ans = solve(N, G)
    print(ans)


if __name__ == "__main__":
    main()