AtCoder Beginner Contest 184をPythonで解く

AtCoder Beginner Contest 184の問題をPythonで解いてみました。

A - Determinant

求める値$ad - bc$を出力します。

main.py (A - Determinant)

a, b = map(int, input().split())
c, d = map(int, input().split())

print(a*d-b*c)

B - Quizzes

「クイズに正解すると$1$点増え、不正解だと$1$点減る」を律儀に行って、出力します。

main.py (B - Quizzes)

n, x = map(int, input().split())
s = list(input())

for i in range(n):
  # i番目の文字列が"o"かそうでないかを判定し, 得点に点数を加える
  if s[i] == "o":
    x += 1
  else:
    # 持っている点数が0点のときに不正解となった場合は点数は減らない
    x = max(0, x - 1)

print(x)

C - Super Ryuma

マス目を移動できる条件を再掲します。

• A：$a + b = c + d$
• B：$a - b = c - d$
• C：$|a - c| + |b - d| \leq 3$

移動A・Bを高々$2$回行えば、全マス目の半分の場所(市松模様にしたときに同じ色の場所)には移動できます。もう半分だけは、移動A・Bに加えて移動Cが必要です。

したがって、$0$回、$1$回、$2$回で移動できるかどうかを判定すれば、それ以外は$3$回で移動できると判定すればよいです。

• $0$回：同じマスかどうかの判定
• $1$回：上記3つの移動可能条件のどれかに当てはまるかの判定
• $2$回：
  • 移動A・Bの組み合わせは $((a - c) + (b - d)) \ \mathrm{mod} \ 2 = 0$
  • 移動C・Cの組み合わせは $|a - c| + |b - d| \leq 6$
  • 移動A・Cの組み合わせは $|(a - c) + (b - d)| \leq 3$
  • 移動B・Cの組み合わせは $|(a - c) - (b - d)| \leq 3$

main.py (C - Super Ryuma)

r1, c1 = map(int, input().split())
r2, c2 = map(int, input().split())
r = r2 - r1
c = c2 - c1

# 0回判定
if (r,c) == (0,0) :
  print(0)
# 1回判定(移動A)
elif r == c :
  print(1)
# 1回判定(移動B)
elif r == -c :
  print(1)
# 1回判定(移動C)
elif abs(r) + abs(c) <= 3 :
  print(1)
# 2回判定(移動A・B)
elif (r + c) % 2 == 0 :
  print(2)
# 2回判定(移動C・C)
elif abs(r) + abs(c) <= 6 :
  print(2)
# 2回判定(移動A・C)
elif abs(r+c) <= 3 :
  print(2)
# 2回判定(移動B・C)
elif abs(r-c) <= 3 :
  print(2)
# 3回判定(それ以外)
else :
  print(3)

D - increment of coins

金貨が$X$枚、銀貨が$Y$枚、銅貨が$Z$枚のときの操作回数の期待値を$f(X, Y, Z)$とします。

$X$、$Y$、$Z$のいずれかが$100$の場合には操作は完了するので、

f(X, Y, Z) = 0

です。$0 \leq X, Y, Z \leq 99$の場合は

f(X, Y, Z) = \frac{X}{X + Y + Z} \left( f(X + 1, Y, Z) + 1 \right) + \frac{Y}{X + Y + Z} \left( f(X, Y + 1, Z) + 1 \right) + \frac{Z}{X + Y + Z} \left( f(X, Y, Z + 1) + 1 \right)

です。

以上の漸化式をもとに、動的計画法で計算します。

main.py (D - increment of coins)

a, b, c = map(int, input().split())

dp = [[[0 for i in range(101)] for j in range(101)] for k in range(101)]
for i in range(100,-1,-1):
  for j in range(100,-1,-1):
    for k in range(100,-1,-1):
        if i == 0 and j == 0 and k == 0:
            dp[i][j][k] = 0
        elif i == 100 or j == 100 or k == 100 :
            dp[i][j][k] = 0
        else:
            dp[i][j][k] = dp[i + 1][j][k] * i / (i + j + k) + dp[i][j + 1][k] * j / (i + j + k) + dp[i][j][k + 1] * k / (i + j + k) + 1

print(dp[a][b][c])

あるいは、「メソッドのある引数に対する計算結果を保存しておき、後で同じ引数が与えられたとき、計算結果を再利用する」機能であるlru_cacheを使用できます。

main.py (D - increment of coins)

from functools import lru_cache

@lru_cache(None)
def f(i, j, k):
    if i == 100 or j == 100 or k == 100:
        return 0
    t = i + j + k
    return (f(i + 1, j, k) + 1) * i / t + (f(i, j + 1, k) + 1) * j / t + (f(i, j, k + 1) + 1) * k / t

a,b,c = map(int,input().split())
print(f(a, b, c))

参考にしたサイト等