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 - The Number of Even Pairs The question is to answer the number of combinations of N balls with even numbers and M balls with odd numbers, for which the total is even.
The answer is simply to combine the even-numbered combination $ N (N-1) / 2 $ and the odd-numbered combination $ M (M-1) / 2 $.
N, M = map(int, input().split())
print((N*(N-1))//2 + (M*(M-1))//2)
B - String Palindrome
It is a problem to judge whether the given character string is a "palindrome that combines two palindromes".
Whether the four character strings of the first half on the left side, the second half on the left side, the first half on the right side, and the second half on the right side match is determined by turning up to 1/4 of the character string N.
s = input()
n = len(s)
for i in range((n-1+3)//4):# +3 is for rounding up
if not(s[i] == s[(n-1)//2-i-1] and s[(n+3)//2 + i-1] == s[-i-1] and s[i] == s[-i-1]):
print('No')
exit()
print('Yes')
When I looked at other answers and explanations, there was a cleaner way to write.
s = input()
n = len(s)
sl = s[:n//2]
sr = s[n//2+1:]
if sl == sr and sr == sr[::-1]:
print('Yes')
else:
print('No')
Divide the character string into left and right, and if the right `sr``` is a palindrome, the sl that matches it is also a palindrome. Since `` `sl and sr are matching palindromes, it is a palindrome even if the two are combined. Only two conditions were required.
C - Maximum Volume The total height, width, and height is the problem of answering the maximum volume of a rectangular parallelepiped of L.
When height = width = height, the volume is the maximum, so the length of each is $ L / 3 $. Just cube this.
L = int(input())
print((L/3)**3)
I couldn't explain why it is the maximum when the lengths of the sides match, so I will write a mathematical explanation for the time being.
The following is the formula for the additive geometric mean with three variables.
D - Banned K
It is a problem to think about how many combinations to select the same number from N balls with numbers written on them, excluding the balls.
First, find the total number of combinations $ S $ from all the balls. From there, when there are $ m $ balls with the number $ n $, if you take out one ball with the number $ n $, the total $ S $ will be reduced by $ m-1 $. The number $ n $ is applied to each ball to be taken out and output.
import collections
N = int(input())
li = list(map(int, input().split()))
cn = collections.Counter(li)
sumC = sum([n*(n-1)//2 for n in cn.values()])
for k in range(N):
print(sumC-cn[li[k]] + 1)
E - Dividing Chocolate
It is a question of answering the number of times to divide so that the amount of white chocolate in the chocolate bar is below a certain level.
I gave up because I didn't understand either "the idea of exploration" or "how to count the number of white chocolates in the split".
I saw the commentary. Since there is a narrow range specification of $ H \ leq 10 $, the horizontal division can be straightforward to search all $ 2 ^ {H-1} $ streets. For a full search, use ʻitertools.product ()` to create a complete array of length H-1 containing 0s or 1. Search is OK with this.
Chocolates that are split horizontally are stored in the two-dimensional array SW as a one-dimensional array that counts the number of white chocolates vertically, and are counted from the left. If the number of chocolates in any column exceeds the specified number K, divide the chocolates vertically and return the count to 0. You can also count chocolates with this. However, if the value of the one-dimensional array exceeds K, it is impossible to divide the chocolate many times, so the situation should be redone from the sideways division.
So the code looks like this:
import itertools
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 1e4
for t in itertools.product([0, 1], repeat=H-1):
cnt = t.count(1)
SW = []
tmp = [int(s) for s in S[0]]
for i, c in enumerate(t):
if c:
SW.append(tmp)
tmp = [int(s) for s in S[i+1]]
else:
tmp = [tmp[j] + int(S[i+1][j]) for j in range(W)]
SW.append(tmp)
H_ = len(SW)
sums = [0] * H_
if max(itertools.chain.from_iterable(SW)) > K:
continue
for w in range(W):
sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
if max(sumtmp) > K:
cnt += 1
sums = [SW[i][w] for i in range(H_)]
else:
sums = sumtmp
ans = min(ans, cnt)
print(ans)
This article ends with question E for the time being.
Recommended Posts