Codeforces Round #728 (Div. 2) ABC 풀이

 

A. Pretty Permutations

 

문제 및 풀이

 

수열 [1, 2, ..., n] 을 i번째 인덱스의 수가 i가 되지 않도록 재배치합니다.

단, 숫자의 움직임(기존 i번째 수 -> j번 위치 이동 시 | i - j | ) 의 합을 가장 작게 하도록 재배치한 결과를 출력합니다.

 

처음에 [n, 1, 2, ..., n-1] 이 정답인 줄 알았는데, 한 번 틀리고 알았네요,,

만약 n이 짝수라면 모든 수는 1칸만 이동해도 재배치가 가능합니다. 배열에서 순서대로 2*i, 2*(i+1) 을 서로 뒤집어주면 됩니다.

반면 n이 홀수라면 딱 한 수만 2칸을 이동해주면 됩니다. 문제에서 나온 n=3 테스트케이스처럼, 맨 앞에 1,2,3 을 3,1,2 로 바꿔주면

이제 n-3은 짝수이므로 짝수일 때와 동일하게 둘 씩 뒤집어 배치하면 됩니다.

 

소스 코드(.cpp)

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

typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		if(n % 2 == 1){
			cout<<"3 1 2 ";
			int num = 4;
			n -= 3; n /= 2;
			while(n--){
				cout<<num + 1<<" "<<num<<" ";
				num += 2;
			}
		}
		else {
			int num = 1;
			n /= 2;
			while(n--){
				cout<<num + 1<<" "<<num<<" ";
				num += 2;
			}
		}
		cout<<"\n";
	}
	return 0;
}

 

B. Pleasant Pairs

 

문제 및 풀이

 

n개의 서로 다른 정수 배열이 있습니다. i < j, ai * aj = i + j 를 만족하는 (i, j) 순서 쌍의 개수를 출력하시오. 

 

우선 입력에서 n제한은 10만입니다. 당연히 이렇게 간단한 문제를 완전 탐색으로 해결하려는 건 어리석은 생각입니다. 시간 O(n^2)

이 문제를 풀면서 미리 전처리하고, n개를 순회하며 logn 이나 한 번만에 (ai, i) 와 식을 만족하는 경우의 수를 바로 구할 수 있을 줄 알고 다방면으로 생각했었는데, 생각보다 허탈하게 풀렸습니다.

 

문제에서 요구하는 식 ai * aj = i + j 를 다시 보자면,

우변의 (i + j) 는 가장 커봤자 n + n - 1 이고, 이 수는 최대 20만 정도 됩니다.

반면 좌변은 생각보다 2n - 1 보다 큰 수가 많이 등장하게 됩니다. 문제에서 강조한 1 ~ 2n 사이의 서로 다른 수라는 조건 때문이죠.

최대한 작게해서 배열을 [1, ..., n] 라고 생각해도, 2n - 1 보다 작은 경우는 생각보다 많지 않고, 이 부분은 입력받은 배열을 오름차순 정렬 후, 2중 for문으로 두 원소를 곱한 수가 2n - 1 보다 크면 안쪽 for문을 break; 해주는 방법으로 시간을 단축시킬 수 있습니다.

코드를 보는 게 더 이해가 쉽겠네요!  

 

소스 코드(.cpp)

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

typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		vector<pair<ll, ll> >v(n);
		for(int i=0; i<n; i++){
			cin>>v[i].first;
			v[i].second = i + 1;
		}
		
		sort(v.begin(), v.end());
		
		int ans = 0;
		
		for(int i=0; i<n; i++){
			for(int j=i + 1; j<n; j++){
				ll num1 = v[i].first; ll num2 = v[j].first;
				ll idx1 = v[i].second; ll idx2 = v[j].second;
				if(num1 * num2 >= 2 * n) break;
				if(num1 * num2 == idx1 + idx2) ans++;
			}
		}
		
		cout<<ans<<"\n";
		
	}
	return 0;
}

 

 

C. Great Graphs

 

문제 및 풀이

 

n개의 목초지(노드)로 구성된 가중치가 존재하는 단방향 그래프가 있습니다.

가중치는 음수도 있는데, 단 음의 사이클이 존재해서는 안됩니다. 또한 i -> j 노드로 가는 길은 하나만 있어야 합니다. 

문제는 1번 목초지(노드)에서 2 ~ n번 목초지로 갈 수 있는 최단 거리만 아는 상태에서 모든 에지의 가중치 합을 최소로 하도록 답을 출력하면 됩니다.

 

문제의 테스트 케이스가 굉장히 큰 힌트가 되었던 문제였네요

우선 테스트 케이스를 한 번 그려 보다 보면, 몇 가지 힌트를 얻어낼 수 있습니다.

 

1. 어떻게든 정답은 양수가 될 수 없습니다.

어떤 서로 다른 i, j 에 대해 i -> j 가중치가 양수라면, j -> i 가중치는 -(i -> j 가중치) 로 바꿔버리면 음의 사이클이 안 만들어지는 한 최솟값이 되기 때문입니다.

 

2. 가중치의 합을 최대한 줄이려면, d[i]는 d[i] 보다 작거나 같은 가장 큰 d 를 만족하는 노드 x에서 i로 연결되는 에지를 타고 오는 게 좋습니다. (말이 좀 난해할 수도 있는데, c++ lower_bound 를 생각하면 좋을 듯합니다)

이 부분은 d값들을 정렬해서 줄줄이 이어주면 됩니다. 반드시 이게 최적일 수밖에 없습니다.

 

3. 되돌아오는 길은 대부분 음수를 만들 수 있습니다. 

a-b-c-d-e 로 단방향 에지로 줄줄이 이어져있다고 생각해봅시다. 이 부분은 2번을 통해 미리 구해두면 좋습니다.

우선 바로 이전 노드로 되돌아오는 길은 1번 조건처럼 음수로 돌려서 만들어줍니다.

 

다음 2개 멀리 떨어져 있는 노드들부터는 해당 노드 ~ 직전 노드까지의 거리를 계속 더해주어야 합니다. 예를 들어 노드 e를 기준으로

c-d, b-c-d, a-b-c-d 거리입니다.  이런 식으로 거리를 다 더해야 하는데, 이 부분은 부분합을 계산해두면 한 번에 구할 수 있습니다. 방금 노드 e를 생각해보면, c-d, b-c-d, a-b-c-d 3가지 거리는 3 * (a ~ d) - (a-b, a-b-c) 과 같습니다.

전체 거리에서 빠진 부분을 빼주는 방식입니다. 이 부분에서 (a-b, a-b-c) 이 바로 부분합 포인트입니다.

 

 

소스 코드(.cpp)

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

typedef long long ll;

ll psum[100010];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		vector<ll>v(n);
		for(int i=0; i<n; i++) cin>>v[i];
		sort(v.begin(), v.end());
		
		ll ans = 0;
		psum[1] = v[1];
		for(int i=2; i<n; i++){
			psum[i] = psum[i-1] + v[i];
			ans += (psum[i-2] - (v[i] * (i-1)));
		}
		cout<<ans<<"\n";
	}
	return 0;
}