[PYTHON] AtCoder Beginner Contest 072 Review of past questions
The second past question that I have already solved
Time required
Problem A
Case by whether or not the sand runs out
answerA.py
x,t=map(int,input().split())
print(max(x-t,0))
B problem
All you have to do is fetch the odd letters You can write more concisely by setting steps like the second (Python string manipulation Too good)
answerB.py
s=input()
l=len(s)
t=""
for i in range(l):
if i%2==0:
t+=s[i]
print(t)
answerB_better.py
s=input()
print(s[0:len(s):2])
C problem
The first method I came up with during the virtual console. When a certain number x is selected, the total number of x-1, x + 1 combined should be maximized, so subtract the maximum number of indexes above i-1 from the index of the number larger than i + 1. You can see that the number of things is written by hand and experimented. (This method was a little difficult. It's good to be able to use binary search. ** Searching for sorted things is binary search! **) The second method is the ideal solution. This solution simply records how many of each number is in an array and outputs the one with the maximum sum of i-1, i, i + 1. Easy.
answerC1.py
import bisect
n=int(input())
a=sorted([int(i) for i in input().split()])
ma=0
for i in range(10**5):
ma=max(bisect.bisect_right(a,i+1)-bisect.bisect_left(a,i-1),ma)
print(ma)
answerC2.py
import bisect
n=int(input())
a=[int(i) for i in input().split()]
b=[0]*(10**5)
for i in range(n):
b[a[i]]+=1
ma=0
for i in range(1,10**5-1):
ma=max(b[i-1]+b[i]+b[i+1],ma)
print(ma)
D problem
Since you can only swap two adjacent ones, it is clear that swapping from the front is the least frequent. (How can I prove it ... ??) When pi = i, swapping pi and pi + 1 to make pi ≠ i is repeated in order from i = 1 to n-1, and pi ≠ i holds when i <= n-1, so the last i Swap with pn and pn−1 only when = n is pi = i. Also, since pn = n at this time, it should be noted that pn−1 ≠ n−1 is satisfied even if swapped. Furthermore, when I solved it before, I was not aware of the preamble and was spinning the loop once more with i = n-1 ~ 1. (It is clear that only pn and pn-1 swap occurs when the loop is turned, so it is OK)
answerD.py
n=int(input())
p=[int(i) for i in input().split()]
c=0
for i in range(n-1):
if p[i]==i+1:
p[i],p[i+1]=p[i+1],p[i]
c+=1
if p[-1]==n:
p[-1],p[-2]=p[-2],p[-1]
c+=1
print(c)
Recommended Posts