ABC 285

가장 성적이 좋았던 대회입니다. 앞으로 코드포스 혹은 앳코더를 할 때 복습 및 업솔빙 겸 풀이를 여기다 적겠습니다. 성적은 다음과 같습니다.

 

Score

 

최종 랭킹과 Performance는 다음과 같습니다.

 

Performance

 

A. Edge Checker 2

그림에서 직관적으로 보이듯이, 노드 N의 자식 l, r는 각각 N * 2, N * 2 + 1 입니다.

 

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
 
int A, B;
 
signed main() {
 
    cin >> A >> B;
    if (B == A * 2 || B == A * 2 + 1) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

 

B. Longest Uncommon Prefix

문제의 x와 i의 범위는 5,000 이하이기 때문에, 브루트 포스 방법을 사용해서 풀 수 있습니다.

 

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
 
int N; string S;
 
signed main() {
 
    cin >> N >> S;
    for (int i = 1; i <= N - 1; i++) {
 
        int maxi = 0;
        for (int j = 1; j <= N - i; j++) {
            if (S[j - 1] == S[j + i - 1]) break;
            maxi++;
        }
 
        cout << maxi << '\n';
    }
}

 

C. abc285_brutmhyhiizp

우리는 주어지는 알파벳 배열을 26진수로 생각할 수 있습니다. 입력받는 문자열 배열 S에서 A를 1로 두고, B를 2로 두고, ... Z를 26으로 둔다면 답은 다음과 같습니다.

 

• S[1] + S[2] * 26 + S[3] * 26 * 26 + S[4] * 26 * 26 * 26 + ...

 

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
 
string S;
int _26Jinsu[17];
 
signed main() {
 
    cin >> S;
    for (int i = 0; i < S.size(); i++) {
        _26Jinsu[i + 1] = S[i] - 65 + 1;
    }
 
    int pow26 = 1, ans = 0;
    for (int i = S.size(); i >= 1; i--) {
        ans += _26Jinsu[i] * pow26;
        pow26 *= 26;
    }
 
    cout << ans << '\n';
}

 

D. Change Usernames

문제에서 입력받는 S와 T의 개수의 합은 200,000을 넘지 않습니다. 우리는 문자열 그대로 처리하기 힘드니 각 문자열에 숫자를 하나 배당할 수 있습니다. 그 후 우리는 Si -> Ti 의 링크 그래프를 만듭시다. 예를 들어 예제 3의 그래프 모형은 다음과 같습니다.

 

Figure: Example 3

 

우리는 이렇게 하여 만들어진 그래프에 사이클이 있는지 검사하여 문제를 해결할 수 있습니다. 각 문자열에 노드 번호를 매기는 작업은 map을 통하여 빠르게 수행할 수 있습니다.

 

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
#define MAXN 300000
 
int N, cnt = 1;
map<string, int> m;
int link[MAXN], discovered[MAXN], node_order, cycle;
bool finished[MAXN];
 
void dfs(int node)
{
    discovered[node] = node_order++;
 
    int nxt = link[node];
    if (link[node] == 0) return;
 
    if (discovered[nxt] == -1)
        dfs(nxt);
    else if (!finished[nxt])
        ++cycle;
 
    finished[node] = true;
}
 
signed main() {
 
    cin >> N;
    for (int i = 1; i <= N; i++) {
        string from, to; cin >> from >> to;
        auto fnode = m.find(from), tnode = m.find(to);
        
        int f, t;
        if (fnode == m.end()) { f = cnt; m.insert({ from, cnt }); cnt++; }
        else f = fnode->second;
        if (tnode == m.end()) { t = cnt; m.insert({ to, cnt }); cnt++; }
        else t = tnode->second;
        link[f] = t;
 
    }
 
    for (int i = 0; i <= cnt; i++) discovered[i] = -1;
    for (int i = 1; i <= cnt; i++) {
        if (!finished[i]) dfs(i);
    }
 
    if (cycle == 0) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

 

E. Work or Rest

이 문제를 풀 때 필요한 포인트는 두 가지입니다.

 

1. 첫번째 설치되는 Holiday는 어디에 설치가 되든지 상관이 없습니다. 따라서 그냥 Day 1에 놓는다고 가정합시다.
2. Holiday i와 그 다음 Holiday = Holiday j로 갈 때, 문제에서 요구하는 min(x, y)는 1부터 (j - i) / 2 까지 차츰 증가하는 형태를 가집니다.

 

이 두 가지 특성을 착안하여 dp로 문제를 풀 수 있습니다.

 

• dp[x] = 현재 Day를 Holiday로 만들 때, Day 1~Day x까지의 maximum productivity

 

답은 max(dp[N], dp[N + 1]) 입니다. dp 테이블을 Naive하게 채우면 O(N^3) 이지만 누적 합을 이용한다면 O(N^2)만에 처리할 수 있습니다.

 

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
 
int N, A[5001], dp[10001], psum[5001];
 
signed main() {
 
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
 
    psum[0] = 0;
    psum[1] = A[1];
    for (int i = 2; i <= N; i++) psum[i] = A[i] + psum[i - 1];
 
    dp[1] = 0;
    for (int i = 2; i <= N + 1; i++) {
        for (int j = 1; i - j >= 1; j++) {
 
            int oldis = j / 2;
 
            int x = psum[oldis] * 2; // Base case
            if (j % 2 == 0) {
                x -= A[oldis];
            }
 
            //cout << "i: " << i << ", j: " << j << ", x: " << x << '\n';
            dp[i] = max(dp[i], x + dp[i - j]);
        }
 
    }
 
    cout << max(dp[N], dp[N + 1]) << '\n';
}

 

Comment

나머지 F, G, Ex 문제는 Skill Issue 때문에 풀지 못했습니다. GG.

 

 

Contact

Discord: Dis33#7936