[PYTHON] AtCoder Beginner Contest 177 Review
This time's results
Impressions of this time
I was able to pass through the D problem smoothly, but even though E was easy, I lost my concentration until the D problem. It is a reflection. The F problem is a type of problem that I can think of, but I'm addicted to the lie solution method.
Problem A
Consider whether to satisfy $ t \ times s \ geqq d $.
A.py
n,x,t=map(int,input().split())
y=-((-n)//x)
print(y*t)
B problem
$ len (s) \ times len (t) $ is about $ 10 ^ 6 $, so subsequence candidates for $ s $ that match $ t $ ($ len (s)-len (t) + 1 $ streets) All you have to do is search for.
B.py
s,t=input(),input()
ls=len(s)
lt=len(t)
ans=1000000000000
for i in range(ls-lt+1):
ans_sub=0
for j in range(lt):
if t[j]!=s[i+j]:
ans_sub+=1
ans=min(ans,ans_sub)
print(ans)
C problem
$ \ frac {(A \ _1 + A \ _2 +… + A \ _N) ^ 2- (A \ _1 ^ 2 + A \ _2 ^ 2 +… + A \ _N ^ 2)} {2} $ is the solution I will. I wanted to find all the multiplications of the two numbers, so this was the policy.
Normally, it seems to be a cumulative sum policy, but I don't think it's such a difficult idea.
C.py
n=int(input())
a=list(map(int,input().split()))
x=sum(a)
y=sum([(a[i])**2 for i in range(n)])
print(((x**2-y)//2)%(10**9+7))
D problem
I suspect ** Union Find ** first because it will be ** connected ** by friendship. In other words, friends are those that are included in the set united by a given friendship.
Now divide the $ N $ people into as few groups as possible so that you don't have any friends in the group. The number of groups may be greater than or equal to the maximum number of elements in each set of the disjoint set system, and this is output.
Also, using the library of this article, you can find the maximum value of the array size.
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
//Below, the disjoint sets and the tree represent the same thing.
class UnionFind {
public:
vector<ll> parent; //parent[i]Is the parent of i
vector<ll> siz; //An array representing the size of the disjoint sets(Initialize with 1)
map<ll,vector<ll>> group;//Associative array managed for each disjoint set(key is the parent of each disjoint set, value is an array of elements of that disjoint set)
//constructor
UnionFind(ll n):parent(n),siz(n,1){
//Initialize as the root of all elements is itself
for(ll i=0;i<n;i++){parent[i]=i;}
}
//Get the root of the tree to which the data x belongs(Also performs path compression)
ll root(ll x){
if(parent[x]==x) return x;
return parent[x]=root(parent[x]);//Since the value of the assignment expression is the value of the assigned variable, the route can be compressed.
}
//Merge x and y trees
void unite(ll x,ll y){
ll rx=root(x);//root of x
ll ry=root(y);//root of y
if(rx==ry) return;//When in the same tree
//Merge small set into large set(Merged from ry to rx)
if(siz[rx]<siz[ry]) swap(rx,ry);
siz[rx]+=siz[ry];
parent[ry]=rx;//If x and y are not in the same tree, add y root ry to x root rx
}
//Determine if the tree to which x and y belong is the same
bool same(ll x,ll y){
ll rx=root(x);
ll ry=root(y);
return rx==ry;
}
//Get the size of the disjoint sets of x
ll size(ll x){
return siz[root(x)];
}
//Group each disjoint set
void grouping(ll n){
//Perform route compression first
REP(i,n)root(i);
//Manage with map(Use default build)
REP(i,n)group[parent[i]].PB(i);
}
};
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n,m;cin>>n>>m;
UnionFind uf(n);
REP(i,m){
ll a,b;cin>>a>>b;
uf.unite(a-1,b-1);
}
uf.grouping(n);
ll ans=0;
FORA(i,uf.group){
ans=max(ans,SIZE(i.S));
}
cout<<ans<<endl;
}
E problem
Despite its appearance, it wasn't difficult. I want to get rid of the habit of being scared just by looking.
First, we need to handle two conditions here. The first is that $ GCD (A \ _ i, A \ _ j) = 1 $ holds for any $ 1 \ leqq i <j \ leqq N $. The second is that $ GCD (A \ 1, A \ 2,…, A \ N) = 1 $ holds. The second condition is good because it only does $ O (N \ log {A {max}}) $, but the first condition is $ O (N ^ 2 \ log {A {A { max}}) $.
Therefore, consider rephrasing the first condition further. First of all, ** arbitrary ** was awkward to handle, so considering denial, there is at least one pair of $ i, j $ that becomes $ GCD (A \ _i, A \ _j) \ neq 1 $. I decided to consider ** if it exists. At this time, when it becomes $ GCD (A \ _i, A \ _j) \ neq 1 $, it is enough to show that (not 1) ** there is a common divisor **. Therefore, I decided to enumerate the divisors of each $ A \ _i $ and check if the same divisors exist. However, this method is difficult because the amount of calculation is $ O (N \ sqrt {A \ _ {max}}) $ (it seems that this method also works in C ++).
At this point, I realized that it is not necessary to list all the divisors, but only the prime numbers included in the prime factorization **. In other words, if $ 12 = 2 \ times 2 \ times 3 $, then $ 2,3 $ will be enumerated (checked). At this time, the eratosthenes sieve can perform prime factorization at $ O (\ log {A_ {i}}) $, and the total complexity is $ O (N \ log {A_ {i}}) $. I will.
From the above, implement in the following order.
(1) Array PN_chk used in prime factorization, array check to check how many divisors appear, dictionary (or set) to check the numbers appearing in each $ A \ _i $ prime factorization Prepare prime.
(2) Initialize PN_chk using the Eratosthenes sieve. This allows prime factorization with $ O (\ log {A_ {i}}) $.
③ Perform prime factorization for each $ A \ _i $ and store it in prime. The stored prime numbers are recorded in check.
④ Check if there are 2 or more of each prime number recorded in check. If even one exists, it will be setwise coprime when the total gcd is 1, and not coprime when it is not. Also, if none exist, it will be pairwise coprime.
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 1000000 //10^6: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
#define PN 1 //The prime number mark is 1
//MAXR(=10^6)Suppose the integers up to are prime numbers
vector<ll> PN_chk(MAXR+1,PN);//0index corresponds to the i-th integer i(0~MAXR)
//O(MAXR)
void se(){
ll MAXRR=sqrt(MAXR)+1;
//It does prime factorization of 2 or more numbers and can be ignored.
PN_chk[0]=0;PN_chk[1]=0;
FOR(i,2,MAXRR){
//A prime number if it is assumed to be a prime number when you arrive
//Mark a multiple of a prime number because it is divisible by that prime number
if(PN_chk[i]==1) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=i;}
}
}
vector<ll> check(MAXR+1,0);
//O(logn)
//Note that prime is not aligned in this case! !! !!
//One-time check
map<ll,ll> prime;
void prime_factorize(ll n){
if(n<=1) return;
//If 1, n is a prime number
if(PN_chk[n]==1){prime[n]+=1;return;}
//Marked numbers are prime numbers
prime[PN_chk[n]]+=1;
//Consider the number of marked numbers divided by n
prime_factorize(ll(n/PN_chk[n]));
}
signed main(){
se();
//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];
//check twice
REP(i,n){
prime_factorize(a[i]);
FORA(j,prime){
check[j.F]++;
}
prime.clear();
}
ll g=gcd(a[0],a[1]);
FOR(i,2,n-1){
g=gcd(g,a[i]);
}
REP(i,MAXR+1){
if(check[i]>=2){
if(g==1){
cout<<"setwise coprime"<<endl;
}else{
cout<<"not coprime"<<endl;
}
return 0;
}
}
cout<<"pairwise coprime"<<endl;
}
F problem
I couldn't pass it at all during the contest, but it seemed to be a better policy than I expected because there was a shipment ** that I could narrow down the candidates to go.
The following is a policy in line with the explanation (I will summarize it while thinking about how to think about it).
First, consider whether to move down or to the right, but when moving to the $ k + 1 $ line, the number of times to move down is always $ k $. Therefore, the minimum number of moves should be ** only the minimum number of moves to the right ** (** separation & simplification of operations **).
Also, when moving from a certain starting point, the number of times to move to the right is minimized, so when you can go down, you should go down (** greedy movement **). Therefore, it can be said that ** once the start point is determined, the end point is uniquely determined **. Also, you have to go to the right only when the current point is included in $ A \ _i $ to $ B \ _i $.
Therefore, while managing the candidates (end point, start point), we will investigate in order from the top line. Also, from the above consideration, the end point is moved to $ B \ _ {i} + 1 $ only when the end point is included in $ B \ _i $ from $ A \ _i $, but if it is not included, the end point is moved. There is no need to move. Furthermore, if there are multiple start points when moving the end point (because we want to find the case where the number of moves is the minimum), ** only the maximum start point should be left **. Also, if $ B \ _ {i} + 1 $ becomes $ W $, it is not necessary to update the (end point, start point) candidates.
Furthermore, to find the case where the end point is included in $ A \ _i $ to $ B \ _i $, store the set of (end point, start point) in set and use lower_bound and ʻupper_bound`. It's fine. Also, if it is included, the number of elements is reduced, but ** the total number of reductions does not exceed $ W $ **, so the total amount of calculation is $ O ((H + W) \ log {(H +). W)}) $.
Also, in order to ** find the minimum number of movements in each line at high speed **, save the end point-start point value with ** multiset **, and do the same as the previous set. Delete or add.
Therefore, the implementation is summarized as follows.
(1) Prepare to from set that manages (end point, start point) and cost of multiset that saves the number of movements (end point-start point).
② Initialize to from and cost.
③ Perform operations on each line
(1) If $ [A \ _i, B \ _i] $ has an end point, move the end point to $ B \ _i + 1 $ and change both to from and cost. Also, it may not be necessary to move it, so be careful about the implementation at that time. Then, when $ B \ _ {i} + 1 $ becomes $ W $, insert only into cost without inserting to from.
(2) Look at the cost after the move operation in (1), and if the smallest element is not INF, output that element, and if it is INF, output -1.
Also, ** the problem that you only have to manage a part with set or multiset by paying attention to the selection order ** and ** the problem that manages information with multiple data structures ** are difficult. I often see it in, so I will try to keep it as an idea.
✳️ I had a lot of trouble with the implementation, so I will summarize some points below.
① ** Integer pairs can be speeded up ** by converting them to integers. (2) If you want to find the interval with lower_bound and upper_bound, it will cause a bug, so it is better to follow from ** lower_bound and check if the upper end condition is satisfied **. ③ ** If you use erase with set or multiset, the next iterator will be returned **, so it is very easy to implement if you use a while statement when implementing ③.
F.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 1000000 //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 h,w;cin>>h>>w;
//end point,Manage the starting point
set<ll> tofrom;
//Manage the minimum
multiset<ll> cost;
REP(i,w){
tofrom.insert(i*MOD+i);
cost.insert(0);
}
REP(i,h){
ll a,b;cin>>a>>b;a--;b--;
auto j=tofrom.lower_bound(a*MOD);
if(j!=tofrom.end()){
ll ne=-1;
while(j!=tofrom.end() or *j<(b+2)*MOD){
cost.erase(cost.lower_bound(ll(*j/MOD)-*j%MOD));
ne=*j%MOD;
j=tofrom.erase(j);
}
if(b==w-1){
cost.insert(INF);
}else{
cost.insert(b+1-ne);
tofrom.insert((b+1)*MOD+ne);
}
}
if(*cost.begin()!=INF)cout<<*cost.begin()+i+1<<"\n";
else cout<<-1<<"\n";
}
}
Recommended Posts