Codeforces Round # 663 (Div. 2) Bacha Review (8/16)
This time's results
Impressions of this time
Personally, I don't want to solve unrated times so much, but I did not notice it.
Problem A
I was also surprised by the gag problem. Does Kodfo have such a tendency ...?
$ a \ _x + a \ _y \ neq a \ _z $ should consist of any ($ x, y, z $). This is true if all the elements are in the same sequence. Therefore, you only need to output 1 for the given number of elements (although other numbers are fine).
A.py
for _ in range(int(input())):
print(" ".join(map(str,[1]*int(input()))))
Problem B
I think I saw a similar problem with AtCoder, but I don't remember.
I thought about maximizing ** $ GCD (a, b) $ to minimize $ LCM (a, b) $. Also, since $ GCD (a, b) $ is a divisor of $ n $, select the largest divisor of $ N $ ($ X $) excluding $ n $ (✳︎1).
At this time, $ N = X \ times K $ ($ K $ is an integer of 2 or more). Also, if $ a = X \ times Y $ ($ Y $ is a positive integer less than $ K $), then $ b = X \ times (K-Y) $. Here, $ Y $ and $ K-Y $ are relatively prime from the condition of $ X $, so $ LCM (a, b) = X \ times Y \ times (K-Y) $. And since $ X $ and $ K $ have already been determined, $ Y $ is positive and $ LCM (a, b) $ is monotonically decreasing ** with respect to ** $ Y $, so $ Y = K-1 $ Is the minimum. Therefore, when $ a = X \ times (K-1), b = X $, $ LCM (a, b) $ outputs this at the minimum (✳︎2).
Also, (✳︎1) was not shown during the contest because of my guess, but it can be shown in reverse from (✳︎2).
B.py
for _ in range(int(input())):
n,m=map(int,input().split())
a=[input() for i in range(n)]
ans=0
for i in range(m-1):
ans+=(a[n-1][i]=="D")
for i in range(n-1):
ans+=(a[i][m-1]=="R")
print(ans)
C problem
I was fooled by the fact that the question text said that it was less than $ 10 ^ {18} $ times. In reality, there are only two times at the maximum.
First of all, I greedily changed the position of the number, so I experimented with sample 2. Then, it becomes as follows.
In other words, from the above experiment, it can be said that ** there is no need to change the one that already corresponds to the position at the edge **, and ** if there is one that matches the position ** excluding the edge ** (sample As you can see) it looks like it will need to be replaced twice. Also, it is obvious that you cannot exchange it once, but you can also feel that you can exchange it twice. That is, the sequence $ a \ _1, a \ _2,…, a \ _n $ before the exchange is exchanged for the sequence $ b \ _1, a \ _2,…, a \ _n $, and finally the exchange is performed. It would be nice to show that it can be exchanged for $ 1,2,…, n $. At this time, $ b \ _i \ neq a \ _i $ and $ b \ _i \ neq i $ must hold for any $ i $. During the contest, I came to the conclusion that such $ b \ _i $ could be made by successfully exchanging sequences.
Also, the above proof seems to be possible, but it is not troublesome. ** I think I can show it because it is only necessary to have a perfect permutation relationship ** with each other. ** It is intuitive that if you can show a small pattern of $ n $, it will be possible with a larger $ n $ **.
Furthermore, if there is no one that matches the position except for the end, it is possible to replace it once, and if all the positions correspond from the beginning, it is not necessary to replace it, so it is possible to replace it 0 times. ..
C.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a==[i+1 for i in range(n)]:
print(0)
continue
#Excluding the edges
for i in range(n):
if a[i]!=i+1:
break
for j in range(n-1,-1,-1):
if a[j]!=j+1:
break
#Index error
for k in range(i,j+1):
if a[k]==k+1:
print(2)
break
else:
print(1)
D problem
It was difficult to debug and the remaining time was short because I used a greedy method with a heavy implementation that was properly considered. ** Do not do greedy algorithms that cannot be shown to be valid **.
First, two numbers disappear each time, and one number disappears as a sum, so ** $ [\ frac {n} {2}] $ numbers disappear **. Therefore, consider making the sum of these numbers as small as possible. That said, the $ [\ frac {n} {2}] $ numbers ** don't seem to be arbitrary **, so I'll experiment. Then, it will be as shown in the figure below.
From the above figure, you can see that when erasing $ [\ frac {n} {2}] $ numbers, ** the numbers next to each other cannot be erased **. Also, ** arrange the numbers so that they are not next to each other ** and $ a \ _1, a \ _3,…, a \ _ {n-2}, a \ _n, a \ _2, a \ _4,…, It becomes a \ _ {n-3}, a \ _ {n-1} $. If you select these consecutive $ [\ frac {n} {2}] $ numbers, any number will not be consecutive, and otherwise you may erase the numbers next to each other. You can find the maximum value of consecutive $ [\ frac {n} {2}] $ numbers ($ n $ streets) in a sequence while counting the difference.
D.py
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[[int(j) for j in input()[:-1]] for i in range(n)]
if n>=4 and m>=4:
print(-1)
exit()
if n==1 or m==1:
print(0)
exit()
inf=10000000000000
if n==2 or m==2:
bitcheck=[[0]*4 for i in range(4)]
for j in range(4):
for k in range(4):
for i in range(1):
if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
bitcheck[j][k]=False
break
else:
bitcheck[j][k]=True
bitcalc=[[0]*4 for i in range(4)]
for j in range(4):
for k in range(4):
for i in range(2):
if ((j>>i)&1)^((k>>i)&1):
bitcalc[j][k]+=1
if n==2:
n,m=m,n
b=[list(x) for x in zip(*a)]
else:
b=[i for i in a]
dp=[[inf]*4 for i in range(n)]
for i in range(n):
if i!=0:
for j in range(4):
for k in range(4):
if bitcheck[j][k]:
dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2][k])
else:
for k in range(4):
dp[i][k]=bitcalc[b[i][0]+b[i][1]*2][k]
print(min(dp[n-1]))
exit()
if n==3 or m==3:
bitcheck=[[0]*8 for i in range(8)]
for j in range(8):
for k in range(8):
for i in range(2):
if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
bitcheck[j][k]=False
break
else:
bitcheck[j][k]=True
bitcalc=[[0]*8 for i in range(8)]
for j in range(8):
for k in range(8):
for i in range(3):
if ((j>>i)&1)^((k>>i)&1):
bitcalc[j][k]+=1
if n==3:
n,m=m,n
b=[list(x) for x in zip(*a)]
else:
b=[i for i in a]
dp=[[inf]*8 for i in range(n)]
for i in range(n):
if i!=0:
for j in range(8):
for k in range(8):
if bitcheck[j][k]:
dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k])
else:
for k in range(8):
dp[i][k]=bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k]
print(min(dp[n-1]))
exit()
After the E problem
I will skip this time
Recommended Posts