Review of AtCoder Beginner Contest 154, up to question E (Python)

This is a review article for beginners of competition professionals.

The solution I write here is written while looking at the commentary and other people's submissions. It may not be what you actually submitted.

A - Remaining Balls

Given two types of character strings and the number of balls belonging to each, the problem is to take out one of the specified balls and then output each number.

The point is that the input ʻU` is specified to match either string.

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...

This is a problem to replace the specified character string with'x'and output it.

Returns x for the number of characters entered.

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

C - Distinct or Not

The problem is to check the input array for duplicates.

I checked the array length without duplication by putting it in the set type. Note that the output is'YES'instead of'Yes' (one loss).

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

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

D - Dice in Line

It is a problem to answer the expected value by extracting K dice with adjacent numbers from the dice whose maximum value is $ p_i $.

The expected value is an independent value for each dice, so addition and subtraction are possible. First, find the expected value of each and overwrite the maximum value of each dice.

After that, I searched for the maximum value while shifting the index (decreasing the value that exits by shifting and increasing the value that is added).

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

It is a question to answer the number of N-digit numbers that can contain K numbers from 1 to 9 in decimal notation.

The number that satisfies the numbers from 1 to N digits 999 ... $ {}_N C _K \times 9^K $ There is only ... so? I didn't know how to search and gave up. This formula is not used in the following answers.

I saw the commentary. It seems to use an algorithm called digit DP. I learned digit DP by referring to here.

Create a three-dimensional array like this.

dp[i][smaller][k]

Here, ʻiis the number of digits counted with the left end as 1 (think that there is another 0th digit with a value of 0 on the left), andsmalleris the maximum value that the digits up to that can take if it is 1. No,k` represents the number of non-zero digits that have appeared up to that digit.

The code below counts from the left according to these rules. A detailed explanation of the process is awkward, so I will omit it.

I passed by this.

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)
]

#0th digit(0)Takes the maximum value with k=There is one 0 element.
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])

That's all for this article.