AtCoder Beginner Contest 178 Review

This time's results

スクリーンショット 2020-09-14 8.36.47.png

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 ) ( 9 ^ n ) and when 0 ~ 8 is selected ( 9 ^ n ). Also, when 1 to 8 are selected ( 8 ^ n $), they are duplicated, so they are excluded. So $ 10 ^ n-9 ^ n-9 ^ n + 8 ^ n $ is the answer. You also need to answer $ mod \ 10 ^ 9 + 7 $, but in Python you need to use the ** built-in ** pow function.

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 pointsxCoordinates andyYou can fix the coordinatesI thought I'd try, but I couldn't tell. Therefore, the next thing to considerTo remove the absolute valueis. here,As a typical pattern when removing the absolute value|x|=max(x,-x)There isIt seems. According to this, between two points(x\_1,y\_1),(x\_2,y\_2)Manhattan distancemax((x\_1+y_1)-(x\_2+y\_2),(x\_1-y_1)-(x\_2-y\_2),(-x\_1+y_1)-(-x\_2+y\_2),(-x\_1-y_1)-(-x\_2-y\_2))It will be. Therefore,Between any two pointsIf you think about each point(x,y)aboutx+y,x-y,-x+y,-x-yEvery time(Maximum value)-(minimum value)を求めてそのMaximum valueが答えとなります。

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

AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 181 Note
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 182 Note
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 156 WriteUp
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 183 Note
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 184 Note
AtCoder Grand Contest 046 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions