EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC219をpythonで解いてみた

Atcoder 競技プログラミング

目的

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

X = int(input())

if X < 40:
    print(40-X)
elif 40 <= X and X < 70:
    print(70-X)
elif 70 <= X and X < 90:
    print(90-X)
else:
    print("expert")

結果

B問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

S1, S2, S3 = input(), input(), input()
T = input()

ans = []

for t in T:
    if t == "1":
        ans.append(S1)
    elif t == "2":
        ans.append(S2)
    else:
        ans.append(S3)

print(*ans, sep="")

結果

C問題

atcoder.jp

考察

久々にC問題で取りこぼして2完に

独自の辞書順のものを、通常のアルファベット順に直し、sortしたのちに、戻すのが簡単そう

  • あっさり解けた
    • sortを独自で作るのとかはなかなかハードル高い

実装

X = list(input())
N = int(input())

tmp, ans = [], []

for _ in range(N):
    S = input()
    string = [chr(97 + X.index(s)) for s in S]
    tmp.append("".join(string))

tmp.sort()

for i in range(len(tmp)):
    s = tmp[i]
    string = [X[(ord(c)-97)] for c in s]
    ans.append("".join(string))

print(*ans, sep="\n")

結果

D問題

atcoder.jp

考察

DPであることはすぐに気づいたが、DPが組み立てられず、時間切れ

  • 下記の方針を2本を考えた
    • i個目の弁当を考え、j個のたこ焼き、k個のたい焼きを考える
      • 3重ループになって大変そう？
    • 弁当を取るかどうか？の話なので、DPの値をtupleで持ってみる？
      • たこ焼き、たい焼きのそれぞれをどのように更新するかのロジックが組めず・・・

f:id:kazu_0716:20210924231746p:plain
ABC219 D問題メモ

素直に3重ループで解けた

  • 1sちょっとで、時間はかかるが、時間内に解けた

実装

N = int(input())
INF = pow(10, 9)
X, Y = map(int, input().split())

dp = [[[INF] * (Y+1) for _ in range(X+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    A, B = map(int, input().split())
    for j in range(X+1):
        for k in range(Y+1):
            x, y = min(j+A, X), min(k+B, Y)
            dp[i][x][y] = min(dp[i][x][y], dp[i-1][j][k]+1)
            dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k])

ans = dp[-1][X][Y]

if ans == INF:
    print(-1)
else:
    print(ans)

結果

まとめ

  • 今回2完で、大きくレートを落とした・・・
    • 腐らず、また頑張っていこうと思う

f:id:kazu_0716:20210924232640p:plain
ABC219の結果

  • 今回のが悔しかったので、Educational DP Contestの問題を、解き進めてDPの理解を深めた
    • まだまだ歴が浅く、苦手が出るとrateを大きく落とすことがあるので、都度見つけたら重点的に弱点を補強して行きたい

I問題まで解いた

  • いろんなDPを組むパターンを覚えて、応用できるようにしたい