Open3ヶ月前にコメント追加2

ABC201メモ

C

ポイント

全探索できることに秒で気づくべき（4桁）
pythonのちょっとした文法知識があると楽に書ける
- format文字列
- for-else

def main():
    S = IS()
    ans = 0
    for i in range(10000):
        fmt_num = f"{i:04d}"
        for j in range(10):
            if (S[j] == "o" and str(j) not in fmt_num) or (S[j] == "x" and str(j) in fmt_num):
                break
        else:
            ans += 1
    print(ans)
    return

t_shunsuke

D

ポイント

ゲームDPの割と典型
「相手との得点差の最大値」を考える
再帰DFS解法でPypy、CPythonだとTLEを食らった。（Rustだと100ms未満）
- トップダウン的なDFSからボトムアップ的なループに変更することで解消
+/- を予め +1/-1 に変換しておくと少し処理しやすい

def main():
    H, W = INN()
    A = [IS() for _ in range(H)]

    dp = [[0] * W for _ in range(H)]
    sign = [[(1 if c == '+' else -1) for c in row] for row in A]

    for i in reversed(range(H)):
        for j in reversed(range(W)):
            if i == H - 1 and j == W - 1:
                continue
            ans = -INF
            if i + 1 < H:
                tmp = sign[i + 1][j] - dp[i + 1][j]
                ans = max(ans, tmp)
            if j + 1 < W:
                tmp = sign[i][j + 1] - dp[i][j + 1]
                ans = max(ans, tmp)
            dp[i][j] = ans

    if dp[0][0] == 0:
        print("Draw")
    elif dp[0][0] > 0:
        Takahashi()
    else:
        Aoki()
    return

ログインするとコメントできます