[PYTHON] AtCoder Beginner Contest 170 Review
This time's results
Impressions of this time
I made a big mistake after a long time. I didn't think that D wouldn't pass, but if you think calmly, you can't pass it with Python or PyPy in terms of calculation. I solved E in the second half, but it hurts to have a bug in the implementation ... The speed of implementation seems to have to be trained repeatedly to get used to it.
When I was playing code golf, I was late to publish an article. I will try to play code golf after finishing the review ...
Problem A
Since it is an integer sequence after substituting 0, the index of the element that becomes 0 can be calculated by 1-indexed.
A.py
x=list(map(int,input().split()))
print(x.index(0)+1)
B problem
Consider how many animals are cranes and turtles, respectively. There are 0 to x cranes and turtles, and if you decide how many of them are, the other will be decided, and if you know how many of them, the number of legs will be decided, so look for a combination that will be y.
B.py
x,y=map(int,input().split())
for i in range(x+1):
if 2*i+4*(x-i)==y:
print("Yes")
break
else:
print("No")
C problem
Recently, I feel that there are some problems to think about in C.
Integer to be calculated
C.py
x,n=map(int,input().split())
p=sorted(list(map(int,input().split())))
q=[0]*(102)
for i in range(n):
q[p[i]]=1
ans=(1000000,-1)
for i in range(102):
if q[i]==0:
if ans[0]>abs(i-x):
ans=(abs(i-x),i)
print(ans[1])
D problem
It was written in the Answer that it can be done in the same way as the Eratosthenes sieve, but I was forced to $ O (N \ sqrt { A_ {max}}) I passed it with $. In terms of the amount of calculation, Python and PyPy are not in time, so I changed to C ++. Also, I couldn't make this decision during the contest, so I felt that I should be ** calm. ** When $ A_i $ is divisible by $ A_j $, $ A_j $ is a divisor of $ A_i $ **. Also, as you can see from this article, you can enumerate divisors with $ O (\ log {A_i}) $. Therefore, if you enumerate the divisors for each $ A_i $ and the divisors included in the sequence $ A $, you can judge that the property of the problem statement is not satisfied.
As an additional note, when I was looking at maspy's commentary, I thought it was true that it was written that it was easier to find multiples than divisors in ordering relations. I want to use it from now on.
D.cc
//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//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.
#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--)
//x is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
vector<ll> make_divisors(ll n){
vector<ll> divisors;
//cout << 1 << endl;
FOR(i,1,ll(sqrt(n))){
if(n%i==0){
divisors.PB(i);
if(i!=ll(n/i))divisors.PB(ll(n/i));
}
}
return divisors;
}
signed main(){
ll n;cin >> n;
map<ll,ll> a;
REP(i,n){
ll x;cin >> x;
a[x]+=1;
}
ll ans=0;
for(auto i=a.begin();i!=a.end();i++){
vector<ll> div=make_divisors(i->F);
//cout << 1 << endl;
ll f=true;
REP(j,SIZE(div)){
if((a.find(div[j])!=a.end() and div[j]!=(i->F))or(div[j]==(i->F) and (i->S)>1)){
f=false;
break;
}
}
if(f)ans++;
}
cout << ans << endl;
}
E problem
The multiset I did just last week came out, but I couldn't solve it due to a bug in the implementation ...
First of all, ** you need to store the infant with the highest rate in each garden **, so prepare a container to store this (youjitati). Also, ** the highest rate infants in each kindergarten must also be stored in a container ** (youtien), but ** yojitati and youtien elements can change depending on the kindergarten **, so only the highest rate infants Instead, you need to keep both youjitati and yououtien as a sorted container **.
Here, ** C ++ set, multiset ** are available as ($ O (\ log {n}) $) containers ** that can be added or deleted at high speed while maintaining the sorted state (Python). There is also a heap queue, but it seems to me that it is difficult to use personally, contrary to my intuition.) Also, here I decided to use a multiset that stores the infant's rate and number as a pair to distinguish infants with the same rate, but since it can be distinguished by pairing, the result is the same for sets instead of multiset You can write a program like this.
So, if you sort out the above, youjitati saves the highest rate toddlers in each kindergarten in ascending order with the pair <infant rate, toddler number> with multiset <pair <ll, ll >>. Saves the rates of each kindergarten toddler in ascending order with vector <multiset <pair <ll, ll >>>.
Consider processing each query under this. Now consider transferring Toddler C from Kindergarten E to Kindergarten D, but ** Kindergarten E to which Toddler C belongs cannot be determined from the containers youjitati and youtien mentioned earlier **. Therefore, simply record ** which kindergarten each toddler is in ** in vector <ll> (doko). Based on this, let's think about query processing with diagrams.
First, consider the case where you have enough toddlers in youtuien. Here, it is easy to understand if it is divided into ** stages , and it can be divided into three stages. ( I couldn't organize the production so far . I think I have to gain confidence because I can solve it if I calm down.)
① erase from youjitati
First, you need to erase the maximum rate of kindergarten D and kindergarten E stored in youjitati, as the elements that should be stored in youjitati may change when moving toddler C. Here the maximum rate infants in kindergarten D and kindergarten E can be obtained in the iterator as --youtien [D] .end (), --youtien [E] .end (). ( It's refreshing to think that you should escape once **.)
② Movement of infant C
At the end of ①, move Toddler C from Kindergarten E to Kindergarten D. At this time, when searching for the element of infant C, you have to search by <infant rate, infant number>, ** the infant rate cannot be obtained as it is **, so each infant rate is vector. Record it in <ll> (tikara). This allows the operation of moving infant C to be easily expressed by erase from youtuien [E] and insert into youtuien [D].
③ insert into youjitati
I erased from youjitati at the stage of ① earlier, but this time it is necessary to insert again. This is not difficult. As in ①, you can get the maximum rate of kindergarten D and kindergarten E with --youtien [D] .end (), --youtien [E] .end (), so insert them. It's fine.
Also, this is ** if there are enough toddlers in youtien , and there may not be enough toddlers to erase. In that case, it is good to divide the case as shown in the code below, but if the size of ** youtien [E] and youtien [D] is 0, you can simply do not operate ** I later realized that ( simplification of such problems is very important **).
Repeat the above operation for each query, get the smallest element with youjitati with youjitati.begin (), and output it.
E.cc
//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//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.
#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--)
//x is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#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 f=2*pow(10,5);
ll n,q;cin >> n >> q;
vector<multiset<pair<ll,ll>>> youtien(f);
vector<ll> doko(n);
vector<ll> tikara(n);
REP(i,n){
ll a,b;cin >> a >> b;b--;
youtien[b].insert(MP(a,i));
doko[i]=b;
tikara[i]=a;
}
multiset<pair<ll,ll>> youjitati;
REP(i,f){
if(!(youtien[i].empty())){
youjitati.insert(*(--youtien[i].end()));
}
}
REP(i,q){
ll c,d;cin >> c >> d;c--;d--;
if(youtien[d].size()>0 and youtien[doko[c]].size()>1){
youjitati.erase(*(--youtien[d].end()));
youjitati.erase(*(--youtien[doko[c]].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
youjitati.insert(*(--youtien[doko[c]].end()));
doko[c]=d;
}else if(youtien[d].size()==0 and youtien[doko[c]].size()>1){
youjitati.erase(*(--youtien[doko[c]].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
youjitati.insert(*(--youtien[doko[c]].end()));
doko[c]=d;
}else if(youtien[d].size()>0 and youtien[doko[c]].size()==1){
youjitati.erase(*(--youtien[doko[c]].end()));
youjitati.erase(*(--youtien[d].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
doko[c]=d;
}else{
youjitati.erase(*(--youtien[doko[c]].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
doko[c]=d;
}
cout << (youjitati.begin())->F << endl;
}
}
F problem
I can think of BFS and DFS ** because there is no ** search and weight on the squares of the number of $ H \ times W \ leqq 10 ^ 6 $. Also, since it is the minimum number of moves, I will search with BFS **.
First, consider all possible candidates for the next cell to be traced by each recursion. In other words, consider 4K streets that advance by K squares in four directions, up, down, left, and right, which can be the next square (however, in the case of @ square, you cannot go further). However, if you search all of this, you will find that you are searching too much ** (even if you do not know that you are searching too much, you will notice it when you TLE). Therefore, you should consider ** the minimum mass condition ** for a necessary and sufficient search.
Here, when I actually think of the previous search in my mind, I implemented BFS, which is the TLE, by the method of ** skipping the already searched cells and following the K cells **. I felt that there was a waste in terms of re-searching the squares that had already been searched **. In other words, since it is possible to search from the already searched square to K squares in four directions, the already searched squares have already been searched. Therefore, we considered that if there is a cell that has already been searched in addition to the cell of @, the search after that will end. This is illustrated below.
However, at this rate, it is not possible to consider a cell that has been searched, but the search beyond that cell has not started. We can say that such cells are ** cells of the same depth **, and if there are such cells, we will continue to search. This is illustrated below.
If you think about it as above, you can think of it as a slightly different type of BFS and implement it easily, and the code will be as follows.
F.py
import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque([[x1-1,y1-1]])
dp[x1-1][y1-1]=0
def bfs(d):
global dp,now
l=len(now)
dp_sub=deque()
cand=set()
for i in range(l):
x,y=now.popleft()
for j in range(1,min(k+1,w-y)):
if dp[x][y+j]==inf:
dp_sub+=[[x,y+j,d]]
cand.add((x,y+j))
else:
break
for j in range(1,min(k+1,y+1)):
if dp[x][y-j]==inf:
dp_sub+=[[x,y-j,d]]
cand.add((x,y-j))
else:
break
for j in range(1,min(k+1,h-x)):
if dp[x+j][y]==inf:
dp_sub+=[[x+j,y,d]]
cand.add((x+j,y))
else:
break
for j in range(1,min(k+1,x+1)):
if dp[x-j][y]==inf:
dp_sub+=[[x-j,y,d]]
cand.add((x-j,y))
else:
break
while dp_sub!=deque([]):
e=dp_sub.popleft()
dp[e[0]][e[1]]=e[2]
for i in cand:
now+=[i]
if l!=0:bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
answerF.cc
//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//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.
#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--)
//x is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define PF pop_front
#define F first //The first element of pair
#define S second //The second element of pair
ll h,w,k;
vector<vector<ll>> dp;
deque<pair<ll,ll>> now;
void bfs(ll d){
ll l=SIZE(now);
if(l==0){
return;
}
deque<vector<ll>> dp_sub;
set<pair<ll,ll>> cand;
REP(i,l){
ll x,y;x=now.front().F;y=now.front().S;now.PF();
FOR(j,1,min(k,w-y-1)){
if(dp[x][y+j]==INF){
dp_sub.PB({x,y+j,d});
//dp[x][y+j]=d;
cand.insert(MP(x,y+j));
//now.PB(MP(x,y+j));
}else{
break;
}
//if(dp[x][y+j]==-1)break;
}
FOR(j,1,min(k,y)){
if(dp[x][y-j]==INF){
dp_sub.PB({x,y-j,d});
//dp[x][y-j]=d;
cand.insert(MP(x,y-j));
//now.PB(MP(x,y-j));
}else{
break;
}
//if(dp[x][y-j]==-1)break;
}
FOR(j,1,min(k,h-x-1)){
if(dp[x+j][y]==INF){
dp_sub.PB({x+j,y,d});
//dp[x+j][y]=d;
cand.insert(MP(x+j,y));
//now.PB(MP(x+j,y));
}else{
break;
}
//if(dp[x+j][y]==-1)break;
}
FOR(j,1,min(k,x)){
if(dp[x-j][y]==INF){
dp_sub.PB({x-j,y,d});
//dp[x-j][y]=d;
cand.insert(MP(x-j,y));
//now.PB(MP(x-j,y));
}else{
break;
}
//if(dp[x-j][y]==-1)break;
}
}
while(!dp_sub.empty()){
vector<ll> d=dp_sub.front();
dp[d[0]][d[1]]=d[2];
dp_sub.PF();
}
for(auto i=cand.begin();i!=cand.end();i++){
now.PB(*i);
}
bfs(d+1);
}
signed main(){
//Code for speeding up input
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> h >> w >>k;
ll x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;
vector<string> c(h);REP(i,h)cin >> c[i];
dp.resize(h);
REP(i,h){
REP(j,w){
if(c[i][j]=='.')dp[i].PB(INF);
else dp[i].PB(-1);
}
}
now.PB(MP(x1-1,y1-1));
dp[x1-1][y1-1]=0;
bfs(1);
if(dp[x2-1][y2-1]!=INF) cout << dp[x2-1][y2-1] << endl;
else cout << -1 << endl;
}
Recommended Posts