RONの技術ブログ

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

【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を連発してしまい、順位が奮いませんでした。
    気を取り直して次回も頑張りたいと思います。
    お疲れ様でした。