[PYTHON] Codeforces Round # 645 (Div. 2) Bacha Review (9/10)
This time's results
Impressions of this time
This time, the computer froze and restarted repeatedly, so it was not very helpful as a result. However, I think I was able to solve the D problem in less time, so I would like to continue to do my best.
Problem A
I don't like problem sentences very much, but it's good to think about arranging tiles.
Arrange the tiles of $ 1 \ times 2 $. If $ n \ times m $ is even, you can just line up the tiles, so $ \ frac {n \ times m} {2} $ is the answer. When $ n \ times m $ is odd, even if they are arranged well, there are surplus tiles of $ 1 \ times 1 $, so additional tiles are needed. $ \ Frac {n \ times m -1} {2} + 1 $ Is the answer.
A.py
for _ in range(int(input())):
n,m=map(int,input().split())
if n%2==0 or m%2==0:
print(n*m//2)
else:
print((n*m-1)//2+1)
Problem B
The problem was so long that it seemed to be sharp. The essence was simple and sharp.
It is easy to solve if you think using Example. Also, the number of people required by each person is sorted in ascending order and saved in ʻa`. At this time, it is good to move people who can move ** at once **. Furthermore, the maximum number of people who can move is ** $ a [0], a [1],…, a [i] \ leqq i + 1 $ holds **, which is the largest $ i $ +2 It will be the one that was done. Here, $ a [0], a [1],…, a [i] \ leqq i + 1 \ leftrightarrow a [i] \ leqq i + 1 $, so you can easily determine with the for statement. .. If there is no element that holds $ a [i] \ leqq i + 1 $, the answer is 1.
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
a.sort()
for i in range(n-1,-1,-1):
if a[i]<=i+1:
print(i+2)
break
else:
print(1)
C problem
When I started to solve this problem, my computer broke and I couldn't think about it. I want to be calm even if I am hit by an accident.
Normally, if you search all the way **, you can think of BFS **, but the square cannot be $ (10 ^ 9) ^ 2 $. Then, ** go vertically or horizontally ** to $ \ _ {(x \ _2-x \ _1) + (y \ _2-y \ _1)} C _ {(x \ _2-x ) _1)} $ There are so I wanted to ask for this, but there aren't that many. In other words, ** it may be the same number by following different routes **, so I experimented and thought about it. For example, considering the figure below, there are $ \ _4 C \ _2 = 6 $ routes, but there are only 5 routes, $ 68,69,70,70,71,72 $.
After all, I wanted to find out how many numbers there are, so I thought that ** upper and lower limits could be found **. At this time, since the number increases from diagonally above to bottom, it can be seen that the route going to the right and going down is the smallest and the route going down and going to the right is the largest. Therefore, consider ** finding the difference ** (and we need to prove that the integer between the upper and lower limits can be represented by a suitable path, but we have made it clear here).
To find the difference, I thought of an example of $ x \ _2-x \ _1 \ neq y \ _2-y \ _1 $, and considered the following example.
Since it is only necessary to consider the difference, it is expressed in the form of (+ integer). At this time, you can see that the number of + is increased one by one by looking at the above figure. This is because, as you can see from the red diagonal line, the diagonal difference increases. Also, the number of + is only $ min (x \ _2-x \ _1, y \ _2-y \ _1) $ at most. In other words, the numbers that are + as $ m = min (x \ _2-x \ _1, y \ _2-y \ _1)) $ are summarized as follows.
(1) When the number of + is increased
-Is the last because the lower left element is counted twice.
(2) When the number of + is reached the upper limit
Therefore, since the difference was obtained above, it should be (difference) +1.
C.py
for _ in range(int(input())):
x1,y1,x2,y2=map(int,input().split())
a,b=(x2-x1+1),(y2-y1+1)
if a>b:
a,b=b,a
print((a-2)*(a-1)+(a-1)+(a-1)*(b-a)+1)
D problem
I was able to come up with this problem quickly, but it was difficult to implement.
Consider the case where the days are assigned in order from 1 in each month, and when you select consecutive $ x $ days, the total of the days is the maximum.
At this time, ** the biggest candidate is ** if you select until the end of each month **. Also, since there are $ n $ of months, I found that it could be implemented with $ O (n) $ by translating ** $ x $ days and managing the difference **.
The problem in implementation is "** How many months are you selecting when you select the end of a month " and " How many days are you selecting for a month that has an odd date selected ** ". This can be implemented by splitting into a fully selected minimum monthly $ now1 $ and a total of $ now2 $ for that day, and an additional $ add1 $ for the selected day and a total of $ add2 $ for that day. Also, if there is no completely selected month, set $ now1 = inf $.
Here, it is implemented by performing operations in descending order of $ i = n-1 \ rightarrow 0 $ according to the following cases. Also, let the dates that need to be searched additionally be $ x $, and the sum of the dates of the $ i $ th month be $ a [i] $.
(1) When $ now1 = inf $ or $ now1 = i + 1 $
In this case, there is no completely selected month, so initialize it with $ now1 = inf, now2 = 0, add1 = 0, add2 = 0 $ and search for $ check = x $ days.
[1] $ check <d [i] $ There is no completely selected month, and $ now1, now2 $ remains unchanged. $ add1, add2 $ needs to be updated, $ add1 = check, add2 = \ sum_ {j = 0} ^ {check-1} (d [i] -j) = \ frac {(2d [i]- check + 1) \ times check} {2} $.
[2] $ check \ geqq d [i] $ There is a fully selected month, and $ now1 = i, now2 = a [i], check = x-d [i] $ are confirmed. In addition, there may be more completely selectable months, so decrement $ now1 $ and add to $ now2 $ while turning the while statement with $ check \ geqq d [now1-1] $ as the loop condition. , The surplus is calculated by putting it in $ add1 and add2 $.
(2) In the case of $ now1 \ neq inf $ and $ now1 \ neq i + 1 $
$ now1, now2 $ does not need to be initialized. Also, let's set $ check = add1 + d [i + 1] $ to consider which month the surplus $ add1 $ will be paid out. Also, set 0 for both $ add1 and add2 $.
In (1), there was no month that was completely selected, so I started from the $ i $ th month, but in (2), I have already completely selected up to $ now1 $. Therefore, the next thing to look for is $ now1-1 $, and a similar implementation can be achieved by replacing $ i $ in the discussion in (1) with $ n-1 $.
✳︎… Implementation is easy if you are aware of ** ① case classification, ② initialization, ③ difference processing **.
D.py
n,x=map(int,input().split())
d=list(map(int,input().split()))
a=[i*(i+1)//2 for i in d]
inf=100000000000
ans=0
#now1:How far did you take it completely(When not completely-1)
now1=inf
#now2:What is the total of the parts taken completely?
now2=0
#add1:How much was added
add1=0
#add2:What is the total of the additional parts taken?
add2=0
for i in range(n-1,-1,-1):
if now1==inf or now1==i+1:
check=x
now1=inf
now2=0
add1=0
add2=0
if check<d[i]:
#now1 does not work
now2=0
add1=check
add2=(2*d[i]-check+1)*check//2
else:
now1=i
now2=a[i]
check-=d[i]
while check>=d[now1-1]:
check-=d[now1-1]
now2+=a[now1-1]
now1-=1
add1=check
add2=(2*d[now1-1]-check+1)*check//2
else:
#Delete when taking
#check is an additional value
check=add1+d[i+1]
add1=0
add2=0
now2-=a[i+1]
if check<d[now1-1]:
#now1 does not work
add1=check
add2=(2*d[now1-1]-check+1)*check//2
else:
while check>=d[now1-1]:
check-=d[now1-1]
now2+=a[now1-1]
now1-=1
add1=check
add2=(2*d[now1-1]-check+1)*check//2
#print(now1,now2,add1,add2)
ans=max(now2+add2,ans)
print(ans)
After the E problem
I will skip this time
Recommended Posts