Codeforces Round # 648 (Div. 2) Bacha Review (9/5)
This time's results
Impressions of this time
This time, I made use of my usual reflections and ** worked calmly **, but I was able to achieve relatively good results. However, I have a habit of temporarily losing my concentration when I hit a problem that needs consideration **, so I want to be able to over-concentrate there.
Also, I feel that I was able to get a little more results, but since this is probably the first time for Gokan, I would like to use it as a source of motivation in the future.
(Except for this article, I have accumulated 3 reviews, so I want to digest it quickly.)
Problem A
You cannot select rows and columns that contain craiming cells. Here, the number of rows and columns that do not contain craiming cells from the first input can be calculated as mr, mc, respectively ($ O (m \ times n) $).
At this time, each person may ** select one cell from the rows and columns that are not included and select the cell at the intersection **, and the person who cannot select by alternating this operation loses. I will. Also, the number of operations is min (mr, mc), and the winner is determined by the oddness of the number of operations.
A.py
for _ in range(int(input())):
n,m=map(int,input().split())
r,c=[False]*n,[False]*m
for i in range(n):
x=list(map(int,input().split()))
if not all(k==0 for k in x):
r[i]=True
for j in range(m):
if x[j]==1:
c[j]=True
z=min(r.count(False),c.count(False))
print(["Vivek","Ashish"][z%2])
Problem B
Note that it is a swap ** between different types, not just the same type.
Here, when the $ i $ th number should be the $ j $ th after sorting, if $ i $ and $ j $ are different types, it is realized by doing a swap between $ i $ and $ j $. Is possible. On the other hand, if $ i $ and $ j $ are the same type, ** via swap between different $ k $ th numbers of different types ** (swap at $ j $ and $ k $ → $ This can be achieved by doing swap in the order of i $ and $ k $). Therefore, ** if there is at least one of each type ** it is possible to sort according to the subject. Also, even if there is only one type in the sequence, it is possible to sort if the sequence is ** sorted **. Therefore, these cases are described as follows.
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
c=sorted(a)
b=list(map(int,input().split()))
if a==c:
print("Yes")
continue
if b.count(1)==n or b.count(0)==n:
print("No")
else:
print("Yes")
C problem
Obviously, you only need to shift the cycle ** at most once **. It is also clear that a full search of $ n $ streets of cycle shifts will result in $ O (N ^ 2) $ ** and will not be in time. Therefore, instead of focusing on shifts, we focused on ** how many shifts each element requires **. Also, the total number of elements that can be shifted and matched is limited to ** $ n $ with $ n $ shifts, so I came up with the idea that I should pay attention to the elements.
Once you have an idea of paying attention to the elements, the rest is not difficult. You can easily find out how much to shift each element from the array $ a $ and the array $ b $. Also, at this time, (index at $ b $)-(index at $ a $) may be ** negative **, so in that case, add $ n $. From the above, since the required shifts for each element could be saved, the number of elements was saved for each shift using the Counter class, and the maximum value of the number of elements was calculated.
C.py
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
#Position of each element
ind=[0 for i in range(n)]
for i in range(n):
ind[a[i]-1]+=i
for i in range(n):
ind[b[i]-1]-=i
for i in range(n):
if ind[i]<0:
ind[i]+=n
from collections import Counter
c=Counter(ind)
ans=1
for i in c:
ans=max(ans,c[i])
print(ans)
D problem
** I made a mistake in the variable name ** or set it to -1 where I added +1 and I was impatient without passing through the sample. The policy was quickly set to perfection, so I would like to work hard to ensure a stable implementation. Also, ** I used padding when tracing with BFS ** I was able to write the judgment part neatly (compared to our company), so I would like to use it from now on.
Since it is a move to the part that shares the edge, consider implementing it in BFS or DFS. Also, G escapes and B does not escape, but ** B is more restrictive **, so consider satisfying this condition first. When B escapes, the pattern is either to reach where G is or to reach $ (n, m) $ directly. Therefore, in case of either, ** it is necessary to put a wall in the middle **. You can also see that the smaller the area where the wall is placed, the higher the probability of reaching $ (n, m) $ in ** G. In other words, when there is B, you can ** put walls on all sides **. Also, if $ G $ is included on all sides and the wall cannot be placed, the subject cannot be satisfied at that point, and in other cases, the wall can be surrounded on all sides. Therefore, for the condition that B cannot escape, ** placing walls on all four sides is necessary and sufficient **.
Based on this, we will consider ** G escape conditions **, but the condition that each G can reach $ (n, m) $ by BFS or DFS (here, use the BFS you like). It's not difficult to paraphrase. However, if you do BFS on each G, you need to search up to $ (50 \ times 50) ^ 2 $ times and there are up to 100 test cases, so it is obviously not in time. Here, taking advantage of the fact that the final destination is the same as $ (n, m) $, ** conversely, can we reach each $ G $ from $ (n, m) $ **? think. At this time, ** one BFS is required **, so the search is $ 50 \ times 50 $ times and can be implemented in a relatively slow language such as Python.
When implementing, you can do it in two steps: (1) fill the area around B → (2) perform BFS. However, please note that there are the following cases.
(1) When there is $ G $ on all sides in ① → Output No (2) When $ (n, m) $ is a wall or $ B $ and there is no ** $ G $ ** → Yes is output. (3) When $ (n, m) $ is a wall or $ B $ and $ G $ exists → Output No (4) When there is $ G $ that cannot be searched in the case of ② → No is output (5) When $ G $ that cannot be searched does not exist in ② → Output Yes
D.py
from collections import deque
def bfs():
global n,m,s,d,check
#print(d)
while len(d):
l=len(d)
for i in range(l):
p=d.popleft()
for j in [[p[0],p[1]+1],[p[0],p[1]-1],[p[0]+1,p[1]],[p[0]-1,p[1]]]:
#print([[p[0],p[1]+1],[p[0],p[1]-1],[p[0]+1,p[1]],[p[0]-1,p[1]]])
#print(check[j[0]][j[1]])
if not check[j[0]][j[1]]:
check[j[0]][j[1]]=True
d.append(j)
#print(d)
for _ in range(int(input())):
n,m=map(int,input().split())
s=[["#" for i in range(m+2)]]+[list("#"+input()+"#") for i in range(n)]+[["#" for i in range(m+2)]]
f=False
#Fill around B
for i in range(1,n+1):
for j in range(1,m+1):
if s[i][j]=="B":
for k in [[i,j+1],[i,j-1],[i-1,j],[i+1,j]]:
if s[k[0]][k[1]]=="G":
f=True
elif s[k[0]][k[1]]==".":
s[k[0]][k[1]]="#"
#print(s)
if f:
print("No")
continue
#Search with bfs
if s[n][m]=="B" or s[n][m]=="#":
for i in range(1,n+1):
for j in range(1,m+1):
if s[i][j]=="G":
f=True
if not f:
print("Yes")
else:
print("No")
continue
d=deque()
d.append([n,m])
check=[[(s[i][j]=="B") or (s[i][j]=="#") for j in range(m+2)] for i in range(n+2)]
check[n][m]=True
#print(check)
bfs()
for i in range(1,n+1):
for j in range(1,m+1):
if s[i][j]=="G" and check[i][j]==False:
f=True
#if f:
#print(s)
#print(check)
#print(3)
if f:
print("No")
continue
print("Yes")
E problem
The implementation didn't have to be C ++, but I had to go through a total of about $ 10 ^ 7 $ loops, so I chose C ++.
First of all, the problem statement was difficult to read, but in summary, the problem is as follows (although my summary is also difficult to read ...).
"When $ k $ numbers are selected from the sequence $ a $ of length $ n $, $ max (1, k-2) $ or more stands in the selected numbers for each bit. Finds how to choose the number that maximizes the answer, including that bit in the answer. "
First, ** each bit moves independently **, so it seems difficult to greedily choose such a number **. So, for the time being, I set a bit appropriately with $ k = 1,2 $ and thought about it. Then, I noticed that $ k = 1,2,3 $ should be selected so that ** as many bits as possible are set ** ($ \ because max (1, k-2) = 1 $). However, when $ k = 4 $, $ max (1, k-2) = 2 $, and even if one number is added, the number of each bit is increased by at most one, so $ k = There is no new bit included in the answer by increasing from 3 $ to $ k = 4 $. The same thing can be said for $ k \ geqq 5 $, so ** $ k $ should be considered up to 3 **.
From the above, you can think about how to select 3 ways, but at most $ _ {500} C_3 = 2.07085 \ times 10 ^ 7 $ ways, and you can ** search all **. Also, since it is only necessary that one number of bits is set when three numbers are selected, it is only necessary to calculate with bitwise or to find the maximum value. However, when $ n = 1,2 $, the solution is the bitwise or of all elements.
E.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
ll ans=0;
REP(i,n){
FOR(j,i+1,n-1){
FOR(k,j+1,n-1){
ans=max(ans,a[i]|a[j]|a[k]);
}
}
}
if(n==1)cout<<a[0]<<endl;
else if(n==2)cout<<(a[0]|a[1])<<endl;
else cout<<ans<<endl;
}
After the F problem
I will skip this time
Recommended Posts