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;
}