Codeforces Round #695 (Div. 2)

문제 링크

codeforces.com/contest/1467

 

 

A. Wizard of Orz

문제

0~9까지 표현이 가능한 디지털 패널이 n개가 있다고 한다. 이 패널은 매초 1씩 증가하다가 9가 된 다음 1초 후에는 0으로 다시 표기된다.

이 패널을 멈추면 숫자가 일시정지가 되는데, 만약 패널이 일시정지가 되면 인접한 패널도 1초 뒤에 일시 정지가 되고,  그 일시 정지된 패널의 인접한 패널도 1초 뒤 일시 정지가 되고, ... 이 과정을 반복하여 패널들이 전부 멈출 때까지 반복이 된다고 한다.

디지털 패널을 딱 한 개만 선택하여 멈추게 할 수 있을 때, 패널이 표현할 수 있는 가장 큰 수를 출력하시오.

모든 패널은 전부 0에서부터 시작한다.

 

풀이 1

숫자를 0~9중 하나를 선택하는 것인데, 최대 값을 구하는 문제이므로 첫번째 숫자판은 무조건 9이다.

두번째 숫자판은 첫번째 숫자판이 9이므로 0 또는 8이 나올 수 있는데, 여기서는 8을 선택하면 된다.

그리고 세번째 숫자판은 두번째 숫자판이 8이므로 7또는 9가 나올 수 있는데, 여기서는 9를 선택하면 된다. 이러면 9 8 9 이므로 두번째 숫자가 8이 될 때 숫자판을 멈추면 무조건 최대값이 나온다.

소스 코드 1

for _ in range(int(input())):
    n = int(input())
    if n == 1:
        print(9)
        continue
    ans = [0] * n
    ans[0] = 9
    ans[1] = 8
    for i in range(2, n):
        ans[i] = (ans[i - 1] + 1) % 10
    print(''.join(map(str, ans)))

 

B. Hills And Valleys

문제

a1, a2, a3 .... an의 수열이 있고 이때 hill 혹은 valley로 정의되는 원소들이 있다

hill : (aj>aj-1 && aj>aj+1, j>=2 && j<=n-1)

valley : (aj<aj-1 && aj<aj+1, j>=2 && j<=n-1)

또한 hill과 valley의 개수 합을 intimidation value 라고 부른다.

 

한번만 a1~an의 원소중 하나를 원하는 수로 바꿀 수 있다고 할 때(바꾸지 않아도 됨), 가능한 intimidation value의 최소값은 얼마인가?

 

풀이 1

각 hill과 valley를 첨점이라고 부르자, 이 문제에서는 둘을 구분 할 필요가 없다.

원소 1개를 바꿀때 첨점존재에 영향을 받는 원소는 선택한 원소의 좌우 양 옆 1개씩의 원소이다.(그 외의 원소는 아무런 영향을 받지 않는다.)

따라서 모든 원소를 좌에서 우로 스위핑하면서 가능한 경우들마다 양 옆 원소를 모두 살펴 보면 된다.

그럼 가능한 경우에는 무엇이 있을까 생각을 해보자

 

1. 선택한 점이 첨점이 아니면 볼 필요가 없다.

- 선택한 점을 수정함으로써 없앨 수 있는 첨점은 좌, 우의 원소 중 하나인데, 그 경우는 없애고자 하는 점의 차례에서도 동일하게 없앨 수 있기 때문에 중복된다

 

2. 선택한 점이 첨점이면 좌,우의 원소와 똑같이 맞췄을때가 가장 큰 이득을 본다.

- 양옆이 둘 다 첨점인 경우 : 둘 다 없애는 방법은 둘 중에 선택한점에서 가장 멀리 떨어진 원소와 같게할 경우 양옆과 본인원소를 포함해 총 3개의 첨점을 없앨 수 있다.

- 양옆의 둘 중 하나만 첨점인경우 : hill과 valley의 정의에서 초과 혹은 미만으로 정의 됬기 때문에 첨점인 원소와 같게할 경우 선택한첨점+같아진 원소의 첨점이 사라지게 된다.(선택한 첨점만 없애는 것 보다 이득이다.. 예외의 경우에도 손해는 안보는데 아래 예제에 나와있다)

- 양옆이 둘다 첨점이 아닌경우 : 당연히 양옆 중 하나로 맞추면 최대 이익인 1개를 얻을 수 있다

 

- 따라서 좌의 원소와 같아지게 했을때와 우의 원소와 같아지게 했을 때 얻을 수 있는 이익의 최대치를 구하면 무조건 최대 이익이 나오게 된다.

- 여기서 그냥 좌우 첨점개수만 가지고 구할 수 있지 않느냐 라고 생각 할 수 있는데 좌측의 좌측원소와 우측의 우측원소때문에 없던 첨점이 생겨나는 경우가 있어서 일일히 다시 계산을 해 보아야 한다ex(52431의 4를 생각해보면 첨점을 두개 없애려 하면 하나가 생겨나버리기 때문에 문제가 된다, ...만약 원소5개의 경우의 수를 다 나눌 자신있으면 해도 된다)

- 위에 표시한 예외 상황 때문에 이익 계산을 위해 나는 3원소중 (이전에 존재하는 첨점의 개수 - 변경후 첨점의 개수)를 이용하였다.. 어떻게 보면 슬라이딩 윈도우 같기도 하다.

- 위의 과정을 거치면 O(n)에 할 수 있으므로 30만개 원소 정도는 충분히 계산이 된다

소스 코드 1

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int t;
ll n;

vector<ll> v; //원소들의 리스트
vector<bool> point; //첨점 여부

inline bool fun(int i){ //해당 점이 첨점인지 확인하는 함수
    if(i==0||i==n-1) return false;
    if(v[i]<v[i-1]&&v[i]<v[i+1] || v[i]>v[i-1]&&v[i]>v[i+1]) return true;
    return false;
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> t;
    while(t--){
        cin >> n;
        v.clear();
        point.clear();
        for(int i=0;i<n;i++){
            ll a;
            cin >> a;
            v.push_back(a);
            point.push_back(0);
        }
        int ans = 0;
        for(int i=1;i<n-1;i++){
            if(fun(i)) point[i] = 1, ans++;
        }
        int max_val = 0;
        for(int i=1;i<n-1;i++){
            if(point[i]){
                int sum = point[i-1] + point[i] + point[i+1]; //sum : 기존첨점개수, sum2 : 변경후 개수
                int temp = v[i];

                v[i] = v[i-1];
                int sum2 = fun(i-1) + fun(i) + fun(i+1);
                max_val = max(max_val,sum-sum2);

                v[i] = v[i+1];
                sum2 = fun(i-1) + fun(i) + fun(i+1);
                max_val = max(max_val,sum-sum2);

                v[i] = temp;
            }
        }
        cout << ans-max_val << '\n'; //최대이익을 빼서 출력
    }

    return 0;
}

 

C. Three Bags

 

문제

3개의 가방이 있고, 각각의 가방에 숫자들이 들어가 있다. 다음과 같은 연산을 할 수 있다.

"서로 다른 두 가방에서 숫자를 1개씩 꺼내고 각각을 a,b라고 할 때, a를 a-b로 대체하고, b는 제거한다."

숫자가 1개가 남을 때 까지 이러한 연산을 적용했을 때, 최종적으로 남은 숫자의 최대값을 구하라.

 

 

풀이 1

서로 다른 두 가방에서 꺼낸 숫자를 각각 a,b라 하고  a>=b라 할 때, 연산을 적용하면 대체된 a-b는 a보다 작아지는 상쇄 효과가 발생합니다. 하지만 a를 제거하고 b를 b-a로 대체하면 b-a<0이 되고 이를 한 번 더 어떤 수 c와 연산하면 c-(b-a) = c+양수가 되서 증가하는 효과가 발생합니다. 이런 식으로 생각하면 b는 최대한 작은 것이 최적일 것입니다. 많은 수들을 최소의 b에 연산을 적용하면 그게 아마 최적일 것이란 생각이 문제 풀이의 시작점이었습니다. 

 b는 최대한 작은 것이 이득일 것이므로 각 가방을 오름차순으로 정렬합니다. 각각의 가방을 a[i]라 하고, 가방에 들어있는 숫자의 합을 t[i]라 할 때, 만약 1번째 가방에 있는 모든 수를 2번째 가방의 첫번째 수와 연산하면, 2번째 가방의 첫번째 수인 a[2][1]은 a[2][1] -(t1)이 됩니다. 이 수를 3번째 가방의 첫번째 원소와 연산하면, 3번째 가방의 첫번째 수는  a[3][1] -a[2][1]+t1으로 a[2][1]을 빼주긴 했지만 무려 1번째 가방 전체를 더한 효과를  얻었습니다. 

 

이러한 조작을 해보면 여러 수식이 나올 수 있지만 아래의 2가지 수식이 아마 최적일거라는 걸 알 수 있습니다.

1. t1 + t2 + t3  -2*(a[i%3+1][1]+a[(i+1)%3+1][1])  ( i :1~3)

2. t[(i+1)%3+1] + t[(i+2)%3+1] -t[i] (i:1~3)

 

예를 들어 1번째 수식은 다음과 같이 얻을 수 있습니다.

1) 1번째 가방의 1번째 원소에 2번째 가방의 1번째를 제외한 모든 수를 빼기 

2) 1번째 가방의 1번째 원소에 3번째 가방의 1번째를 제외한 모든 수를 빼기

3) 3번째 가방의 1번째 원소에 1번째 가방의 1번째를 제외한 모든 수를 빼기

4) 2번째 가방의 1번째 원소에 (교체된)1번째 가방의 1번째수를 빼기

5) (교체된)2번째 가방의 1번째 원소에 (교체된)3번째 가방의 1번째수를 빼기

 

1) a[1][1] -(t2-a[2][1])

2) a[1][1] -(t2-a[2][1])  - (t3-a[3][1])=-t2-t3+a[1][1]+a[2][1]+a[3][1]

3) a[3][1] -(t1-a[1][1])

4) a[2][1] -(-t2-t3+a[1][1]+a[2][1]+a[3][1]) = t2+t3 -(a[1][1]+a[3][1])

5)  t2+t3 -(a[1][1]+a[3][1]) -( a[3][1] -(t1-a[1][1]))=t1+t2+t3-2*(a[1][1]+a[3][1])

 

이렇게 2가지 수식으로 가방을 선택하는 모든 방법(3C2)을 고려해주면 답을 구할 수 있습니다.

 

소스 코드 1

#include <iostream>
#include <vector>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <climits>
#include <cmath>

#define all(v) (v).begin(), (v).end()
typedef long long ll;
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	vector<int> n(3);
	cin >> n[0] >> n[1] >> n[2];
	vector<vector<ll> > a(3);

	for (int i = 0; i < 3; i++) {
		vector<ll> tmp(n[i]);
		for (int j = 0; j < n[i]; j++) cin >> tmp[j];
		a[i] = tmp;
	}

	for (int i = 0; i < 3; i++) sort(all(a[i]));

	vector<ll> tot(3, 0);
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < n[i]; j++) tot[i] += a[i][j];
	}

	ll ans = 0;

	//t1+t2+t3 -2*(a11+a31)
	for (int i = 0; i < 3; i++) {
		ll t = tot[0] + tot[1] + tot[2];
		t -= 2 * (a[(i + 1) % 3][0] + a[(i + 2) % 3][0]);
		ans = max(ans, t);
	}

	//t1+t3-t2
	for (int i = 0; i < 3; i++) {
		ll t = tot[0] + tot[1] + tot[2];
		t -= tot[i] * 2;
		ans = max(ans, t);
	}

	cout << ans << '\n';
	return 0;
}