티스토리 뷰
이번 앳코더 ARC에서 6문제를 다 풀어 전체 5등, Rated 중 1등을 하였습니다. 간단한 후기와 문제 풀이를 해볼까 합니다.
A. 2nd Greatest Distance
구현과 케이스처리가 매우 복잡한, 400점짜리 문제 치고는 어려운 문제입니다. 다만 아래와 같은 관찰을 통해 구현을 편리하게 줄일 수 있습니다.
각 정점을 x좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점과,
y좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점만이 필요하다.
만약 2번째로 긴 체비셰프 거리가 위 정점들로 이루어지지 않는다면, 두 양끝점 중 하나를 위에서 뽑아낸 (최대 8개의) 점들로 대체했을 때 더 긴 해를 얻을 수 있음이 보장되기 때문입니다. 따라서 위와 같이 8개의 점의 후보를 얻어내고, 나이브하게 2번째로 긴 거리를 찾아 출력하면 됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dat{
int x, y, idx;
dat(){}
dat(int x, int y, int idx): x(x), y(y), idx(idx){}
};
int n;
dat arr[200002];
dat arr2[200002];
bool chk[200002];
vector<int> vec;
vector<int> dvec;
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d %d", &arr[i].x, &arr[i].y);
arr[i].idx = i;
}
for(int i=1; i<=n; i++) arr2[i] = arr[i];
sort(arr2+1, arr2+n+1, [&](dat &a, dat &b){
return a.x<b.x;
});
for(int i=1; i<=2; i++) chk[arr2[i].idx] = 1, chk[arr2[n+1-i].idx] = 1;
for(int i=1; i<=n; i++){
arr2[i] = arr[i];
}
sort(arr2+1, arr2+n+1, [&](dat &a, dat &b){
return a.y<b.y;
});
for(int i=1; i<=2; i++) chk[arr2[i].idx] = 1, chk[arr2[n+1-i].idx] = 1;
for(int i=1; i<=n; i++){
if(chk[i]) vec.push_back(i);
}
for(int i=0; i<(int)vec.size(); i++){
for(int j=i+1; j<(int)vec.size(); j++){
dvec.push_back(max(abs(arr[vec[i]].x - arr[vec[j]].x), abs(arr[vec[i]].y - arr[vec[j]].y)));
}
}
sort(dvec.rbegin(), dvec.rend());
printf("%d", dvec[1]);
}
B. RGB Matching
빨간 강아지의 수를 $r$, 초록 강아지의 수를 $g$, 파란 강아지의 수를 $b$로 두면, 이 셋의 홀짝성에 따라 일반성을 잃지 않고 케이스를 두 가지로 나눌 수 있습니다.
- $r$, $g$, $b$가 모두 짝수인 경우
- 같은 색의 강아지끼리만 항상 매칭을 시켜줄 수 있고, 이때의 답이 0입니다. 따라서 최적해는 항상 0입니다.
- $r$은 짝수, $g$와 $b$가 홀수인 경우
- 아래와 같은 두 가지 해 중 하나가 최적해임이 보장됩니다. (다른 방법이 존재한다면, 항상 답이 더 작거나 같은 해를 찾아줄 수 있습니다.)
- Case 1) 초록색(G) 강아지와 파란색(B) 강아지 한 마리씩을 잇고(G-B), 나머지는 같은 색 강아지끼리 잇는다.
- Case 2) 빨간색 강아지 두 마리(RR)를 각각 초록색(G), 파란색(B) 강아지 한 마리와 잇고(R-G, R-B), 나머지를 같은 색 강아지끼리 잇는다.
- Case 1의 경우 초록색과 파란색 강아지의 $a_i$를 모두 정렬해 두고, 가장 가까운 두 수를 찾아주면 되는데 이는 이분 탐색이나 투 포인터를 이용하면 풀 수 있습니다.
- Case 2의 경우 모든 초록색 / 파란색 강아지 각각에 대해 가장 $a_i$가 가까운 빨간색 강아지까지의 $a_i$의 차이를 구한 뒤, 이 둘을 더하면 됩니다. 이 두 강아지가 겹치는 경우에는 어떻게 하냐고 생각하실 수 있는데, 이 경우 아래와 같은 두 가지 경우가 있습니다. 둘 모두 초록색 강아지와 파란색 강아지를 직접 이어주는 더 작거나 같은 해가 존재하기 때문에 상관없습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<ll> R, G, B;
ll ans = LLONG_MAX;
int main(){
scanf("%d", &n);
for(int i=1; i<=n*2; i++){
ll x; char c;
scanf("%lld %c", &x, &c);
if(c=='R') R.push_back(x);
if(c=='G') G.push_back(x);
if(c=='B') B.push_back(x);
}
if(R.size() % 2 == 0 && G.size() % 2 == 0 && B.size() % 2 == 0){
printf("0\n");
return 0;
}
if(G.size() % 2 == 0) R.swap(G);
if(B.size() % 2 == 0) R.swap(B);
sort(R.begin(), R.end());
sort(G.begin(), G.end());
sort(B.begin(), B.end());
for(auto x: G){
auto it = lower_bound(B.begin(), B.end(), x);
if(it != B.end()) ans = min(ans, *it - x);
if(it != B.begin()) ans = min(ans, x - *prev(it));
}
ll gMin = 1e18, bMin = 1e18;
for(auto x: G){
auto it = lower_bound(R.begin(), R.end(), x);
if(it != R.end()) gMin = min(gMin, *it - x);
if(it != R.begin()) gMin = min(gMin, x - *prev(it));
}
for(auto x: B){
auto it = lower_bound(R.begin(), R.end(), x);
if(it != R.end()) bMin = min(bMin, *it - x);
if(it != R.begin()) bMin = min(bMin, x - *prev(it));
}
ans = min(ans, gMin + bMin);
printf("%lld", ans);
}
C. Odd Even Sort
정렬에서 swap할 수 있는 횟수가 매우 널널하기 때문에 별 생각 없이 구현해도 정답이 나옵니다. 저와 같은 경우는 아직 제자리에 있지 않은 가장 작은 수 $x$를 찾은 뒤, $x$와 그 왼쪽 수를 지금 교환할 수 있으면 교환하고, 아니라면 교환할 수 있는 쌍 중에서 교환하기 가장 적합한 것을 교환했습니다. 만약 $a_{i} > a_{i+1}$이고 현재 교환할 수 있는 $(i, i+1)$ 쌍이 있다면 교환하고, 아니라면 교환할 수 있는 최대한 오른쪽에 있는 쌍을 교환합니다. 자세한 풀이는 코드를 참조하시기 바랍니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int n;
int arr[502];
int main(){
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
}
vector<int> ans;
int odd = 1;
while(1){
int tmp = -1;
for(int i=1; i<=n; i++){
if(arr[i] != i){
tmp = i;
break;
}
}
if(tmp == -1) break;
for(int i=1; i<=n; i++){
if(arr[i] == tmp){
tmp = i;
break;
}
}
if((tmp-1 + odd) % 2 == 0){
ans.push_back(tmp-1);
swap(arr[tmp-1], arr[tmp]);
}
else{
bool swapped = 0;
for(int i=n-1; i>=1; i--){
if(arr[i] > arr[i+1] && (i+odd) % 2 == 0){
swapped = 1;
ans.push_back(i);
swap(arr[i], arr[i+1]);
break;
}
}
if(!swapped){
if((n-1 + odd) % 2 == 0){
ans.push_back(n-1);
swap(arr[n-1], arr[n]);
}
else{
ans.push_back(n-2);
swap(arr[n-2], arr[n-1]);
}
}
}
odd = !odd;
}
printf("%d\n", (int)ans.size());
for(auto x: ans) printf("%d ", x);
puts("");
}
}
D. 1 or 2
풀이가 틀렸는데 데이터가 약해서 맞은 것 같습니다. 정해는 아래와 같은 관찰이 필요합니다.
- 사탕 하나를 혼자 먹는 것은 맛이 0인 사탕과 함께 먹는 것과 정확히 동치이다.
따라서 사전에 맛이 0인 사탕 몇 개를 추가해 준 뒤, 매 순간별로 가장 맛이 좋은 사탕과 나쁜 사탕을 먹는 것을 반복해 주면 $O(N^2)$ 풀이가 완성됩니다.
최적해는 아래와 같은 종류라는 것을 관찰할 수 있습니다.
Step 1. 혼자 먹을 사탕의 집합을 위에서부터 $x$개 고르거나, 아래에서부터 $x$개 고른다. ($0 \le x \le N$)Step 2. 아래의 작업을 $c$번 시행한다. (단, $0 \le 2c \le N-x$)남아 있는 가장 맛이 좋은 / 나쁜 사탕을 확인한 뒤, 그 둘을 한 번에 먹는다.
Step 3. 남은 사탕은 모두 따로 먹는다.
Step 1로 가능한 $O(N)$ 가지 경우를 모두 시험해 보며, 남은 사탕들에 Step 2를 한 번씩 적용해 가며 지금 현재 Step 3으로 넘어갔을 때 나오는 해들 중 최적해를 모두 구해 주면 $O(N^2)$에 문제를 풀 수 있습니다. 역시 구현이 간단하니 코드를 참고하시기 바랍니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll arr[5002];
ll ans = LLONG_MAX;
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%lld", &arr[i]);
}
sort(arr+1, arr+n+1);
for(int i=n; i>=1; i--){
ll tMax = LLONG_MIN, tMin = LLONG_MAX;
for(int j=i+1; j<=n; j++){
tMax = max(tMax, arr[j]);
tMin = min(tMin, arr[j]);
}
for(int a=1, b=i; a<=b; a++, b--){
ans = min(ans, max(tMax, arr[b]) - min(tMin, arr[a]));
ll weight = a==b ? arr[a] : arr[a] + arr[b];
tMax = max(tMax, weight);
tMin = min(tMin, weight);
}
ans = min(ans, tMax - tMin);
}
for(int i=1; i<=n; i++){
ll tMax = LLONG_MIN, tMin = LLONG_MAX;
for(int j=1; j<i; j++){
tMax = max(tMax, arr[j]);
tMin = min(tMin, arr[j]);
}
for(int a=i, b=n; a<=b; a++, b--){
ans = min(ans, max(tMax, arr[b]) - min(tMin, arr[a]));
ll weight = a==b ? arr[a] : arr[a] + arr[b];
tMax = max(tMax, weight);
tMin = min(tMin, weight);
}
ans = min(ans, tMax - tMin);
}
printf("%lld", ans);
}
E. Directed Tree
$DP[i][j]$: $i$번 정점을 루트로 가지는 서브트리의 정점 중 $j$개에서 자신의 자식을 고를 때, 겹치지 않게 고르는 방법의 수로 정의합시다. 이때 크기가 $A$와 $B$인 두 서브트리의 결과를 $O(AB)$에 합칠 수 있으므로, DP 배열을 $O(N^2)$에 얻어낼 수 있습니다. (KOI 2019 검은 돌 참고)
포함과 배제의 원리를 이용하면 답은 $\sum_{i=0}^{n} (-1)^i (n-i)! \times DP[0][i]$로 구할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
ll mpow(ll x, ll y){
if(!y) return 1;
if(y&1) return mpow(x, y-1) * x % MOD;
ll tmp = mpow(x, y/2);
return tmp * tmp % MOD;
}
int n;
int par[2002];
vector<int> link[2002];
ll fact[2002], factInv[2002];
ll DP[2002][2002];
ll tmpDP[2002];
int sz[2002];
ll ans;
void dfs(int x, int par = -1){
DP[x][0] = 1;
for(auto y: link[x]){
dfs(y, x);
int xL = sz[x], yL = sz[y];
for(int i=0; i<=xL+yL; i++){
tmpDP[i] = 0;
}
for(int i=0; i<=xL; i++){
for(int j=0; j<=yL; j++){
tmpDP[i+j] = (tmpDP[i+j] + DP[x][i] * DP[y][j]) % MOD;
}
}
for(int i=0; i<=xL+yL; i++){
DP[x][i] = tmpDP[i];
}
sz[x] += sz[y];
}
for(int i=sz[x]; i>=0; i--){
DP[x][i+1] += DP[x][i] * (sz[x] - i) % MOD;
DP[x][i+1] %= MOD;
}
sz[x]++;
}
int main(){
fact[0] = 1;
for(int i=1; i<=2000; i++) fact[i] = fact[i-1] * i % MOD;
factInv[2000] = mpow(fact[2000], MOD-2);
for(int i=1999; i>=0; i--) factInv[i] = factInv[i+1] * (i+1) % MOD;
scanf("%d", &n);
for(int i=2; i<=n; i++){
scanf("%d", &par[i]);
link[par[i]].push_back(i);
}
dfs(1);
int sign = 1;
for(int i=0; i<=n; i++){
ans += DP[1][i] * fact[n-i] % MOD * sign;
ans = (ans + MOD) % MOD;
sign *= -1;
}
printf("%lld", ans);
}
F. Logical Operations on Tree
모든 정점과 간선에 0/1이나 OR/AND를 쓴 상태이고, 여기서 1을 만들 수 있는 지 생각해 봅시다. AND가 쓰여 있는 간선의 경우 양쪽 모두 1이어야 1이 되므로, 1을 만들기가 쉽지 않습니다. 따라서 1을 만들 여지를 남겨 두기 위해서는 먼저 AND가 쓰여 있는 간선부터 모두 합쳐준 후 OR 간선을 합쳐 주는 것이 이득일 것입니다.
어떤 배치에서 "1을 만들 수 있다"의 반대는 "0밖에 만들 수 없다"입니다. 0밖에 만들 수 없는 배치는 모든 AND 게이트로 연결된 컴포넌트에 0이 적어도 하나 쓰여 있는 경우입니다.
아래와 같이 DP 식을 정의합시다.
$DP[i][0]$: 현재 $i$번 노드가 연결된 컴포넌트에 0이 하나도 쓰여 있지 않은 경우
$DP[i][1]$: 현재 $i$번 노드가 연결된 컴포넌트에 0이 하나라도 쓰여 있는 경우
$DP[i][0]$을 구하기 위해서는 $i$번 노드와 자식 노드 $c$가 무슨 게이트로 연결되어 있는지를 살펴봐야 합니다. 일단 $i$번 노드에는 무조건 1이 쓰여 있어야 하고, $i$번 노드와 AND 게이트로 연결된 노드의 경우 $DP[c][0]$을 (0이 쓰여 있지 않아야 하므로), OR 게이트로 연결된 노드의 경우 $DP[c][1]$을 (정점 $c$가 속한 연결 성분에는 0이 적어도 하나 있어야 하므로) 취해야 합니다. 따라서 $DP[i][0]$은 모든 자식 노드 $c$에 대해 $DP[c][0] + DP[c][1]$의 곱입니다.
$DP[i][1]$을 구하기 위해서는 $i$번 정점에 0이 쓰인 경우와 1이 쓰인 경우로 나눌 수 있습니다. 0이 쓰인 경우는 $i$번 정점과 $c$번 정점을 올바르게 연결만 하면 되는데, 이 둘이 AND 게이트로 연결된 경우 $DP[c][0] + DP[c][1]$가지 경우의 수가, OR 게이트로 연결된 경우 $DP[c][1]$가지 경우의 수가 존재하게 됩니다.
만약 $i$번 정점에 1이 쓰여 있다면 AND 게이트로 연결된 자식 노드 중 적어도 하나의 컴포넌트에 0이 쓰여 있어야 하는데, 이는 바로 윗 문단에서 구한 경우의 수에서 $DP[i][0]$을 빼서 구할 수 있습니다.
답은 $2^{2N-1} - DP[1][1]$이 됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
ll mpow(ll x, ll y){
if(!y) return 1;
if(y%2) return mpow(x, y-1) * x % MOD;
ll tmp = mpow(x, y/2);
return tmp * tmp % MOD;
}
int n;
vector<int> link[100002];
ll DP[100002][2];
void dfs(int x, int par = -1){
DP[x][0] = 1;
ll case1_0 = 1, case1_1 = 1;
for(auto y: link[x]){
if(y == par) continue;
dfs(y, x);
DP[x][0] *= (DP[y][0] /* AND 할 경우 안 만들어진 것*/ + DP[y][1] /* OR 할 경우 만들어진 것 */) % MOD;
DP[x][0] %= MOD;
case1_1 *= (DP[y][0] + DP[y][1] + DP[y][1]) % MOD;
case1_1 %= MOD;
case1_0 *= (DP[y][0] + DP[y][1] + DP[y][1]) % MOD;
case1_0 %= MOD;
}
case1_0 = (case1_0 - DP[x][0] + MOD) % MOD;
DP[x][1] = (case1_0 + case1_1) % MOD;
}
int main(){
scanf("%d", &n);
for(int i=1; i<n; i++){
int x, y;
scanf("%d %d", &x, &y);
link[x].push_back(y);
link[y].push_back(x);
}
dfs(1);
ll ans = (mpow(2, 2*n-1) + MOD - DP[1][1]) % MOD;
printf("%lld", ans);
}