A - Remaining Balls

二種類の文字列とそれぞれに属するボールの数を与えられ、どちらか指定されたボールを一個取り出してからそれぞれの数を出力する問題です。

入力Uはどちらかの文字列には一致することが指定されているのはポイント。

S, T = input().split()
A, B = map(int, input().split())
U = input()

if U == S: A -= 1
else: B -= 1
print(A, B)

B - I miss you...

指定された文字列を'x'に置き換えて出力する問題です。

入力された文字数分だけのxを返しました。

S = input()
print("x" * len(S))

C - Distinct or Not

入力された配列に重複がないか調べる問題です。

set型に入れることで重複なしの配列長を調べました。出力が'Yes'じゃなくて'YES'であることに注意しましょう(一敗)。

N = int(input())
A = list(input().split())

if len(set(A)) == N:
  print('YES')
else:
  print('NO')

D - Dice in Line

値$p_i$を最大値とするサイコロから、隣接した番号のサイコロK個を抜きだして期待値を答える問題です。

期待値はそれぞれのサイコロごとに独立した値なので、足し算引き算が可能です。まずそれぞれの期待値を求めて、それぞれのサイコロの持つ最大値を上書きしてしまいます。

あとはインデックスをずらしながら（ずらして抜ける値は減らし、加わる値は増やして）最大値を探しました。

N, K = map(int, input().split())
P = list(map(int, input().split()))

P = [(1+p)/2 for p in P]

tmp = sum(P[:K])
maxV = tmp

for i in range(N-K):
  tmp += P[i+K] - P[i]
  maxV = max(maxV, tmp)
print(maxV)

E - Almost Everywhere Zero

十進数表記で1~9までの数字がK個入るN桁の数字の数を答える問題です。

1からN桁の999...までの数字に条件を満たす数は
$$ {}_N C _K \times 9^K $$
だけある...で、だから？という感じで探索の方法がわからず諦めました。以下の解答にこの計算式は使用しません。

解説を見ました。桁DPというアルゴリズムを使うそうです。こちらを参考に桁DPを学びました。

このような三次元配列を作成します。

dp[i][smaller][k]

ここでiは左端を1として数えた桁数(もう一つ左に値0の0桁目が存在すると考える)、smallerは1ならそこまでの桁が取りうる最大値を取っていないこと、kはその桁までの登場した0以外の数字の個数を表します。

こういうルールで左から順番に数えたものが以下のコードです。処理の細かい解説は厄介なので省略します。

これで通りました。

N = [0] + list(map(int, input()))
N = [0] + list(map(int, input()))
K = int(input())
n = len(N)

DP = [
      [[0] * (K+2) for _ in range(2)] for _ in range(n)
]

# 0桁目(0)で最大値を取っていてk=0の要素は1個。
DP[0][0][0] = 1

for i in range(1, n):
  for k in range(K+1):
    if N[i] != 0:
      DP[i][0][k+1] += DP[i-1][0][k]
      DP[i][1][k] += DP[i-1][0][k]
      DP[i][1][k+1] += DP[i-1][0][k] * (N[i] - 1)
    else:
      DP[i][0][k] += DP[i-1][0][k]
    DP[i][1][k] += DP[i-1][1][k]
    DP[i][1][k+1] += DP[i-1][1][k] * 9
print(DP[n-1][1][K] + DP[n-1][0][K])

この記事はここまでとします。