Codeforces Round 858

728x90

결과

링크 2023.03.18 DIV2
2솔, 3347/11529 (29%) 1401 (-19) (퍼포1263)

3솔 못한 div2, 오랜만에 코포라 당황하고 실수한 부분이 많았다. 3솔만 했어도 점수가 올랐을 것 같아 아쉽다. 다음에는 좀 더 침착하게 대회에 임해야...

해설이 늦었다. 학기중이라 정신이 없다.

A Walking Master

개요

00:08:45
구현, 수학
왼쪽 위 혹은 왼쪽으로만 이동가능할 때, 두 지점간 최소 이동횟수 구하기

접근

자칫 잘못 접근하면 어렵기 쉽다. 그런데 생각보다 어렵지 않다. 이동을 오른쪽 위나 왼쪽으로만 할 수 있으므로
1. 아래 이동은 안된다. Y값이 작다면 -1 반환
2. 오른쪽 이동은 오른쪽 위로 향하는 대각선을 그어 오른쪽 영역에 있다면 이동할 수 없다. 즉 (a,b)가 직선 y=x+p, (c,d)가 직선 y=x+q 위에 있다고 할 때, q가 p보다 크거나 같아야만 이동할 수 있다.
3. 나머지는 어떻게 이동하냐? 하면 y값을 맞춘 뒤 x값을 맞추자. y값을 맞추기 위해 dy만큼 오른쪽 위로 이동하고, dy만큼 오른쪽으로 갔으니 x값을 맞추기 위해 dy+dx만큼 왼쪽으로 이동하면 된다.
4. dy는 위로 이동하는 것이니까 d-b, dx는 왼쪽으로 이동하는 것이니까 a-c가 된다.

Source code

#include <bits/stdc++.h>
using namespace std;

int test() {
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if (d<b)
        return -1;
    if ((b-a)>(d-c))
        return -1;
    return (d-b)+(a-b+d-c);
}

int main() {
    int t;
    cin>>t;
    while(t--)
        cout<<test()<<"\n";
}

B Mex Master

개요

00:27:54
Greedy, 구성적
배열을 재배치하여 인접한 두 원소의 합의 MEX가 최소가 되도록 만들기

접근

MEX의 최소를 어떻게 생각할 수 있을까? 만약 모든 수가 양수라면? 즉 0이 없다면, 어떤 두 수를 합쳐도 2 이상이다. 어떤 배치에도 0은 등장하지 않을 수 있다. 이때의 MEX는 0이 된다.
그러면 어떤 배치에도 k가 인접한 원소의 합이 되면 안된다는 것이다. 이걸 바꿔 생각하면? 어쩔 수 없이 k가 만들어지는 상황을 구하면 된다. 예를들면 3번 TC
```
 0 0 0 0 0 1 2 3

 0 1 0 2 0 3 0 0
```
0이 나오지 않도록 최선의 배치를 하는 방법인데, 이래도 인접합이 0이 나와버린다. 즉, 0이 전체의 절반을 초과하면 MEX가 0이 될 수 없다.
그럼 위 케이스의 답은 1이 되는데, 이때는 어차피 인접합 0은 무조건 만들어지니까, 0을 한쪽에 몰아넣고 나머지 인접합을 최대로 만들어야 하는데, 아래처럼 배치해보자.
```
 0 0 0 0 0 2 1 3
```
1보다 2를 먼저 등장시키는 것이 이득이다. 그럼 1의 개수도 세어주어야 하는 건가? 하는 생각을 할 수 있다.
MEX가 0이 되는 상황은 0의 개수가 전체 절반 이하 였다. 그러면 다음으로 MEX가 1이 될 상황을 생각해보자.
1. 만약 0,1을 제외한 원소가 하나라도 있다면? 우선 0을 깔고, 그 원소 k를 먼저 등장시키면 된다. 그럼 어떻게 하더라도 인접합이 1이 될 수 없다.
2. 하나도 없다면? 어떻게 배치해도 인접합 1은 나온다. 그때 MEX는 2가 된다. MEX가 0,1이 아닌 2가 될 수도 있다는 생각을 하는 것이 어려운 문제였다.
그런데 여기까지만 하면 오류가 뜬다. 모두 0인 케이스를 고려하지 않았기 때문인데, 모두 0이면 당연히 MEX가 1이 된다.

Pseudo code

if (count0 = n)
    return 1
if (count0 <= (n+1)/2)
    return 0
if (count0 + count1 == n)
    return 2
else
    return 1

Source code

#include <bits/stdc++.h>
using namespace std;

int test() {
    int c0=0,c1=0;
    int n,x;
    cin>>n;
    for (int i=0;i<n;i++) {
        cin>>x;
        if (x==0)c0++;
        if (x==1)c1++;
    }
    if (c0==n)
        return 1;
    if (c0<=(n+1)/2)
        return 0;
    if (c0+c1<n)
        return 1;
    return 2;
}

int main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
        cout<<test()<<"\n";
}

C Sequence Master

개요

WA
Bruteforce, 수학
2n개의 원소를 포함하는 배열의 절반의 합과 나머지 절반의 곱이 같도록 하는 새로운 배열과, 원 배열의 차이의 최솟값

접근

어렵다는 평이 많았던 문제. 사실 케이스가 정해져 있는데 이 케이스를 특정하지 못한 경우라면 2솔로 만족하는 것이 좋고, 케이스를 특정했는데 오류가 떴다면 나랑 비슷한 상황이니 앞으로 실수하지 않으면 될 것 같다. 엄밀하게 계산할 필요는 없고, 몇 개 케이스가 특정되고 테케가 풀린다면 그냥 넘어가면 된다.
우선 접근을 할 때 서로 다른 원소의 개수로 해주는 것이 좋다. 그전에 n=1일 때, {a,b}라면 a=b만 만족하면 된다. 따라서 abs(a[0]-a[1])이 답.
나머지 상황에서는 먼저 모든 원소가 같을 때를 생각해보자.

${q = \{a,a,\cdots ,a\}}$
$a^{n}=na,\quad a=0\quad or\quad a^{n-1}=n$

$a^{n-1}=n\rightarrow a=n^{\dfrac{1}{n-1}}$을 만족하는 n은 2 외에는 안된다는 것을 알 수 있다. n이 2를 초과하면 정수가 아니기 때문. 따라서 모든 원소가 같은 경우는 모두 0이거나, n=2일 때 모두 2이거나 이다.
다음으로 하나의 원소만 다를 때를 생각하자.

$q = \{a,a,\cdots ,a,b\}$
$a^{n}=(n-1)a+b,\quad a^{n-1}b=na$

둘을 연립하면,
$a^{2n-1}=(n-1)a^{n}+na$
먼저 a=0일 수가 있는데 이때는 b도 0이 되어버린다. 다음으로 0이 아닐 때,
$a^{2n-2}-(n-1)a^{n-1}-n=0 \rightarrow (a^{n-1}-n)(a^{n-1}+1)=0$
$a^{n-1}=-1,n$
$a^{n-1}$이 n일 때는 2를 제외하고는 안된다고 말했고, n이 2, a가 2가 되면 마찬가지로 b도 2가 되어버린다. 따라서 $a^{n-1}=-1$이 되기 위해 n은 짝수여야 하고, 이때 a=-1, b=n이 된다.

증명

나머지 케이스는 없는데, 왜냐? 증명이 맞는지는 모르겠는데 일단 해보자.
${q=\{a_1,a_2,\cdots,a_{2n}\}}$

만약 위 집합에 0이 하나라도 포함되었다고 생각하자. 그럼 어떤 두 원소 ai, aj에 대해 다음이 성립한다. S는 ai, aj를 포함하지 않는 n-1개 원소의 총합이다.

$0=a_i+S=a_j+S$
따라서 ai=aj가 되는데, i,j는 서로 다른 모든 인덱스이므로 0을 제외한 모든 원소가 같아진다. 따라서

$a_i=a_j=x,\quad 0=nx \rightarrow q=\{0,\}$
모든 원소가 0인 상황이 되어버리므로 q에는 0이 포함되면 안된다.
다음으로, 어떤 두 i,j에 대해 아래와 같은 상황이 일어날 수 있다. 각각 ai를 선택하고 aj를 선택하지 않았을 때, aj를 선택하고 ai를 선택하지 않았을 때의 상황이고, P는 선택한 원소 중 나머지 n-1개의 곱, S는 선택하지 않은 원소 중 나머지 n-1개의 합이 된다. 0은 포함되지 않았으므로 P는 0이 될 수 없다. (해설하는 과정에서 P,S를 집합으로 표현할 수도 있는데, 같은 것이라 생각하면 된다.)
$Pa_i=a_j+S\quad Pa_j=a_i+S\quad\cdots(A)$
$P(a_i-a_j)=a_j-a_i$
여기서 P=-1이거나, ai=aj라는 결론이 나오는데, 먼저 아래 두 가지 상황부터 가정하자.
P내부에 존재하는 ax와 aj를 교환한다고 생각하자. 즉 ax는 배제, aj는 포함으로 간다. P가 0이 아니므로 ax도 0이 아니다.
$\dfrac{P}{a_x}a_ia_j=a_x+S\quad\cdots (B)$
동일하게 S 내부에 존재하는 ay와 ai를 교환하자. ay는 포함, ai는 배제로 간다.
$Pa_y=a_i+a_j-a_y+S\quad\cdots (C)$
마지막으로 P의 원소인 ax와 S의 원소인 ay를 교환하자. ay는 포함, ax는 배제로 간다.
$\dfrac{P}{a_x}a_ia_y=a_j+a_x-a_y+S\quad\cdots (D)$
P=-1이라면, ax는 1또는 -1이 된다. 이때의 식 B는
$a_x=1)\quad Pa_ia_j=1+S\rightarrow a_ia_j=-1-S$
$a_x=-1)\quad -Pa_ia_j=-1+S\rightarrow a_ia_j=-1+S$
이렇게 나누어 줄 수 있는데, P가 1만으로 이루어졌는지, 1,-1을 둘 다 포함하는지, -1만 포함하는지에 따라 나누어주자.
1. P에 1만 포함된다면 모든 값의 곱이 -1이 될 수 없어 모순이다.
2. 만약 P에 -1과 1이 모두 포함된다면 둘을 연립할 수 있다.
  $S=0,a_ia_j=-1$
  ai를 1, aj를 -1이라 하자. 이때의 식 D는
  $a_x=1)\quad Pa_y=-a_y+S$
  $a_x=-1)\quad -Pa_y=-2-a_y+S$
  $\rightarrow a_y=-1$
  S에 포함된 모든 원소가 -1이 되어야 하는데, S의 합이 0이므로 모순이 된다.
  ai를 -1, aj를 1이라고 하자. 이때의 식 D는
  $a_x=1)\quad -Pa_y=2-a_y+S$
  $a_x=-1)\quad Pa_y=-a_y+S$
  $\rightarrow a_y=1$
  마찬가지로 S가 0이 될 수 없어 모순이다.
3. 따라서 P에는 -1만 포함되어야 하고, n은 짝수여야 한다. 이때 식 C를 정리하면
  $C)\quad -a_y=a_i+a_j-a_y+S\rightarrow a_i+a_j=S$
  따라서 식 B와 연립해 이차방정식을 해결하면 ai,aj의 후보를 다음과 같이 정할 수 있다.
  $a_i,a_j=-1,-(S-1)$
  여기서 식 D를 정리하면
  $D)\quad a_ia_y=a_j-1-a_y+S$
  이렇게 되는데, ai에 -1을 대입하면 식 C와 같은식이 되니, -(S-1)을 대입하자.
  $-(S-1)a_y=-2-a_y+S$
  $S(a_y+1)=2(a_y+1)$
  따라서 S=2 혹은 ay=-1인데,
  1. ay=-1이면 ai를 제외하고 전부 -1이 되면서 S=-(n-1)이 되고, ai=n이 된다.
  2. S=2라면 ai=-1이 된다. 이번에는 S에 속한 2개의 원소 ay1,ay2를 -1과 바꿀건데,
    $-1^{n-2}a_{y1}a_{y2}=-1+2-2-a_{y1}-a_{y2}$
    n이 짝수이므로 $a_{y1}a_{y2}=-1-a_{y1}-a_{y2}$가 되면서 연립방정식을 풀어줄 수 있다.
    $x^2-Tx-(T+1)=0\quad(T=a_{y1}+a_{y2})$
    이때의 x는 -1, T+1이고, 이런식으로 2개의 원소 중 하나를 -1로 결정하다보면 하나만 제외하고 모두 -1이 된다. 이는 앞의 상황과 같다.
다음으로 ai=aj=x라고 해보자. 이때의 식 A와 B를 정리하면,
$S=(P-1)x,\quad \dfrac{P}{a_x}x^2=a_x+S$
이차방정식을 풀어주면 아래와 같이 정리된다.
$a_x=-Px,x$
따라서 P에 속하는 모든 원소는 같다.
1. 만약 ax=-Px라면, P에 속하는 모든 원소가 -Px라는 것이다. P를 재정의하면 아래와 같다.
  $P=(-Px)^{n-1}=(-1)^{n-1}P^{n-1}x^{n-1}$
  P는 0이 아니므로
  $1=(-1)^{n-1}P^{n-2}x^{n-1}$
  이고, P,x는 모두 1 또는 -1이어야만 한다.
  1. 만약 n이 짝수면 n-1이 홀수, n-2가 짝수가 된다. 1또는 -1의 k승은 k%2승과 같으므로, 식을 정리하면 1=-x가 된다. 따라서 x=-1, ax=P. 이때 식 B,C를 정리하면,
    $B)\quad 1=P+S$
    $C)\quad Pa_y=-2+a_y+S\rightarrow(P-1)a_y=S-2=-1-P$
    P는 1,-1이 가능하므로
    $P=1)\quad S=2,P=-1$
    $P=-1)\quad -2a_y=0\rightarrow a_y=0$
    P는 1일 때는 P가 1이면서 -1인 모순이, P가 -1일 때는 0을 포함하는 오류가 발생한다.
  2. n이 홀수면 n-1은 짝수, n-2가 홀수가 된다. 마찬가지로 식을 정리하면 P=1, ax=-x가 된다. 이때 식 B,C를 정리하면,
    $B)\quad-x=-x+S\rightarrow S=0$
    $C)\quad2a_y=2x+S=2x\rightarrow a_y=x$
    S의 원소가 모두 x이고 합이 0이므로 x는 0이 된다. q에 0이 포함되므로 안된다.
2. 만약 ax=x라면 P에 속하는 모든 원소가 x라는 것이다. 식 A와 C를 정리해보자.
  $x^n=x+S,\quad x^{n-1}a_y=2x-a_y+S$
  $(x+S)a_y=2x^2-a_yx+Sx$
  $2x^2-(2a_y-S)x-Sa_y=0,\quad (2x+S)(x-a_y)=0$
  $\rightarrow x=a_y,S=-2x$
  1. 만약 x=ay라면, q에 속하는 모든 원소가 같은 것이 된다. 이때 $x^n=nx$가 성립하고 이걸 만족하는 0이 아닌 원소는 2뿐이다.
  2. 만약 S=-2x라면, 다음이 성립하는데,
    $x^n=x+S=-x,\quad x=0,x^{n-1}=-1$
    x=0이면 q에 0이 존재해버리므로 안된다.
    그렇지 않고 $x^{n-1}=-1$이라면, x=-1, n은 짝수일 수밖에 없는데, 이때는 앞에서 P=-1일 때의 상황과 같은 상황이 된다.

조금 길게 설명하긴 했는데 핵심은 포함한 원소를 배제, 배제한 원소를 포함시키며 나오는 식을 연립하는 것이다. 이러면 모든 케이스에 대해 모두 0이거나, 하나 빼고 모두 -1인 상황임을 알 수 있다.

그런데 문제는 여기까지 다 풀어놓고 거리를 잘못구했다는 것이다. 왠지 아무리 해도 안나오더라. 아래 케이스를 보자.

4
-1 -1 -1 -1 -1 -1 2 6
// -1 -1 -1 -1 -1 -1 4 -1 => 9
// -1 -1 -1 -1 -1 -1 -1 4 => 5

이때의 답은 5가 되는데, 나처럼 n과의 거리가 최소인 위치를 미리 구해버리면 2에서 n과의 거리를 구해버리기 때문에 답이 9가 나온다. 모든 위치와 n과의 거리를 구하면서 최솟값을 업데이트 해줘야 한다.

Source code

// WA
#include <bits/stdc++.h>
using namespace std;

using ld=long long;
#define N 400010
ld a[N];

ld test() {
    ld n;
    cin>>n;
    ld j=-1;
    ld p=3e9;
    for (ld i=0;i<2*n;i++) {
        cin>>a[i];
        if (abs(a[i]-n)<p)
            j=i, p=abs(a[i]-n);
    }
    if (n==1)
        return abs(a[0]-a[1]);
    ld s=0,k=0;
    for (ld i=0;i<2*n;i++) {
        s+=abs(a[i]);
        k+=abs(a[i]-ld(2));
    }
    if (n%2) return s;
    ld m=0;
    for (ld i=0;i<2*n;i++) {
        if (i==j) {
            m+=abs(a[i]-n);
            continue;
        }
        m+=abs(a[i]+ld(1));
    }
    if (n!=2) return min(s,m);
    return min(min(s,m),k);
}

int main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);
    ld t;
    cin>>t;
    while(t--)
        cout<<test()<<"\n";
}

//up solving
#include <iostream>
using namespace std;

using ld=long long;
#define N 400010
ld a[N];

ld test() {
    ld n;
    cin>>n;
    for (int i=0;i<2*n;i++)
        cin>>a[i];
    if (n==1) return abs(a[0]-a[1]);
    ld s=0,k=0,m=0;
    for (int i=0;i<2*n;i++) {
        s+=abs(a[i]);
        k+=abs(a[i]-2);
        m+=abs(a[i]+1);
    }
    if (n%2) return s;
    ld p=s;
    for (int i=0;i<2*n;i++)
        p=min(p,m-abs(a[i]+1)+abs(a[i]-n));
    if (n!=2) return p;
    return min(p,k);
}

int main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);
    ld t;
    cin>>t;
    while(t--)
        cout<<test()<<"\n";
}

728x90

저작자표시 비영리 변경금지

'코드포스 > Rated' 카테고리의 다른 글

Educational Codeforces Round 149 (0)	2023.05.26
Codeforces Round 874 (0)	2023.05.20
Educational Codeforces Round 148 (0)	2023.05.13
Codeforces Round 872 (0)	2023.05.09
Codeforces Round 852 (0)	2023.02.13
Codeforces Round 851 (0)	2023.02.10
Codeforces Round 848 (0)	2023.02.08
TypeDB Forces 2023 (0)	2023.02.08

oculis.log

Codeforces Round 858

결과

A Walking Master

개요

접근

Source code

B Mex Master

개요

접근

Pseudo code

Source code

C Sequence Master

개요

접근

증명

Source code

'코드포스 > Rated' 카테고리의 다른 글

댓글

티스토리툴바