【AtCoder】ABC201 感想戦
2021/5/15の開催されたABC201を振り返ります。
結果はA~Cの3完でした。C問題に手こずってしまいました。
順位:4241位、パフォーマンス:619、レート:686→679(茶)
- A問題:A - Tiny Arithmetic Sequence
数列を並び替えて等差数列にできるかどうかを判断する問題です。
まずソートして、要素間の差を比較すればよいです。
A = list(map(int, input().split())) A.sort() if (A[1]-A[0]) == (A[2]-A[1]): print("Yes") else: print("No")
- B問題:B - Do you know the second highest mountain?
与えられた入力から2番目に高い山を出力する問題です。
同じ高さの山はありません。
これはkeyを指定してソートする方法を知っていれば簡単です。
N = int(input()) ST = [] for _ in range(N): S, T = input().split() T = int(T) ST.append([S, T]) ST.sort(key=lambda x: x[1], reverse=True) print(ST[1][0])
- C問題:C - Secret Number
絶対使った数字、使ったかもしれない数字、絶対使ってない数字の情報からあり得る4桁の暗証番号が何通りあるか求める問題です。
数学的に解こうとして手間取ってしまいましたが、素直に10000通り全探索すればよかったんですね。
S = input() ans = 0 for v in range(10000): v = str(v).zfill(4) res = 1 for i, x in enumerate(S): # 絶対に使っている数字なのに、暗証番号にない場合 if x == "o" and str(i) not in v: res = 0 # 絶対に使ってないのに、暗証番号にある場合 elif x == "x" and str(i) in v: res = 0 ans += res print(ans)
- D問題:D - Game in Momotetsu World
動的計画法で解こうと思いたちましたが、どう定義するかわかりませんでした。
dp[i][j]: コマが(i, j)にあるときの「高橋得点 - 青木得点」の最適値
ゴールから逆算して処理していくのがポイントです。
H, W = map(int, input().split()) A = [input() for _ in range(H)] dp = [[0]*W for _ in range(H)] for i in reversed(range(H)): for j in reversed(range(W)): if i == H-1 and j == W-1: continue dp[i][j] = - float("inf") if i+1 < H: score = 1 if A[i+1][j] == "+" else -1 dp[i][j] = max(dp[i][j], -dp[i+1][j] + score) if j+1 < W: score = 1 if A[i][j+1] == '+' else -1 dp[i][j] = max(dp[i][j], -dp[i][j+1] + score) if dp[0][0] == 0: print("Draw") if dp[0][0] > 0: print("Takahashi") if dp[0][0] < 0: print("Aoki")
- まとめ
CでWAを連発してしまい、順位が奮いませんでした。
気を取り直して次回も頑張りたいと思います。
お疲れ様でした。