AtCoder Beginner Contest 185 - AtCoder
This is the third consecutive time ABC has answered all questions correctly!
A
- I submitted it without testing it and got a syntax error due to missing parentheses, I thought it was easy and cut too many corners, sorry. python
print(min(list(map(int, input().split()))))
C - Duodecim FerraC - Duodecim Ferra
- Combination of 11 cutting locations to be selected from L-1 possible cutting locations python
def main():
L = int(input())
print(comb(L - 1, 12 - 1))
- According to the official explanation, it was an “I said the answer was less than 2^63, but I didn’t say the numerator was” type trap overflow trap.
- I’m a Python user, so I solved it without worrying about anything.
- Smaller than the maximum possible stamp size will not result in a better score.
- Calculate score to find maximum stamp size
- Maximum stamp size is minimum gap size
- It doesn’t say that the input is sorted, so sort it (I noticed a minus in the test at hand).
- I put a guard in front and back to get the gap size.
- When the difference of coordinates is 2, the size of the gap is 1
- The score you want is python
def main():
N, M = map(int, input().split())
AS = list(map(int, input().split()))
AS.append(0)
AS.append(N + 1)
AS.sort()
DS = []
for i in range(M + 1):
d = AS[i + 1] - AS[i]
if d > 1:
DS.append(d - 1)
if not DS:
print(0)
return
k = min(DS)
ret = 0
for d in DS:
ret += (d - 1) // k + 1
print(ret)
- Just use segmented trees.
- According to the official explanation, Fennic tree is also acceptable.
- I had a hard time, but when one of them had zero letters left, I had to delete it, so I did a DP with the number of letters left and solved it with O(NM).
- Thoughts.
- O(N^3) is no good since N=1000, O(N^2logN) and O(N^2) are OK
- Do you only take it from the long side?
- I wouldn’t be so sure about that.
- When the number of remaining characters reaches (x, 0), all that remains is to delete x characters.
- I drew a diagram of what’s fixed by this rule, and I could see straightforward dynamic programming.
python
def solve(N, M, AS, BS):
if M > N:
N, M = M, N
AS, BS = BS, AS
table = list(range(N + 1))
for m in range(1, M + 1):
newtable = [0] * (N + 1)
prev = newtable[0] = m
for n in range(1, N + 1):
if AS[-n] == BS[-m]:
d = 0
else:
d = 1
prev = newtable[n] = min(
prev + 1,
table[n - 1] + d,
table[n] + 1
)
table = newtable
return table[-1]
- I see a lot of people on Twitter talking about Longest Common Substring.
- Related:edit distance
This page is auto-translated from /nishio/ABC185 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.