【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月中に入緑を目指して頑張りたいと思います。
お疲れ様でした。