Atcoder-ABC204をpythonで問題を解いてみた

目的

• Atcoderで上を目指すべく頑張っている中でABC204を解いたので、解説してみる
  • pypy7.3を使って解いている

A問題

atcoder.jp

考察

• 入力で与えられた手を元に考える
• xとyが同じなら、同じ手を出力するとあいこになる
• xとyが違うなら、xともyとも違う手を出すとあいこになる

実装

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

if x == y:
    print(x)
else:
    ans = [0, 1, 2]
    ans.remove(x)
    ans.remove(y)
    print(ans[0])

結果

• 無事に解けた

B問題

atcoder.jp

考察

• N<=1000 なので全文探索で考える
• 10個以上の場合のみ、10個残した数を足し続けていく

実装

N = int(input())

ans = 0

for a in map(int, input().split()):
    if a > 10:
        ans += a-10

print(ans)

結果

• 無事に解けた

C問題

atcoder.jp

考察

• N<=2000 なので2重ループくらいまではやっても良さそう
• 行ったら帰ってこれないので、「有向グラフ」で考える
• グラフの探索で、ゴールまで探索しないといけないので「深さ優先探索(dfs)」を使って探索する

qiita.com

実装

import sys

sys.setrecursionlimit(100000000)

N, M = map(int, input().split())

ans = 0
graph = [[] for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    graph[A-1].append(B-1)


def dfs(v):
    global ans

    find[v] = True
    ans += 1
    for next in graph[v]:
        if not find[next]:
            dfs(next)


if M > 0:
    for i in range(N):
        find = [False] * N
        dfs(i)
else:
    ans = N

print(ans)

結果

• 無事に解けた

D問題

コンテスト中は解けず、後日解説見ながら解いた

atcoder.jp

考察

• 数列を二つに分け(数列A, B)、max(A, B)の最小値を考える問題
• 「部分和問題」という動的計画法(DP)等を用いて解ける提携問題らしい
  • 最大N=100個なので、2つのグループにそれぞれ分ける方法で全文探索するとTLEする

qiita.com

実装

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

dp = [[False] * (s + 1) for _ in range(N + 1)]
dp[0][0] = True

for i in range(N):
    for j in range(s + 1):
        if T[i] <= j:
            dp[i + 1][j] = dp[i][j - T[i]] or dp[i][j]
        else:
            dp[i + 1][j] = dp[i][j]

for i in range(s//2, s+1):
    if dp[N][i]:
        print(max(i, s-i))
        break

結果

• 無事に解けた

まとめ

• C問題が、DFS使うところに気づけて、時間内に解けたのがよかった
  • 成長している気がした
• D問題で、DPの勉強をして、実際に時間かかったが解けたので、これからもDPの勉強を続けていきたい
  • DPはよく出るし、応用範囲も広いのでぜひ身につけたい！