Codeforces Round # 639 (Div. 2) Bacha Review (9/4)
This time's results
Impressions of this time
Problem A
First, if the smaller of $ n $ and $ m $ is 1, you can create it by connecting the concave and convex parts in order. In other cases, it holds only when $ n = m = 2 $. (I thought about it properly and did 1WA.)
I thought about this experimentally, but if I consider it accurately, it will be as follows. ** Since there are few concave parts, I want to use it at the boundary as much as possible **. Therefore, it can be made if the number of boundaries is less than the number of concave parts. Here, the boundary part is only $ n \ times (m-1) + (n-1) \ times m $, but the number of puzzles (the number of concave parts) is $ n \ times m $. Therefore, $ n \ times (m-1) + (n-1) \ times m \ leqq n \ times m $ must hold. At this time, it is $ (n -1) (m-1) \ leqq 1
A.py
for _ in range(int(input())):
x=list(map(int,input().split()))
if min(x)==1 or max(x)==2:
print("YES")
else:
print("NO")
Problem B
First, when I thought about how many cards I needed for each pyramid, I found that as the height increased, it increased in the order of $ 2 \ rightarrow 7 \ rightarrow 15 \ rightarrow 26 \ rightarrow
Also, since you will be asked repeatedly in the query, ** ask for the number of cards required to make each pyramid first **, but since the number of cards is at most $ 10 ^ 9 $, you need more than that. You don't have to think about pyramids. Also, experiments have shown that the height of a pyramid that can be made with ** $ 10 ^ 9 $ is at most $ 25820 $ **, so it is necessary to make a pyramid with a height of $ 1 $ ~ $ 25820 $. List all the number of cards (check).
Then consider processing the query. Here, we need to make the tallest pyramid that can be made with the given $ n $ cards, so we can make one of the pyramids found by bisect_right from check, which is one of the lower pyramids. is. ** You can think about the surplus cards with a recursive function **, and output the total.
B.py
check=[2]
i=0
while check[-1]<=10**9:
check.append(check[-1]+3*i+5)
i+=1
print(len(check))
from bisect import bisect_right
def dfs(x):
if x<2:
return 0
return dfs(x-check[bisect_right(check,x)-1])+1
for _ in range(int(input())):
n=int(input())
print(dfs(n))
C problem
I found this problem interesting.
Consider if there is a match as a result of shuffling. First, the generalization of this shuffle is $ k \ rightarrow k + a_ {k \ mod \ n} $. Considering whether it will be duplicated in the shuffle at this time, it will not be duplicated when ** $ mod \ n $ are equal **. For example, $ k $ and $ k + n $ $ mod \ n $ are equal, but $ k + n \ rightarrow k + n + a_ {k \ mod \ n} $, so even if you shuffle It does not overlap.
Therefore, when shuffling, ** consider which $ mod \ n $ room number to move from each $ mod \ n $ room number **, and ** $ mod \ n $ may match. Just check ** to do it. Therefore, for $ i = 0 $ ~ $ n-1 $, find $ (i + a_ {i \ mod \ n}) \ mod \ n $ to find a match. Also, if you assign the obtained value to the set structure, you only have to judge whether the size of the set structure is $ n $.
C.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
s=set()
for i in range(n):
s.add((i+a[i%n])%n)
#print(s)
print("YES" if len(s)==n else "NO")
D problem
** I misunderstood the subject and made many mistakes **. It was regrettable. Immediately after the contest, the solution was to fill in the bugs little by little, but I think that ** I could solve it without bugs and the implementation was light if I could finish the consideration, so I regret it.
First, south can be ** placed at your convenience **. Here, ** each move is in the same row or column **, so let's focus on each row (or column). At this time, ** If there is no south in the left and right ends of the black part of a line, that line cannot be traced by north **. Also, when south is placed on the left and right edges, north can pass through between them, so ** it must be painted black from the left edge to the right edge **.
In addition to the above, rule 1 also requires that there be at least one south magnet in any row and column. At this time, it is sufficient if a black cell exists in any row and column, but ** If it does not exist but does not share a row or column with any other black cell, place south. I can**. Also, if you think of a ** cell as a row-column intersection **, you can paraphrase it as ** if there is at least one row and one column with no black cells **.
If the above judgment is correct in any row and column, the subject can be satisfied. At this time, the required number of ** north matches the number of connected components ** when the black square is viewed as the apex. The number of connected components is always counted by UnionFind, but since it is on the ** grid, the number is counted using BFS **. Then, just output that value.
The first code is after the contest and the second code is for review.
D_worse.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
deque<pair<ll,ll>> d;
vector<vector<bool>> bfs_chk;
ll n,m;
void bfs(){
while(SIZE(d)){
ll l=SIZE(d);
REP(i,l){
ll c0,c1;c0=d.front().F;c1=d.front().S;
//cout<<c0<<" "<<c1<<endl;
vector<pair<ll,ll>> nex={MP(c0-1,c1),MP(c0+1,c1),MP(c0,c1-1),MP(c0,c1+1)};
FORA(j,nex){
//cout<<1<<endl;
if(0<=j.F and j.F<n and 0<=j.S and j.S<m){
//cout<<j.F<<" "<<j.S<<endl;
if(!bfs_chk[j.F][j.S]){
bfs_chk[j.F][j.S]=true;
d.PB(j);
//cout<<1<<endl;
}
}
}
d.pop_front();
}
}
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
cin>>n>>m;
vector<string> s(n);REP(i,n)cin>>s[i];
bfs_chk=vector<vector<bool>>(n,vector<bool>(m,true));
REP(i,n)REP(j,m)bfs_chk[i][j]=(s[i][j]=='.');
ll ans=0;
//cout<<1<<endl;
REP(i,n){
REP(j,m){
if(bfs_chk[i][j]==false){
bfs_chk[i][j]=true;
d.PB(MP(i,j));
bfs();
ans++;
}
}
}
//cout<<1<<endl;
vector<bool> r(n,false);
vector<bool> c(m,false);
REP(i,n){
REP(j,m){
if(s[i][j]=='#'){
FOR(k,j,m-1){
if(s[i][k]=='.'){
FOR(l,k,m-1){
if(s[i][l]=='#'){
//cout<<2<<endl;
cout<<-1<<endl;
return 0;
}
}
break;
}else{
c[j]=true;
r[i]=true;
}
}
break;
}
}
}
REP(i,m){
REP(j,n){
if(s[j][i]=='#'){
FOR(k,j,n-1){
if(s[k][i]=='.'){
FOR(l,k,n-1){
if(s[l][i]=='#'){
//cout<<3<<endl;
cout<<-1<<endl;
return 0;
}
}
break;
}else{
r[j]=true;
c[i]=true;
}
}
break;
}
}
}
//If you can add
pair<vector<ll>,vector<ll>> addition;
REP(i,n){
ll co=0;
REP(j,m){
co+=ll(s[i][j]=='#');
}
if(co==0)addition.F.PB(i);
}
REP(j,m){
ll co=0;
REP(i,n){
co+=ll(s[i][j]=='#');
}
if(co==0)addition.S.PB(j);
}
FORA(i,addition.F){
FORA(j,addition.S){
r[i]=true;
c[j]=true;
}
}
//REP(i,n)cout<<r[i]<<endl;
//REP(i,m)cout<<c[i]<<endl;
if(all_of(ALL(r),[](boolx){returnx;})andall_of(ALL(c),[](boolx){returnx;})){
cout<<ans<<endl;
}else if(all_of(ALL(r),[](boolx){return!x;})andall_of(ALL(c),[](boolx){return!x;})){
cout<<ans<<endl;
}else{
//cout<<4<<endl;
cout<<-1<<endl;
}
}
D_better.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
deque<pair<ll,ll>> d;
vector<vector<bool>> bfs_chk;
ll n,m;
void bfs(){
while(SIZE(d)){
ll l=SIZE(d);
REP(i,l){
ll c0,c1;c0=d.front().F;c1=d.front().S;
//cout<<c0<<" "<<c1<<endl;
vector<pair<ll,ll>> nex={MP(c0-1,c1),MP(c0+1,c1),MP(c0,c1-1),MP(c0,c1+1)};
FORA(j,nex){
//cout<<1<<endl;
if(0<=j.F and j.F<n and 0<=j.S and j.S<m){
//cout<<j.F<<" "<<j.S<<endl;
if(!bfs_chk[j.F][j.S]){
bfs_chk[j.F][j.S]=true;
d.PB(j);
//cout<<1<<endl;
}
}
}
d.pop_front();
}
}
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
cin>>n>>m;
vector<string> s(n);REP(i,n)cin>>s[i];
//cout<<1<<endl;
ll f=0;ll g=0;
REP(i,n){
ll li=-1;ll ri=-1;
//Left end
REP(j,m){
if(s[i][j]=='#'){
li=j;
break;
}
}
//Right end
REPD(j,m){
if(s[i][j]=='#'){
ri=j;
break;
}
}
if(li==-1 and ri==-1){
f++;
continue;
}
FOR(j,li,ri){
if(s[i][j]!='#'){
cout<<-1<<endl;
return 0;
}
}
}
REP(j,m){
ll ui=-1;ll di=-1;
//Top edge
REP(i,n){
if(s[i][j]=='#'){
ui=i;
break;
}
}
//lower end
REPD(i,n){
if(s[i][j]=='#'){
di=i;
break;
}
}
if(ui==-1 and di==-1){
g++;
continue;
}
FOR(i,ui,di){
if(s[i][j]!='#'){
cout<<-1<<endl;
return 0;
}
}
}
//When you can't put south in a good way
if((f==0 and g!=0)or(f!=0 and g==0)){
cout<<-1<<endl;
return 0;
}
bfs_chk=vector<vector<bool>>(n,vector<bool>(m,true));
REP(i,n)REP(j,m)bfs_chk[i][j]=(s[i][j]=='.');
ll ans=0;
//cout<<1<<endl;
REP(i,n){
REP(j,m){
if(bfs_chk[i][j]==false){
bfs_chk[i][j]=true;
d.PB(MP(i,j));
bfs();
ans++;
}
}
}
cout<<ans<<endl;
}
After the E problem
I will skip this time
Recommended Posts