Zenn
😸

AtCoder ABC204 個人的メモ

2021/06/07に公開
Python
#
競技プログラミング
AtCoder
tech

所感

abc3完
abc204_score

A - Rock-paper-scissors

if文でおｋ

x, y = map(int, input().split())

res = {x, y}
if 0 not in res and len(res) == 2:
    print(0)

if 1 not in res and len(res) == 2:
    print(1)

if 2 not in res and len(res) == 2:
    print(2)

if len(res) == 1:
    print(x)


x, y = map(int, input().split())

if x == y:
    print(x)
else:
    print(*{0, 1, 2} ^ {x, y})

B - Nuts

forループですべての木において、その木が条件を満たしているかを判定すればおｋ

N = int(input())
A = list(map(int, input().split()))

ans = 0
for a in A:
    if a <= 10:
        continue
    ans += a - 10

print(ans)

C - Tour

DFS
都市の組み合わせは全部で_N C_2通りで、これを全探索するのは無理。
スタートする都市を固定すると、到達可能な都市はDFSで求められる。
計算量は全ての都市を考えるのにO(N)DFSでO(N+M)なので、全体でO(N(N+M))となり間に合いそう。

再帰上限を変え忘れてre

from sys import setrecursionlimit

setrecursionlimit(4000)


def dfs(node: int):
    if visited[node]:
        return
    visited[node] = 1

    for n_node in E[node]:
        if visited[n_node]:
            continue
        dfs(n_node)
    return


N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a - 1].append(b - 1)

ans = 0
for i in range(N):
    visited = [0] * N
    dfs(i)
    ans += sum(visited)

print(ans)

c参考

再帰関数の計算量
https://qiita.com/drken/items/4a7869c5e304883f539b#3-5-dfs-の計算量

D - Cooking

https://atcoder.jp/contests/abc204/editorial/2013

N = int(input())
T = list(map(int, input().split()))

# i番目までの料理で、料理の時間が丁度j分となる組み合わせが存在するか？
dp = [1] + [0] * sum(T)

for t in T:
    next_dp = list(dp)
    for i in range(len(dp)):
        if dp[i]:
            next_dp[i + t] = 1
    dp = list(next_dp)

print(dp[len(dp) // 2:].index(1) + len(dp) // 2)

d参考

部分和問題
https://qiita.com/drken/items/a5e6fe22863b7992efdb#3-部分和問題とその応用たち

Discussion