TypeDB Forces 2023

결과

링크 2023.01.29 DIV1+2
2솔, 4343/11224 (38.69%) 1202 (+42) (퍼포1249)
 
3시간짜리 대회였는데 또 2솔 따리로 끝났다. A,B는 나름 빠르게 풀었는데 C에서 막혔다. 코포에 익숙해지려면 test함수를 따로 빼서 적는 습관부터 들여야겠다.

---

A Exponential equation

개요

00:06:31
y × x^y + x × y^x = n을 만족하는 (x,y) 아무거나 찾기

접근

1. 처음엔 완전탐색으로 찾아도 빠르게 걸릴 것 같아서 i, j에 대해 완탐 시행
2. 그런데 i=1에서 전부 걸리길래 1과 n/2에서 되는 것을 알게 됨
   1 × (n/2)^1 + (n/2) × 1^(n/2) = n
3. 홀수는 -1 짝수는 1, n/2로 찍으니까 pretest passed
   홀수가 안되는 이유는 홀짝 비교하면 됨. 무조건 홀+홀 / 짝+짝 조합이 나와서 합이 홀수가 될 수 없다.

Source code

#include <iostream>
#include <cmath>
using namespace std;

int t, n, i, j;

// 아래 함수로 완탐했는데 지워도 됨
/* 
void find() {
    int i, j;
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            if (j*pow(i,j)+i*pow(j,i)==n) {
                cout << i << ' ' << j << '\n';
                return;
            }
    cout << -1 << '\n';
}
*/

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        if (n % 2 == 0)
            cout << 1 << ' ' << n/2 << '\n';
        else
            cout << -1 << '\n';
    }
}

---

B Number factorization

개요

00:39:20
자연수 n의 서로 다른 소수로 곱해진 인수의 합의 최댓값 구하기

접근

1. 곱의 합이 최대가 되려면 곱한 값이 최대가 되어야 함.
2. 3*3 = 9 > 3+3 = 6 과 같이 곱할수록 무조건 커지니까
3. 최대 곱값을 구하기 위해 소수 구하고 나누어 줌. 만약 수가 남으면 sqrt(N)보다 큰 소수이므로 최댓값에 곱해줌

Pseudo code

// 에라토스테네스의 체로 먼저 소수 구해주고 감
// 범위는 2 ~ sqrt(10^9) ~= 34000
while (n)
    v = 2부터 소수전체로 나눠보면서 구한 서로다른 인수의 곱
    n /= v
    vector.push(v);
if (n이 남았으면)
    vector[최댓값] *= n
answer = vector 원소들의 합;

Source code

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define N 34000
using namespace std;

int t, n, i, j, r, v, ch, tc;
int c[N], s, p[N];
vector <int> st, qq;

int main() {
    for (i=2; i<N; i++)
        if (!p[i]) {
            st.push_back(i);
            for (j=i*i; j<N; j+=i)
                p[j] = 1;
        }
    cin >> t;
    while (t--) {
        qq.clear();
        cin >> n;
        s = 0, ch = 0;
        while (1 < n && !ch) {
            v = 1, ch = 1;
            for (i=0; i<st.size(); i++) {
                if (n%(v*st[i]) == 0)
                    v*=st[i], ch = 0;
            }
            qq.push_back(v);
            n /= v;
        }
        if (1 < n)
            qq[max_element(qq.begin(),qq.end())-qq.begin()] *= n;
        for (i=0; i<qq.size(); i++)
            if (1 < qq[i])
                s += qq[i];
        cout << s << '\n';
    }
}

---

C Remove the Bracket

개요

WA
a1x2+y2x3 + ... + y(n-2)x(n-1)+y(n-1)a(n)를 최소로 만드는 1~a[i] 범위의 (x,y)를 고르기 (단, x,y는 둘 다 s보다 작거나 둘다 크다)

접근

1. 처음엔 y = a-x로 두고 전개해서 푸는 문제인 줄 알았고, x의 선택지가 a[i]만큼 존재하므로 완탐을 하면 O(N^2) 이상이 걸리므로 안됨. 그리디하게 선택해야 함

2. 선택 방법 = 최대와 최소를 배치

   y[i-1] × x[i] + y[i] × x[i+1]와 y[i-1] × (x[i]+1) + (y[i]-1) × x[i+1]의 대소 관계는 항상 선형 단조증가 / 감소
   따라서 (x,y) = (min(a[i],s),a[i]-min(a[i],s))
   만약 a[i] < s이면 (x,y) = (0,a[i])
   아니면 (x,y) = (s, a[i]-s) (a[i]>2s이면 s가 최소, 아니면 a[i]-s가 최소)
   결국 (최대, 최소)로 나눌 수 있다.

3. 실수한 부분
   선택 후 x[i],y[i]의 순서를 바꾸는 것이 더 작으면 swap하는 식으로 그리디하게 진행하였는데, 모든 경우가 다 탐색되지 않았던 것 같음.
   DP로 작은 값이 오른쪽 / 왼쪽에 온 경우에 따라 최솟값을 업데이트 하면 해결할 수 있었음.

Pseudo code

for (모든 원소)
    (x,y) = (min(a[i], s), a[i]-x)
for (모든 원소)
    left = n-1번째에 왼쪽이 먼저 오는 경우
    right = n-1번째에 오른쪽이 먼저 오는 경우
    // 왼쪽이 먼저 올 경우 더해줄 값
    add_left = (n-1번째 오른쪽값) * 왼쪽값
    // 오른쪽이 먼저 올 경우 더해줄 값
    add_right = (n-1번째 왼쪽값) * 왼쪽값
    dp[n][0] = n번째에왼쪽이먼저 = min(left+add_left, right+add_right)

    add_left = (n-1번째 오른쪽값) * 오른쪽값
    add_right = (n-1번째 왼쪽값) * 오른쪽값
    dp[n][1] = n번째에오른쪽이먼저 = min(left+add_left, right+add_right)

Source code

// WA
#include <iostream>
#define N 200010
using namespace std;

typedef long long ld;
ld t, n, s, i, d1, d2;
ld a[N], x[N], y[N], ans;

void swap(ld *a, ld *b) {
    ld t = *a;
    *a = *b, *b = t;
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> s;
        for (i=1; i<=n; i++)
            cin >> a[i];
        ans = 0;
        y[1] = a[1], x[n] = a[n];
        for (i=2; i<n; i++) {
            if (a[i] <= s)
                y[i] = 0, x[i] = a[i];
            else
                y[i] = s, x[i] = a[i]-s;
        }
        for (i=2; i<n; i++) {
            if (y[i-1]*y[i]+x[i]*x[i+1] < y[i-1]*x[i]+y[i]*x[i+1])
                swap(x+i, y+i);
        }
        for (i=2; i<=n; i++)
            ans += y[i-1]*x[i];
        cout << ans << '\n';
    }
}

//up solving
#include <iostream>
#include <array>
#include <vector>
#define N 200010
using namespace std;

using ld = long long;
using xy = array<ld,2>;

int t, n, s, i, j, x;

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> s;
        vector <xy> a(n), dp(n+1);
        for (i=0; i<n; i++) {
            cin >> x;
            a[i] = {x-min(x,s),min(x,s)};
        }
        dp[1][0] = (a[0][0]+a[0][1])*a[1][0];
        dp[1][1] = (a[0][0]+a[0][1])*a[1][1];
        for (i=2; i<n; i++)
            for (j=0; j<2; j++)
                dp[i][j] = min(dp[i-1][0]+a[i-1][1]*a[i][j],dp[i-1][1]+a[i-1][0]*a[i][j]);
        dp[n-1][0] = dp[n-2][0]+a[n-2][1]*(a[n-1][0]+a[n-1][1]);
        dp[n-1][1] = dp[n-2][1]+a[n-2][0]*(a[n-1][0]+a[n-1][1]);
        cout << min(dp[n-1][0],dp[n-1][1]) << '\n';
    }
}