Round #728

A. Pretty Permutations

https://codeforces.com/contest/1541/problem/A

Problem - A - Codeforces

 

 1부터 n까지 숫자들은 자기자신에 해당하는 인덱스에 있지 않은 상태 && 각 숫자별 움직이는 횟수 합이 가장 작게 하여 정렬시킬 수 있는 경우를 출력해야한다.

 나같은 경우 n개의 숫자를 n번 움직여서 정렬시키는 문제로 잘못 읽어서 시간을 좀 써버렸다. 아니었으면 세자리 등수 안에 들어갔을 수도..

 

 각설하고 최적의 상태는 $2,1,4,3,6,5,...$ 이런 식으로 홀수 인덱스에 짝수, 짝수 인덱스에 홀수가 들어가있는 상태이다. 만약 저렇게 배열에 저장하고 $n=3$일 때 출력하면 $2,1,4$가 나오기 때문에 $n$이 짝수인 경우 홀수인 경우 나눠서 출력해야한다.

 내가 생각한 최적은 짝수일 때 $2,1,4,3,6,5,...n,n-1$, 홀수일 때 $2,1,4,3,6,5,...n,n-2,n-1$이다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int a[101];

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    for (int i = 0; i < 101; i += 2) a[i] = i + 2;
    for (int i = 1; i < 101; i += 2) a[i] = i;
    
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        if (n % 2 == 0) {
            for (int i = 0; i < n; i++) cout << a[i] << ' ';
        }
        else {
            for (int i = 0; i < n - 3; i++) cout << a[i] << ' ';
            cout << n << ' ';
            for (int i = n - 2; i < n; i++) cout << i << ' ';
        }
        cout << '\n';
    }
    return 0;
}

---

B. Pleasant Pairs

https://codeforces.com/contest/1541/problem/B

Problem - B - Codeforces

 완전탐색을 하는데 시간을 줄일 방법을 생각해야했다.

 $a_i\cdot a_j=i+j$ 식을 $a_j$에 대하여 정리해보자.

 $a_j=\frac{i+j}{a_i}$ 에서 이미 $i$와 $a_i$를 안다고 가정하면 $a_j$는 정수이기 때문에 $j=x\ast a_i-i$가 된다. 

 이제 $x$을 구해주기 위해 $i<j$ 식을 이용해보면, $i<x\ast a_i-i=>x>2i/a_i$가 된다.

 따라서 $x>=\lceil \frac{2i}{a_i}\rceil$를 구할 수 있다.

 결국, $j=\lceil \frac{2i}{a_i}\rceil \ast a_i-i$을 시작으로 $+a_i$를 해주면서 문제 조건에 맞는 $i,j$인지 확인하면 된다.

 

 이제 시간 복잡도를 생각해보자.

 $a_i$마다 최대 $\frac{n}{a_i}$번의 연산이 일어난다는 점, $1\le a_i\le 2n$인 것과 모든 $a_i$는 distinct하다는 점을 이용하면, 최대

$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+...+\frac{n}{2n}=n(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{2n})$번의 연산이 일어난다.

 마지막으로 조화 급수를 이용하면 $n(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{2n})=nlog(2n)$로 식이 정리된다. 따라서 시간복잡도는 $O(nlogn)$이 된다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int a[100001] = { 0, };

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
 
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            int x = (2 * i) / a[i] + 1; // 올림
            int start = x * a[i] - i;
            
            for (int j = start; j <= n; j += a[i]) {
                if (a[j] == (i + j) / a[i]) ans++;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

---

C. Great Graphs

https://codeforces.com/contest/1541/problem/C

Problem - C - Codeforces

 입력받은 배열 d를 우선 오름차순으로 정렬시키고 1번부터 n번 목초지가 있다고 생각해보자.

 낮은 번호에서 높은 번호로 가는 도로는 많이 지을수록 total weight cost를 낮추는 데에 도움이 안된다. 반대로 높은 번호에서 낮은 번호로 가는 도로는 많이 지을수록 total weight cost가 낮아지기 때문에 최대한 많이 지어야 한다.

 정리해보면 낮은 번호 -> 높은 번호 도로는 1->n 으로 가는 도로 하나만 짓고, 높은 번호 -> 낮은 번호 도로는 모두 다 지어야 한다. 

 

 B번 문제와 마찬가지로 이중 for문으로 완전탐색을 실시하면 $O(n^2)$이 되므로 TLE에 걸릴 확률이 높다. 자 그러면 문제 해결을 위해 식을 세워보자. $n$번에서 낮은 번호로 가는 도로들의 weight의 합을 구하는 식을 세우자.

$n번->1번=d_1-d_n$

$n번->2번=d_2-d_n$

$...$

$n번->n-1번=d_{n-1}-d_n$

$TotalWeight=(d_1+d_2+...+d_{n-1})-(n-1)d_n$

아! 찾았다. 구간 합을 이용하면 $O(1)$에 $n$번에서 낮은 번호로 가는 모든 도로의 합을 구할 수 있다.

구간 합을 통해 답을 구하는 것이기 때문에 시간 복잡도는 $O(n)$이 된다.

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

ll d[100001] = { 0, };
ll sum[100001] = { 0, };

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> d[i];
        sort(d + 1, d + n + 1);

	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + d[i]; // 구간 합
        ll ans = d[n]; // 1 -> n번으로 가는 도로 weight

        for (int i = n; i > 1; i--) {
            ans += (sum[i - 1]) - (i - 1) * d[i];
        }

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