AtCoder Beginner Contest 181 Review

This time's results

None

Impressions of this time

This time it was about 30 minutes late. A to D were completed in about 20 minutes, and E was completed in about 20 minutes, but I chose no sub to avoid the rate dropping.

I wanted to release it after F was solved, but I didn't come up with the idea of Union Dinf. It was a difficult problem.

(I haven't written a commentary after problem D. I'll update it later today.)

Problem A

The color changes by chance.

A.py


print(["White","Black"][int(input())%2])

A.pas


var
    n:Smallint;
begin
	read(n);
    if (n mod 2)=1 then
        writeln('Black')
    else
        writeln('White');
end.

B problem

At first I thought that only one number would be written for each number due to misreading, but since it is not only one, all you have to do is find the sum of the numbers you wrote.

B.py


n=int(input())
ans=0
for i in range(n):
    a,b=map(int,input().split())
    ans+=(a+b)*(b-a+1)//2
print(ans)

C problem

I googled because I forgot, but ** To have the three points $ A, B, C $ in the same linear shape, the outer product of $ \ vec {AB}, \ vec {BC} $ should be 0. is**.

Therefore, you can write out three candidates with $ O (n ^ 3) $ and check if there is even one with a cross product of 0.

C.py


from math import gcd
n=int(input())
points=[list(map(int,input().split())) for i in range(n)]
def calc(i,j,k):
    global points,n
    vec1=[points[i][0]-points[j][0],points[i][1]-points[j][1]]
    vec2=[points[i][0]-points[k][0],points[i][1]-points[k][1]]
    return vec1[0]*vec2[1]==vec1[1]*vec2[0]
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if calc(i,j,k):
                print("Yes")
                exit()
print("No")

D problem

It is being updated.

D.py


s=list(map(int,input()))
from itertools import permutations
if len(s)<3:
    for i in permutations(s):
        x=int("".join(map(str,i)))
        if x%8==0:
            print("Yes")
            exit()
    print("No")
    exit()
d=dict()
for i in s:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
for i in range(100,1000):
    if i%8==0:
        x=list(map(int,str(i)))
        c=dict()
        for j in x:
            if j in c:
                c[j]+=1
            else:
                c[j]=1
        for j in c:
            if j not in d:
                break
            else:
                if d[j]>=c[j]:
                    continue
                else:
                    break
        else:
            print("Yes")
            exit()
print("No")

E problem

It is being updated.

E.py


n,m=map(int,input().split())
h=list(map(int,input().split()))
h.sort()
w=list(map(int,input().split()))
#Evenness([0,1] [2,3] … [n-3,n-2])
x=[0]
for i in range((n-3)//2+1):
    x.append(h[2*i+1]-h[2*i])
for i in range((n-3)//2+1):
    x[i+1]+=x[i]
#Bizarre([1,2] [3,4] … [n-2,n-1])
y=[0]
for i in range((n-3)//2+1):
    y.append(h[2*i+2]-h[2*i+1])
for i in range((n-3)//2+1):
    y[i+1]+=y[i]
from bisect import bisect_left
ans=10**12
for i in range(m):
    b=bisect_left(h,w[i])
    if b%2==0:
        c=b
    else:
        c=b-1
    ans=min(ans,x[c//2]+(y[-1]-y[c//2])+abs(w[i]-h[c]))
print(ans)

F problem

It is being updated.

F.cc


//Debugging options:-fsanitize=undefined,address

//Compiler optimization
#pragma GCC optimize("Ofast")

//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef int ll;

//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of endings)、のどちら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)
    ll n; //Element count

    //constructor
    UnionFind(ll n_):n(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 inline 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 inline 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;//When x and y are not in the same tree, attach y root ry to x root rx
    }

    //Determine if the tree to which x and y belong is the same
    bool inline same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }
};

typedef tuple<ll,ll,ll> td;

ll n;
pair<ll,ll> xy[101];
UnionFind uf(105);
td edges[5500];


signed main(){
    cout<<fixed<<setprecision(10);
    scanf("%d",&n);
    vector<pair<ll,ll>> xy(n);
    REP(i,n)scanf("%d%d",&xy[i].F,&xy[i].S);
    ll now=0;
    REP(i,n){
        edges[now]={(100-xy[i].S)*(100-xy[i].S),i,n};
        now++;
        edges[now]={(xy[i].S+100)*(xy[i].S+100),i,n+1};
        now++;
        FOR(j,i+1,n-1){
            ll k=(xy[i].F-xy[j].F)*(xy[i].F-xy[j].F);
            ll l=(xy[i].S-xy[j].S)*(xy[i].S-xy[j].S);
            edges[now]={k+l,i,j};
            now++;
        }
    }
    sort(edges,edges+now,[](consttd&l,consttd&r){returnget<0>(l)<get<0>(r);});
    REP(i,now){
        uf.unite(get<1>(edges[i]),get<2>(edges[i]));
        if(uf.same(n,n+1)){
            cout<<sqrt(get<0>(edges[i]))/2<<endl;
            break;
        }
    }
}

Recommended Posts

AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 160 Review
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 177
AtCoder Beginner Contest 172
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 181 Note
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 062 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