RONの技術ブログ

駆け出しエンジニアの備忘録

【AtCoder】ABC204 感想戦

2021/6/6に開催されたABC204を振り返ります。
結果はA~Cの3完でした。
順位:3449位、パフォーマンス:778、レート:742→746(茶)

  • A問題:A - Rock-paper-scissors
    じゃんけんであいこを出す問題です。
    あいこになるパターンは2つあって、全て同じ手か、全て違う手である。
    よって、XとYが同じなら同じ手を、XとYが違うなら残りの手を出力すれば良い。
def main():
    X, Y = map(int,input().split())

    if X == Y:
        return X
    else:
        return 3 - X - Y

print(main())
  • B問題:B - Nuts
    木に実が実っていて、実の数が10個以下なら収穫せず、10個以上なら10個を残して残りの全てを収穫する。
    これは単純にそれぞれ木毎に10個以上であれば余剰分を答えに足していけばよい。
def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0

    for a in A:
        if a > 10:
            ans += a - 10
    
    return ans

print(main())
  • C問題:C - Tour
    C問題でグラフっぽい問題が出ましたね。
    BFSで解いている人が多かったですが、私はDFSで解きました。
    この問題、最初の2行は再帰回数の上限を増やすおまじないですが、これを書き忘れて2回ほどREを出してしまい、やらかしました。
    解法としては、各地点スタートにした時のゴールとしてあり得る地点をDFSでみていきました。
    初めて本番でDFSが自力で解けました。
    成長を実感しました。
import sys
sys.setrecursionlimit(1000000)

N, M = map(int,input().split())
g = [[] for _ in range(N+1)]
ans = 0

def dfs(v):
    if visited[v]:
        return
    
    visited[v] = True
    global ans
    ans += 1
    for nv in g[v]:
        dfs(nv)

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

for i in range(N):
    visited = [False] * (N+1)
    dfs(i)

print(ans)
  • D問題:D - Cooking
    オーブンを使うスケジュールを最適化する問題です。
    問題を見た時、解けそう!と興奮しましたが、結局解けませんでした。
    Dにしてはチャンス問題だったのでは、と思います。
    方針としては、Tの総和の半分より大きい数字かつ最小の数値をTの部分集合で作る、です。
    以下のようにDPで解けます。
import math
def main():
    N = int(input())
    T = list(map(int, input().split()))
    S = sum(T)

    # Tの部分集合を用いてS/2より大きい数値かつ最小のものを作る。
    # dp[i]: Tの部分集合を用いて合計iを作れるか。
    dp = [False] * (S+1)
    dp[0] = True

    for t in T:
        for i in range(S, t-1, -1):
            # tを見ている場合、i-tが作れるならばiも作れる。
            dp[i] |= dp[i-t]
    
    ans = math.ceil(S/2)

    # Tの総和の半分から一つずつインクリメントしていき、作れる数がでてきたらそれが答えになる。
    while dp[ans] == False:
        ans += 1
    
    return ans

print(main())
  • まとめ
    今回はCで凡ミスでREを2回喰らい、レートは現状維持でした。
    D解きたかった...
    とはいえCのDFSを自力で解けたのは嬉しかったです。
    6月中に入緑を目指して頑張りたいと思います。
    お疲れ様でした。