AtCoder Beginner Contest 178 Review
This time's results
Impressions of this time
This time too, the result was disappointing. The E problem took a long time without being particular about my policy.
I regret the F problem because it took a long time to implement it trying to do lie greed using set even though I had some time. ** Do not do greed with proper feelings **. Also, this problem was ** actually a gag problem **, and the correct answer was what I thought was not the solution. I regret too much ...
It was a disappointing result this time as well, but I feel that the soil is gradually gaining strength, so I would like to do my best without giving up. Probably I will be able to ride the waves if I can put out about yellow performance, so I will devote myself.
Problem A
I tried to write it easily and failed.
A.py
print(1 if int(input())==0 else 0)
B problem
** Since it can be shown that the value is larger when the end is selected than when the non-end part is selected **, the maximum value of the four types of multiplication of the ends is calculated.
B.py
a,b,c,d=map(int,input().split())
print(max(a*c,a*d,b*c,b*d))
C problem
** The existence condition is to consider the negation and consider the complement **. That is, except when only 1 ~ 9 is selected from the whole ($ 10 ^ n
C.py
n=int(input())
mod=10**9+7
print((pow(10,n,mod)-2*pow(9,n,mod)+pow(8,n,mod)+2*mod)%mod)
D problem
** If you know the length of the sequence, it seems that it can be decided by overlapping combinations **. Here, the length of the sequence is at most $ [\ frac {n} {3}] $ **, provided that all terms are 3 or more. Also, ** I want to make duplicate combinations 0 or more **, so subtract 3 from all terms. Therefore, if the length of the sequence is $ x $, consider the case where the sum is $ s-3x $ and all the numbers are 0 or more. At this time, it can be rephrased as the problem of arranging ** $ s-3x $ spheres and $ x-1 $ partitions **, and the total number of combinations is $ _ {s-3x + x-1} C _ { It becomes s-3x} $. Also, since I want to find the remainder of $ 10 ^ 9 + 7 $, I used Calculation of binomial coefficient by inverse element.
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
ll fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Creating a table
void COMinit() {
fac[0]=fac[1]=1;
finv[0]=finv[1]=1;
inv[1]=1;
FOR(i,2,MAXR){
fac[i]=fac[i-1]*i%MOD;
inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
finv[i]=finv[i-1]*inv[i]%MOD;
}
}
//Calculation of binomial coefficient
ll COM(ll n,ll k){
if(n<k)return 0;
if(n<0 || k<0)return 0;
return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
COMinit();
ll s;cin>>s;
ll ans=0;
FOR(x,1,ll(s/3)){
ll k=s-3*x;
ans+=COM(k+x-1,k);
ans%=MOD;
}
cout<<ans<<endl;
}
E problem
** It seemed difficult and I lost my concentration **. Although it is a consequential theory, if I can pass this problem at high speed, I can solve the F problem, so I would like to train with bacha so that I can maintain my concentration.
Also, during the contest, I was able to solve it because I found this article by google. This question is not easy, so I think many people googled to get the right answer.
First,Or fix one of the two points
E.py
n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]
ans=[]
cand=[xy[i][0]+xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[-xy[i][0]+xy[i][1]for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[-xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
print(max(ans))
F problem
First of all, I thought about a greedy method of swapping so that the previous elements do not match in order, but I rejected it because it seems to be unjustified. Next, I thought that if you take advantage of the fact that they should not match and that they are all sorted, then ** by reversing, only the middle ** will match (✳︎). However, I rejected this method because I thought it was too easy. After that, the method I came up with was to decide in order from the most. I implemented this method even though I couldn't justify it. Also, the implementation was a bit heavy and didn't finish solving during the contest.
While looking at the answers of other people on Twitter after the contest, I noticed ** the sweetness of my consideration ** during the contest. ** It's so easy that I rejected it **. I have a habit of stopping thinking ** if the solution to a problem is too difficult or too easy **, so I would like to stop. Anyway, if you proceed with the consideration of (✳︎), this problem can be solved as follows.
First, consider how many 1 ~ $ n $ are in total for $ A $ and $ B $, and if there are more elements than $ n $, it is not possible to create a sequence that satisfies the theme. Since it is clear from the principle, No is output.
Under this, first reverse B according to the previous policy. At this time, there is only one ** $ p $ that becomes $ (\ forall x \ in [l, r]) (A \ _x = B \ _x = p) $. On the contrary, if it does not exist, it will satisfy the purpose if it is output as it is. At this time, $ (\ forall x \ notin [l, r]) (A \ _x \ neq B \ _x) $ also holds. (Proof is omitted)
Now swap ** for any element of ** $ x \ in [l, r] $. This swap is between $ x (\ in [l, r]) $ and $ y (\ notin [l, r]) $. Also, this swap can be done for $ y (\ notin [l, r]) $ if it is $ A \ _y \ neq p $ and $ B \ _y \ neq p $, ** Swap selected The two elements never match at their respective indexes **. Furthermore, since $ p $ appearing in $ A $ and $ B $ is less than $ n $, it is possible to swap for any $ x (\ in [l, r]) $ (*). * It is good to think that you can swap so that $ p $ exists in all indexes when you swap to the maximum **.).
From the above, the validity of the method of repeating swapping only where it overlaps and where it does not overlap in the reverse order has been shown, so this is implemented as follows.
F.py
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
from collections import Counter,deque
x,y=Counter(a),Counter(b)
for i in range(1,n+1):
if x[i]+y[i]>n:
print("No")
exit()
ans=b[::-1]
change=deque()
num=-1
now=deque()
for i in range(n):
if a[i]==ans[i]:
change.append(i)
num=ans[i]
else:
now.append(i)
if change==[]:
print("Yes")
print(" ".join(map(str,ans)))
exit()
while len(change):
q=now.popleft()
p=change.popleft()
if a[q]!=num and ans[q]!=num:
ans[q],ans[p]=ans[p],ans[q]
else:
change.appendleft(p)
print("Yes")
print(" ".join(map(str,ans)))
Recommended Posts