Codeforces Round # 662 (Div. 2) Bacha Review (8/8)
This time's results
Impressions of this time
I was impatient with problem A and made a mistake in the experiment and took time. ** If the experiment is wrong ** I haven't been able to take care of it so far, so I'd like to be careful. I've used it for about an hour for A, but such a ** ingenuity that doesn't fit in the swamp ** (** away from the problem **, ** may be fundamentally wrong in consideration or wrong implementation I would like to consider **, etc.). I think that such patterns can be collected in the past Bachacon and contests, so I would like to do it when I can make a ** summary of all the mistakes I have made so far **.
(Also, the review has been delayed. I'd like to be careful, but when other tasks overlap ...)
Problem A
First, consider experimenting with puzzle-like problems like this. However, I ** made a mistake in the puzzle experiment **. As long as it's embarrassing.
If you perform the experiment accurately, it will be as shown in the figure below.
If we can do this experiment correctly, we know that $ [\ frac {n} {2}] $ is likely to be the answer, but we should pay attention to the recursive structure. In other words, the outer frame should be considered separately, and it becomes as follows.
A.py
def f(x):return x//2+1
for i in range(int(input())):
n=int(input())
print(f(n))
Problem B
I feel that a backward compatibility issue has emerged in ABC.
The problem is to combine the boards you have to make one square and one rectangle. However, the boards cannot be connected or cut.
Here, a square can be made by using ** 4 boards of the same length **, and a rectangle can be made by using ** 2 sets of 2 boards of the same length **. Therefore, it is sufficient to record four or more boards and two or more boards, respectively, and to have one or more boards with four or more boards and two or more boards with two or more boards. However, if there are ** 8 or more boards of the same length **, you can make one square and one rectangle with only those boards, and if there are ** 6 or more boards of the same length **, You can make two sides, a square and a rectangle, so you need to consider these cases as well.
Therefore, from the above, 2 or more boards, 4 or more boards, 6 or more boards, and 8 or more boards are saved as sets (d2, d4, d6, d8. By doing so, you can judge whether you can make one square and one rectangle. Also, at this time, I think that it would be easier to implement ** if the array had set as an element **, so I would like to try to be careful so far **.
B.py
n=int(input())
a=list(map(int,input().split()))
q=int(input())
d=dict()
for i in range(n):
if a[i] in d:
d[a[i]]+=1
else:
d[a[i]]=1
d2,d4,d6,d8=set(),set(),set(),set()
for i in d:
if d[i]>=8:
d8.add(i)
elif d[i]>=6:
d6.add(i)
elif d[i]>=4:
d4.add(i)
elif d[i]>=2:
d2.add(i)
for i in range(q):
s,x=input().split()
x=int(x)
if s=="+":
if x in d:
d[x]+=1
if d[x]==2:
d2.add(x)
elif d[x]==4:
d2.remove(x)
d4.add(x)
elif d[x]==6:
d4.remove(x)
d6.add(x)
elif d[x]==8:
d6.remove(x)
d8.add(x)
else:
d[x]=1
else:
d[x]-=1
if d[x]==1:
d2.remove(x)
elif d[x]==3:
d4.remove(x)
d2.add(x)
elif d[x]==5:
d6.remove(x)
d4.add(x)
elif d[x]==7:
d8.remove(x)
d6.add(x)
if len(d8)>0:
print("YES")
elif len(d6)>=2:
print("YES")
elif len(d6)==1 and len(d4)+len(d2)>0:
print("YES")
elif len(d4)>=2:
print("YES")
elif len(d4)==1 and len(d2)>=2:
print("YES")
else:
print("NO")
C problem
(Experiments and illustrations were quite alive in this problem.)
When eating cakes in order, consider leaving as much time as possible to eat the same cake.
Here, ** a large number of cakes have a narrow time interval **, so it is this large number of cakes that ** regulates the maximum distance you want to find **. Therefore, I thought that it would be better to decide the position in order from the cake with the largest number. Based on this assumption, I considered the first sample below.
7
1 7 1 6 4 4 6
In the above sample, the three numbers 1,4,6 are twice each, and 7 is only once, so consider deciding the location of 1,4,6. At this time, the maximum distance of 3 can be achieved by arranging as shown in the figure below.
The points here are "to place 1-4-6 as ** lumps ** without moving the order" and "to place each lump at both ends". This allows each number to be placed as far apart as possible. I also tried to see if the same thing holds for the second sample below.
8
1 1 4 6 4 6 4 7
In this sample, the largest number of cakes appears in 3 of 4 cakes. At this time, the maximum distance of 2 can be achieved by arranging as shown in the figure below.
Here, 4 is ** placed at both ends and between them as evenly as possible **. Also, by adjusting the order of the remaining cakes (1 → 6 in the above figure), the maximum distance will not be affected. Therefore, ** only the cake with the largest number of cakes should be considered **, and the type of cake with the largest number of cakes is $ m $, and the number of cakes is $ k $, as shown in the figure below.
So what we want to find is the distance in this problem, so (mass length-1) = $ [\ frac {n-m} {k-1}]-1 $ is the answer.
C.py
from collections import Counter
for _ in range(int(input())):
n=int(input())
s=list(map(int,input().split()))
d=Counter(s)
d=list(d.items())
d.sort(reverse=True,key=lambda x:x[1])
l=len(d)
now=[1,d[0][1]]
for i in range(1,l):
if now[1]==d[i][1]:
now[0]+=1
else:
break
k=now[1]
m=now[0]
print((n-m)//(k-1)-1)
D problem
I couldn't pass it during the contest, but I'm glad I was able to solve it soon after. ** I'm rushing in the front and I can't spend time on the problems in the back.
First, I wrote the same figure ** as the question sentence. In the figure above, you can see that four dress patterns have been generated that fit the theme, with the center being a red grid. In addition, the number of dress patterns centered on a certain grid can be counted in four directions in order, and can be searched in the form of BFS.
Also, since dresses contain only the same alphabet (lowercase letters), it is possible to search for the number of dress patterns centered on each grid for each alphabet in about $ O ((n \ times m) ^ 2) $. is. However, if nothing is done, the search will not be completed within the time limit, and the search area will obviously be covered when counting, so reduce the amount of calculation to about ** $ O (n \ times m) $ **. Think about. Furthermore, I wanted to make it possible to ** search for each alphabet at once ** for about $ O (n \ times m) $.
In the above, when searching, it is considered that the number of dress patterns centered on each grid is ** recorded on the grid **, so if the recording in the following example is performed by hand, the recording for a will be It will be as follows.
6 6
zbaagd
baaacd
aaaaae
eaaadc
cdafed
aecdae
| 0 | 0 | 1 | 1 | 0 | 0 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 1 | 0 | 0 |
| 1 | 2 | 3 | 2 | 1 | 0 |
| 0 | 1 | 2 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
First, all a's are ** 1 or more **. Furthermore, if there is a 0 in any of the four directions ** (or there is an a at the very end), it can be determined as 1. Also, it seems difficult to decide 2 or 3 immediately, but I realized that it seems that I can decide in the order of ** 1 → 2 → 3 →… **.
In other words, if all four directions are ** 1, then 2 and if all four directions are 2, then 3 ... In other words, after deciding the starting point to become 1, you can search with the amount of calculation of $ O (N \ times M) $ using BFS.
Also, since time constraints are quite strict, it is necessary to devise ways such as (1) using C ++, (2) reusing ** vector **, and (3) passing the grid information in ** pair to the deque used in BFS.
D.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
//pair instead of vector
//Do not generate vector every time
signed main(){
//Code for speeding up input
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll ans=0;
ll n,m;cin>>n>>m;
vector<string> x(n);REP(i,n)cin>>x[i];
vector<char> alph(26);alph[0]='a';
for(ll i=1;i<26;i++){
alph[i]=alph[i-1];
alph[i]++;
}
vector<vector<ll>> y(n,vector<ll>(m,0));
vector<vector<bool>> check(n,vector<bool>(m,true));
FORA(i,alph){
REP(j,n)REP(k,m)y[j][k]=(x[j][k]==i);
REP(j,n)REP(k,m)check[j][k]=(x[j][k]!=i);
ll d=2;
deque<pair<ll,ll>> b;
REP(j,n){
REP(k,m){
if(j==0 or j==n-1 or k==0 or k==m-1){
if(y[j][k]){
check[j][k]=true;
b.PB(MP(j,k));
}
}else if(!(y[j-1][k] and y[j+1][k] and y[j][k-1] and y[j][k+1])){
if(y[j][k]){
check[j][k]=true;
b.PB(MP(j,k));
}
}
}
}
while(SIZE(b)){
ll l=SIZE(b);
REP(_,l){
pair<ll,ll> c=*(b.begin());b.pop_front();
if(c.F>0){
if(! check[c.F-1][c.S]){
check[c.F-1][c.S]=true;
y[c.F-1][c.S]=d;
b.PB(MP(c.F-1,c.S));
}
}
if(c.F<n-1){
if(! check[c.F+1][c.S]){
check[c.F+1][c.S]=true;
y[c.F+1][c.S]=d;
b.PB(MP(c.F+1,c.S));
}
}
if(c.S>0){
if(! check[c.F][c.S-1]){
check[c.F][c.S-1]=true;
y[c.F][c.S-1]=d;
b.PB(MP(c.F,c.S-1));
}
}
if(c.S<m-1){
if(! check[c.F][c.S+1]){
check[c.F][c.S+1]=true;
y[c.F][c.S+1]=d;
b.PB(MP(c.F,c.S+1));
}
}
}
d+=1;
}
REP(j,n)REP(k,m)ans+=y[j][k];
}
cout<<ans<<endl;
}
After the E problem
I will skip this time
Recommended Posts