CodeTON Round 1 (Div. 1 + Div. 2)

이번에 CodeTON Round 1에서 5솔, 308등으로 레드퍼포를 띄웠습니다.

처음에는 A와 C에서 1번씩 틀려서 망했다고 생각했지만, D와 E에서 생각보다 빠르게 답을 찾아서 운 좋게 잘 볼 수 있었던 것 같습니다. 아무래도 Div.1+Div.2다 보니 퍼포가 높게 찍히기도 했네요.

 

아래는 풀이입니다.

 

 

A. Good Pairs

일반성을 잃지 않고 $a_i\leq a_j$라 하면, 수식을 분석했을 때 $a_i\leq a_k \leq a_j$가 수식이 성립할 필요충분조건임을 쉽게 알 수 있습니다. 따라서 배열 중 최댓값과 최솟값의 인덱스를 고르면 됩니다.

(정렬해도 되는 문젠데 이렇게 풀어서 시간도 뺏기고 한 번 틀렸습니다.)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100001];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int n, p=-1e9, q=2e9, idx1=0, idx2=1;
        cin >> n;
        for(int i=0; i<n; i++) {
            cin >> a[i];
            if(a[i]>p) {
                p=a[i];
                idx1=i;
            }
            if(a[i]<q) {
                q=a[i];
                idx2=i;
            }
        }
        cout << idx1+1 << " " << idx2+1 << "\n";
    }
}

 

B. Subtract Operation

임의의 순서에 대해 마지막으로 남는 수는 마지막 두 수가 처음에 몇이었는지에만 의존합니다. 따라서 $a_j-a_i=k$인 서로 다른 $i, j$가 존재하면 답이 YES이며, 그런 쌍이 없다면 NO입니다.

투 포인터로 풀어도 상관없지만, 저는 이분탐색으로 풀었습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, a[200001];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        cin >> n >> k;
        for(int i=0; i<n; i++) cin >> a[i];
        sort(a, a+n);
        bool b=0;
        for(int i=0; i<n; i++) {
            int p=upper_bound(a, a+n, a[i]-k)-lower_bound(a, a+n, a[i]-k);
            if(p) {b=1;break;}
        }
        if(b) cout << "YES\n";
        else cout << "NO\n";
    }
}

 

C. Make Equal With Mod

모든 수가 2 이상이라면 가장 큰 원소부터 작은 원소까지 차례대로 $x$로 설정해서 나머지를 구하면 전체가 0으로 맞춰집니다.

0이 포함되어 있다면, 1이 있지 않는 이상 위의 로직대로 할 수 있고, 1이 포함되면 답이 NO가 됩니다.

1이 포함되어 있다면, 전체를 모두 1로 맞춰주어야 하기 때문에 연속된 수가 없다면 $a_i$를 $a_i-1$로 나눈 나머지를 구함으로써 전체를 1로 동일하게 변화시킬 수 있습니다. 연속된 수가 있다면, $a_i$와 $a_i-1$은 동시에 1이 될 수 없기 때문에 답이 NO가 됩니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a[100001];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        int cnt=0, z=0, two=0;
        for(int i=0; i<n; i++) {
            cin >> a[i];
            if(a[i]==1) cnt++;
            if(a[i]==0) z++;
            if(a[i]==2) two++;
        }
        if(!cnt && !z) {
            cout << "YES\n";
            continue;
        }
        if(z) {
            if(cnt) cout << "NO\n";
            else cout << "YES\n";
            continue;
        }
        sort(a, a+n);
        bool b=0;
        for(int i=0; i<n-1; i++) if(a[i]+1==a[i+1]) b=1;
        if(b) cout << "NO\n";
        else cout << "YES\n";
    }
}

 

D. K-good

수학문제이기는 하지만 꽤나 좋은 문제라고 생각합니다.

수 $n$에 대해 $k$인 해가 있기 위해서는, $n\equiv 0+1+\cdots+(k-1)\equiv \cfrac{k(k-1)}{2}\ (\mathrm{mod}\ k)$이며, $n\geq \cfrac{k(k+1)}{2}$를 만족해야 합니다.

주어지는 수 $n$이 홀수라면 2가 해에 포함됩니다.

$n$이 짝수일 때의 해만 구하면 됩니다.

임의의 자연수 $X$, 어떤 음이 아닌 정수 $t,\ p$에 대해, $X=2^tp\ (p$는 홀수$)$로 나타낼 수 있습니다.

$n=2^tp\ (p$는 홀수$)$라 설정합니다.

$p\geq 2^{t+1}+1$인 경우, $k=2^(t+1)$일 때 위 조건을 만족하므로 답은 무조건 YES가 됩니다.

$1<p\leq 2^{t+1}$인 경우, $k=p$일 때 위 조건을 만족하므로 답은 YES가 됩니다.

$p=1$일 때는 불가능함을 보일 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        ll p=1;
        while(n%p==0) p*=2;
        p/=2;
        ll q=n/p;
        if(p==1) {
            cout << "2\n";
            continue;
        }
        if(q==1) {
            cout << "-1\n";
            continue;
        }
        if(q<=p*2) cout << q << "\n";
        else cout << p*2 << "\n";
    }
}

 

E. Equal Tree Sums

이 문제가 굉장히 참신했습니다.

먼저, 트리를 인접하는 노드들이 같은 색을 가지지 않도록 흰색과 검은색으로 컬러링합니다. 그 후, 흰색 노드는 $\mathrm{deg}$, 검은색 노드는 $-\mathrm{deg}$로 설정합니다. 이렇게 하면 흰색 노드를 없앴을 때는 모든 서브트리의 수가 $1$로, 검은색 노드를 없앴을 때는 모든 서브트리의 수가 $-1$로 됨을 귀납적으로 보일 수 있습니다.

 

저는 처음 구현할 때는 약간 다르게 했습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, ans[100001], b[100001];
bool visited[100001];
vector<int> adj[100001];
void dfs1(int x) {
    visited[x]=1;
    for(auto i: adj[x]) if(!visited[i]) {
        b[i]=-b[x];
        dfs1(i);
    }
}
void dfs2(int x) {
    visited[x]=1;
    for(auto i: adj[x]) if(!visited[i]) {
        dfs2(i);
        ans[x]+=b[i];
    }
    ans[x]=b[x]-ans[x];
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        for(int i=0; i<=n; i++) adj[i].clear();
        memset(b, 0, sizeof(b));
        memset(ans, 0, sizeof(ans));
        memset(visited, 0, sizeof(visited));
        for(int i=0; i<n-1; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        b[1]=1;
        dfs1(1);
        memset(visited, 0, sizeof(visited));
        dfs2(1);
        ans[1]--;
        for(int i=1; i<=n; i++) cout << ans[i] << " ";
        cout << "\n";
    }
}