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