-
NYPC 2021 예선 풀이 및 후기일기장 2021. 8. 26. 22:33
NYPC 2021 예선이 종료되었습니다. 작년에 비해 문제 퀄이 많이 떨어진 것 같아서 개인적으로 좀 아쉬웠습니다. 문제마다 그냥 처음 떠오른 풀이를 바로 짜다보니 세그먼트 트리를 이용한 풀이가 좀 많습니다. 다른 쉬운 풀이가 있을 수 있으니 다른 블로그 풀이도 참고하면서 보면 좋을 것 같습니다.
1일차 1번) 계단
문제 요약
1층부터 $M$층까지 있는 건물의 $F$층에서 시작해서, 계단을 한 층 오르는 것을 $N$번하려고 할 때 엘리베이터를 타는 횟수의 최솟값을 구하는 문제입니다.
풀이
더보기$M$층까지 올라간 후, 엘리베이터를 타고 1층으로 가는 것을 반복하는 것이 최적의 전략입니다. $M$, $N$이 크기 때문에 식을 세워서 풀면 $O(1)$에 답을 계산할 수 있습니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; int main(){ int a, b, c; scanf("%d %d %d", &a, &b, &c); printf("%d\n", (c+a-2)/(a-1)); return 0; }1일차 2번) 레이스 기록 검증
문제 요약
주어지는 로그 파일이 조건을 만족하는지를 묻는 문제입니다.
풀이
더보기문제에서 주어지는 조건을 그대로 확인하면 됩니다. 크기 $N$짜리 배열 $A$를 잡아놓고, $i$번 유저가 $t$초에 레이스를 시작하면 $A[i] = t$로 놓고, $i$번 유저가 레이스가 끝나면 $A[i]$값을 이용해서 조건을 확인한 후, $A[i]$값을 초기화시켜주면 됩니다. 시간복잡도는 $O(N+M)$입니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; int a[101]; int main(){ int n, m; scanf("%d %d", &n, &m); fill(a, a+n+1, -1); bool flag = 0; for (int i=0;i<m;i++){ int x, y, z; scanf("%d %d %d", &x, &y, &z); if (!z){ if (a[y]!=-1) flag = 1; a[y] = x; } else{ if (a[y]==-1 || x-a[y]<60) flag = 1; a[y] = -1; } } for (int i=1;i<=n;i++) if (a[i]!=-1) flag = 1; if (!flag) printf("YES\n"); else printf("NO\n"); return 0; }1일차 3번) 근무표 짜기
문제 요약
개발자 $N$명과 근무하는 날수 $K$가 주어지고, 각 개발자마다 최소 근무일수 $A[i]$와 각 날짜별로 근무할 수 있는 최대 사람 수 $B[j]$가 주어질 때, 근무표를 작성하는 문제입니다. (불가능한 입력은 주어지지 않습니다.)
풀이
더보기간단한 그리디 문제입니다. 1번째 개발자부터 차례대로 보면서, 근무할 수 있는 사람이 가장 많이 남아있는 상위 $A[i]$개의 날짜를 골라 그 날짜에 개발자를 넣어주면 됩니다. 우선순위 큐를 이용하면 간단하게 구현할 수 있고, 시간복잡도는 $O(N+K+\sum{A[i]}\log{K})$입니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; int a[101], b[101]; vector<int> ans[101]; int main(){ int n, k; scanf("%d %d", &n, &k); for (int i=0;i<n;i++) scanf("%d", a+i); priority_queue<pair<int, int>> pq; for (int i=0;i<k;i++){ scanf("%d", b+i); pq.emplace(b[i], i); } for (int i=0;i<n;i++){ vector<pair<int, int>> tmp; for (int j=0;j<a[i];j++){ ans[pq.top().second].push_back(i+1); tmp.push_back(pq.top()); tmp.back().first--; pq.pop(); } for (auto &p:tmp) pq.push(p); } for (int i=0;i<k;i++){ printf("%d ", (int)ans[i].size()); for (auto &x:ans[i]) printf("%d ", x); printf("\n"); } return 0; }1일차 4번) 파티
문제 요약
길이 $N$짜리 배열 $A$가 주어졌을 때, 임의의 $1\le i, j \le N$에 대해 $|A[i]-A[j]| \le 1$를 만족하도록 하기 위한 시행의 최소 횟수를 구하는 문제입니다.
시행: $1\le i, j \le N$인 $i$와 $j$를 골라 $A[i]$에서 1을 빼고, $A[j]$에 1을 더한다.
풀이
더보기$\sum{A[i]}$가 고정되어 있을 때, $|A[i]-A[j]| \le 1$를 만족하는 배열 $A$는 순서를 고려하지 않으면 유일합니다. ($x$가 $y$개, $x+1$이 $N-y$개 있는 형태)
또한, 최종 상태의 배열을 $B$라고 했을 때, $A$에서 $B$로 만들기 위한 최적의 전략은 각 수에 대해, 그 수에서 빼기만 반복하거나 더하기만 반복하는 것입니다. 따라서, 시행 횟수의 최솟값은 $\frac{1}{2} \sum{|A[i]-B[i]|}$입니다.
위 식의 값을 최소로 만드는 배열 $B$를 구하면 답이 되고, 이는 배열 $A$와 $B$를 모두 오름차순 정렬해주면 해결됩니다.
시간복잡도는 $O(N\log{N})$입니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; ll a[200200]; ll myabs(ll x){ if (x<0) return -x; return x; } int main(){ int n; scanf("%d", &n); ll s = 0; for (int i=0;i<n;i++){ scanf("%lld", a+i); s += a[i]; } sort(a, a+n, greater<ll>()); ll ans = 0; for (int i=0;i<n;i++){ if (i<s%n) ans += myabs(a[i]-s/n-1); else ans += myabs(a[i]-s/n); } printf("%lld\n", ans/2); return 0; }1일차 5번) 페인트 칠하기
문제 요약
아웃풋 온리 문제입니다.
특정 행이나 열에 특정 색을 칠하는 연산을 여러 번 반복하여 입력의 상태로 만드는 문제입니다.
항상 가능한 입력만 주어집니다.
풀이
더보기마지막에 칠한 행/열을 생각해보면, 그 행/열은 모두 같은 색입니다. 이 사실을 이용하여, 거꾸로 색이 모두 같은 행/열을 찾아준 후, 그 행/열을 지워주는 것을 반복하면 문제가 풀립니다. 행과 열의 개수는 $N+M$개이므로, 시행은 최대 $N+M$번 일어납니다. 색이 같은 행/열을 찾는건 $O(NM)$에 구현할 수 있으므로, 시간복잡도 $O(NM(N+M))$에 문제를 해결할 수 있습니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; struct node{ char x; int y, z; node(){} node(char _x, int _y, int _z): x(_x), y(_y), z(_z){} }; int a[101][101]; vector<node> ans; bool iszero(int n, int m){ for (int i=0;i<n;i++){ for (int j=0;j<m;j++) if (a[i][j]) return 0; } return 1; } void color(int n, int m){ for (int i=0;i<n;i++){ int cur = 0; for (int j=0;j<m;j++){ if (!cur && a[i][j]) cur = a[i][j]; else if (a[i][j] && cur!=a[i][j]) cur = -1; } if (cur>0){ ans.emplace_back('H', i+1, cur); for (int j=0;j<m;j++) a[i][j] = 0; return; } } for (int j=0;j<m;j++){ int cur = 0; for (int i=0;i<n;i++){ if (!cur && a[i][j]) cur = a[i][j]; else if (a[i][j] && cur!=a[i][j]) cur = -1; } if (cur>0){ ans.emplace_back('V', j+1, cur); for (int i=0;i<n;i++) a[i][j] = 0; return; } } exit(1); } int main(){ int n, m; scanf("%d %d", &n, &m); for (int i=0;i<n;i++){ for (int j=0;j<m;j++) scanf("%d", a[i]+j); } while(!iszero(n, m)) color(n, m); printf("%d\n", (int)ans.size()); reverse(ans.begin(), ans.end()); for (auto &x:ans) printf("%c %d %d\n", x.x, x.y, x.z); return 0; }2일차 1번) 폭탄 터트리기
문제 요약
길이 $N$짜리 배열 $A$와 정수 $K$가 주어졌을 때, 배열 $A$를 다음 조건을 만족하는 구간 $x$개로 나눠야 합니다.
조건: 구간의 원소의 최솟값과 최댓값의 차이가 $K$이하이다.
이때, $x$의 최솟값을 구하는 문제입니다.
(실제 문제와 내용이 약간 다르긴 한데 좀만 생각해보면 동치라는 것을 알 수 있습니다.)
풀이
더보기배열을 맨 앞부터 스위핑하면서, 최대한 구간의 길이가 길도록 그리디하게 구간을 나눠주면 문제가 해결됩니다. 증명은 어렵지 않으니 스스로 해보시는걸 추천드립니다.
시간복잡도는 $O(N)$입니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; int a[300300]; int main(){ int n, k; scanf("%d %d", &n, &k); int ans = 1, mn = 1e9, mx = -1e9; for (int i=0;i<n;i++){ scanf("%d", a+i); mn = min(mn, a[i]); mx = max(mx, a[i]); if (mx-mn>k) ans++, mn = mx = a[i]; } printf("%d\n", ans); return 0; }2일차 2번) 루트가 많은 트리?
문제 요약
$N$개의 정점이 있는 트리가 주어지고, 간선 중 몇 개의 방향이 고정되어 있습니다. 이때, 나머지 간선들의 방향을 적절히 정해줘서 임의의 정점 $w$에 대해 $v$에서 $w$로 가는 경로가 존재하도록 할 수 있는 정점 $v$의 개수를 구하는 문제입니다.
풀이
더보기1번 정점을 루트로 두고, 간선의 방향을 무시하고 dfs를 돌립시다. 정점 $x$에 대해, $x$와 $par[x]$($x$의 부모)를 있는 간선이 방향이 정해져 있다고 가정해봅시다.
1. 간선의 방향이 $x \rightarrow par[x]$일 경우
$x$의 서브트리 외부에서 $x$의 서브트리로 들어오는 경로가 없으므로, 문제의 조건을 만족하는 정점들의 집합은 $x$의 서브트리의 부분집합임을 알 수 있습니다.
2. 간선의 방향이 $par[x] \rightarrow x$일 경우
1과 동일한 논리를 적용하면, 문제의 조건을 만족하는 정점들의 집합은 $x$의 서브트리의 여집합의 부분집합임을 알 수 있습니다.
모든 간선에 대해 확인했을 때 1과 2에서 따진 조건을 모두 만족하는 정점의 개수가 답이 된다는 것을 알 수 있습니다.
저는 오일러 투어 트릭과 세그먼트 트리를 이용하여 이를 구현했습니다.
시간복잡도는 $O(N\log{N})$입니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; struct Seg{ int tree[600600], sz; void init(int n){sz = n;} void update(int l, int r, int x){ for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){ if (l&1) tree[l++] += x; if (r&1) tree[--r] += x; } } int query(int x){ int ret = tree[x+sz]; for (x+=sz;x>1;x>>=1) ret += tree[x>>1]; return ret; } }tree; vector<pair<int, int>> edge; vector<int> adj[300300]; int dfn[300300], out[300300], cnt = 1; void dfs(int s, int pa = -1){ dfn[s] = cnt++; for (auto &v:adj[s]) if (v!=pa) dfs(v, s); out[s] = cnt; } int main(){ int n; scanf("%d", &n); for (int i=0;i<n-1;i++){ int x, y, z; scanf("%d %d %d", &x, &y, &z); adj[x].push_back(y); adj[y].push_back(x); if (z) edge.emplace_back(x, y); } dfs(1); tree.init(n+1); for (auto &p:edge){ if (dfn[p.first]>dfn[p.second]){ tree.update(dfn[p.first], out[p.first], 1); } else{ tree.update(dfn[p.second], out[p.second], -1); tree.update(1, n+1, 1); } } int ans = 0; for (int i=1;i<=n;i++) if (tree.query(i)==(int)edge.size()) ans++; printf("%d\n", ans); return 0; }2일차 3번) 영역 나누기
문제 요약
원주 위에 $2N$개의 점들이 주어진 순서대로 놓여있을 때, 같은 번호를 이은 직선 $N$개로 분할된 원 내부의 영역의 최대 개수를 구하는 문제입니다.
풀이
더보기(최대 영역 개수) = (직선 개수) + (교점 개수) + 1이라는 공식이 잘 알려져 있습니다. 따라서, 교점의 개수만 세주면 됩니다. 선분 $i$의 끝점을 각각 $A[i]$, $B[i]$라고 할 때 (WLOG $A[i] \le B[i]$), 좌표평면 상에 $(A[i], B[i])$ 위치와 $(B[i], A[i])$ 위치에 점을 찍어주면, 선분 $i$와 교차하는 선분의 개수는 ($[A[i]+1, B[i]-1] \times [1, 2N]$위에 있는 점의 개수) - ($[A[i]+1, B[i]-1] \times [A[i]+1, B[i]-1]$위에 있는 점의 개수) 임을 알 수 있습니다.
위와 같은 2차원 쿼리는 PST나 오프라인 쿼리 + 세그먼트 트리를 이용하여 $O(N\log{N})$에 해결할 수 있음이 알려져 있습니다. PST는 상수가 커서 TLE를 당했고, 오프라인 쿼리 + 세그먼트 트리를 이용해서 100점을 받았습니다.
참고로 머지소트트리를 짜면 보통 $O(N\log^2N)$이지만, 아래 링크에 있는 트릭을 사용하면 $O(N\log{N})$에 풀 수도 있습니다. 제가 짜보지는 않아서 TLE를 안 당하는지는 잘 모르겠습니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; pair<int, int> a[500500]; int b[1001000]; struct Query{ int x, y; bool add; Query(){} Query(int _x, int _y, bool _add):x(_x), y(_y), add(_add){} }; struct Seg{ int tree[2002000], sz; void init(int n){sz = n;} void update(int x){ for (tree[x+=sz]++;x>1;x>>=1) tree[x>>1] = tree[x]+tree[x^1]; } int query(int l, int r){ int ret = 0; for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){ if (l&1) ret += tree[l++]; if (r&1) ret += tree[--r]; } return ret; } }tree; vector<Query> Q[1001000]; int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); int n; cin >> n; for (int i=1;i<=n*2;i++){ int tmp; cin >> tmp; if (a[tmp].first) a[tmp].second = i, b[a[tmp].first] = i, b[i] = a[tmp].first; else a[tmp].first = i; } ll ans = 0; tree.init(n*2+1); for (int i=1;i<=n;i++){ int l = a[i].first+1, r = a[i].second-1; Q[r].emplace_back(1, n*2+1, 1); Q[l-1].emplace_back(1, n*2+1, 0); Q[r].emplace_back(l, r+1, 0); Q[l-1].emplace_back(l, r+1, 1); } for (int i=1;i<=n*2;i++){ if (b[i]) tree.update(b[i]); for (auto &p:Q[i]){ if (p.add) ans += tree.query(p.x, p.y); else ans -= tree.query(p.x, p.y); } } cout << n+1+ans/2; return 0; }2일차 4번) K-좀비
문제 요약
아웃풋 온리 문제입니다.
출발점에서 시작해서 주기가 $K$인 좀비를 피해 도착점까지 가는 경로를 출력하는 문제입니다.
10만번 이하로 도착점에 도달하는 것이 가능함이 보장됩니다.
풀이
더보기간단한 bfs 문제입니다.
정점을 (시간, x좌표, y좌표)로 놓고 bfs를 돌리면 정점의 개수는 최대 $10^6 \times 25 \times 25$이고, 간선의 개수는 정점 개수의 4배 이하이므로 최악의 경우에도 1~2초내로 답을 구할 수 있습니다.
시간복잡도는 $O(NM \times ans)$입니다. ($ans$는 최단경로의 길이)
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; char a[27][27]; bool visited[100100][27][27]; int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; pair<int, pair<int, int>> pa[100100][27][27]; bool valid(int t, int x, int y){ for (int k=0;k<4;k++){ int nx = x+dx[k], ny = y+dy[k]; if (a[nx][ny]>='2' && a[nx][ny]<='9'){ int tmp = a[nx][ny] - '0'; if (t%tmp) return 0; } } return 1; } int main(){ int n, m; scanf("%d %d", &n, &m); fill(a[0], a[26]+27, '#'); for (int i=1;i<=n;i++){ scanf("%s", a[i]+1); a[i][m+1] = '#'; } queue<pair<int, pair<int, int>>> q; q.emplace(0, make_pair(1, 1)); visited[0][1][1] = 1; int t = 0; while(!q.empty()){ auto p = q.front(); q.pop(); int x = p.second.first, y = p.second.second; for (int k=0;k<4;k++){ int nx = x+dx[k], ny = y+dy[k]; if (a[nx][ny]=='#' || (a[nx][ny]>='2' && a[nx][ny]<='9')) continue; if (!valid(p.first+1, nx, ny)) continue; if (visited[p.first+1][nx][ny]) continue; visited[p.first+1][nx][ny] = 1; pa[p.first+1][nx][ny] = p; q.emplace(p.first+1, make_pair(nx, ny)); if (nx==n && ny==m){ t = p.first+1; break; } } if (t) break; } string ans; pair<int, pair<int, int>> cur = {t, make_pair(n, m)}; for (;cur.first;){ auto nxt = pa[cur.first][cur.second.first][cur.second.second]; if (nxt.second.first-cur.second.first==1) ans.push_back('U'); else if (nxt.second.first-cur.second.first==-1) ans.push_back('D'); else if (nxt.second.second-cur.second.second==1) ans.push_back('L'); else ans.push_back('R'); cur = nxt; } reverse(ans.begin(), ans.end()); cout << ans << '\n'; return 0; }3일차 1번) 다양성이 힘이다
문제 요약
길이 $N$짜리 배열 $A$와 정수 $K$가 주어졌을 때, 다음 식의 최댓값을 구해야 합니다.
$$\sum_{i, j \in [x, x+K-1]} {|A[i]-A[j]|}$$
풀이
더보기슬라이딩 윈도우로 길이가 $K$인 구간을 한 칸씩 이동해주면서 답을 갱신해주면 됩니다. 구간에서 원소를 빼거나 추가할 때 식의 값이 얼마나 변하는지는 세그먼트 트리를 이용하면 빠르게 계산할 수 있습니다.
시간복잡도는 $O(N\log{N})$입니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; struct Seg{ pair<ll, int> tree[400400]; int sz; pair<ll, int> combine(pair<ll, int> x, pair<ll, int> y){ return {x.first+y.first, x.second+y.second}; } void init(int n){sz = n;} void update(int p, int x, int y){ p += sz; for (tree[p].first+=x, tree[p].second+=y;p>1;p>>=1) tree[p>>1] = combine(tree[p], tree[p^1]); } pair<ll, int> query(int l, int r){ pair<ll, int> ret = {0, 0}; for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){ if (l&1) ret = combine(ret, tree[l++]); if (r&1) ret = combine(tree[--r], ret); } return ret; } }tree; pair<int, int> a[200200]; int n, k; ll query(int i){ auto p1 = tree.query(a[i].second+1, n), p2 = tree.query(0, a[i].second); return (p1.first - (ll)a[i].first*p1.second) + ((ll)a[i].first*p2.second - p2.first); } int main(){ scanf("%d %d", &n, &k); vector<int> v; for (int i=0;i<n;i++){ scanf("%d", &a[i].first); v.push_back(a[i].first); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int i=0;i<n;i++) a[i].second = lower_bound(v.begin(), v.end(), a[i].first) - v.begin(); tree.init(n); ll ans = 0, cur = 0; for (int i=0;i<k;i++){ cur += query(i); tree.update(a[i].second, a[i].first, 1); } ans = cur; for (int i=k;i<n;i++){ cur -= query(i-k); tree.update(a[i-k].second, -a[i-k].first, -1); cur += query(i); tree.update(a[i].second, a[i].first, 1); ans = max(ans, cur); } printf("%lld\n", ans); return 0; }3일차 2번) 원룸 구하기
문제 요약
$N$개의 가게의 위치와 종류, $M$개의 원룸의 위치가 주어질 때, 각 원룸에 대해 $K$종류의 가게와 자기자신을 포함하는 선분의 최소 길이를 구하는 문제입니다.
풀이
더보기일단 좌표압축을 하고 생각합시다. 가게만 있다고 생각하고, 각 지점 $x$마다 $x$가 왼쪽 끝점이면서 $K$종류의 가게를 포함하는 선분의 최소 길이를 계산할겁니다. 이는 투 포인터(슬라이딩 윈도우)로 $O(N)$에 구할 수 있습니다.
이제, $M$개의 원룸에 대해 답을 구해봅시다. 편의상, 위에서 구했던 여러 개의 선분들 중, 하나의 선분만 사용 가능하다고 생각하고 답을 계산해봅시다. 원룸의 위치를 $pos$, 선분을 $[x, y]$라고 했을 때, 답은 다음과 같습니다.
1. $pos < x$인 경우: $-pos+y$
2. $x \le pos \le y$인 경우: $y-x$
3. $y < pos$인 경우: $pos-x$
선분이 여러 개인 경우, 각각의 선분에 대해 위 식을 계산한 다음 이 중 최솟값을 구해주면 됩니다. 이를 나이브하게 계산하면 시간복잡도가 $O(NM)$이라 시간 초과가 납니다.
이를 해결하기 위해, 세그먼트 트리를 만듭시다. 위에서 적었던 식을 생각해보면 기울기가 -1, 0, 1인 직선(혹은 선분)이므로, 세그먼트 트리의 각 노드에 대해 위 식의 상수항의 최솟값을 각 기울기마다 저장해주면 $O(\log{N})$에 최솟값을 계산할 수 있습니다.
시간복잡도는 $O((N+M)\log{N})$입니다.
코드
더보기#include <bits/stdc++.h> #define int long long typedef long long ll; using namespace std; const ll INF = 1e18; struct node{ int l, r; ll x, y, z; node(){} node(int _l, int _r, ll _x, ll _y, ll _z):l(_l), r(_r), x(_x), y(_y), z(_z) {} }; void add(node &x, int _a, ll _b){ if (_a==1) x.x = min(x.x, _b); else if (_a==0) x.y = min(x.y, _b); else x.z = min(x.z, _b); } ll calc(node &x, ll p){ return min(p+x.x, min(x.y, -p+x.z)); } pair<int, int> a[500500]; vector<int> v; struct Seg{ node tree[1001000]; int sz; void init(int n){ sz = n; for (int i=sz;i<sz*2;i++) tree[i] = node(v[i-sz], v[i-sz+1], INF, INF, INF); for (int i=sz-1;i;i--) tree[i] = node(tree[i<<1].l, tree[i<<1|1].r, INF, INF, INF); } void update(int l, int r, int _a, ll _b){ for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){ if (l&1) add(tree[l++], _a, _b); if (r&1) add(tree[--r], _a, _b); } } ll query(int p, int x){ ll ret = INF; for (p+=sz;p;p>>=1) ret = min(ret, calc(tree[p], x)); return ret; } }tree; int cnt[500500]; signed main(){ int n, k, q; scanf("%lld %lld %lld", &n, &k, &q); for (int i=0;i<n;i++){ scanf("%lld %lld", &a[i].first, &a[i].second); v.push_back(a[i].first); } sort(a, a+n); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); if ((int)v.size()==1){ while(q--){ int x; scanf("%lld", &x); int ans = x-v[0]; if (ans<0) ans = -ans; printf("%lld\n", ans); } return 0; } int m = (int)v.size()-1; tree.init(m); int pt1 = 0, pt2 = 0, cur = 0; for (;pt1<n;pt1++){ while(pt2<n && cur<k){ if (!cnt[a[pt2].second]) cur++; cnt[a[pt2].second]++; pt2++; } if (cur<k) break; int l = lower_bound(v.begin(), v.end(), a[pt1].first) - v.begin(); int r = lower_bound(v.begin(), v.end(), a[pt2-1].first) - v.begin(); tree.update(l, r, 0, a[pt2-1].first-a[pt1].first); tree.update(0, l, -1, a[pt2-1].first); tree.update(r, m, 1, -a[pt1].first); cnt[a[pt1].second]--; if (!cnt[a[pt1].second]) cur--; } while(q--){ int x; scanf("%lld", &x); int idx = upper_bound(v.begin(), v.end(), x) - v.begin()-1; if (x<v[0]) printf("%lld\n", tree.query(0, v[0]) + (v[0]-x)); else if (x>=v.back()) printf("%lld\n", tree.query(m-1, v.back()) + (x-v.back())); else printf("%lld\n", tree.query(idx, x)); } return 0; }3일차 3번) 생존 신호
문제 요약
아웃풋 온리 문제입니다.
격자판에 거울을 적절히 배치해서 레이저가 이동한 거리를 최대화하는 문제입니다.
제가 만점을 받지 못한 유일한 문제입니다. (99.9점)
풀이
더보기만점 풀이가 아니지만, 제가 99.9점을 받은 풀이를 설명하겠습니다.
풀이의 아이디어는 간단합니다. 백트래킹으로 가능한 답들을 탐색하는 것입니다. 현재까지 이동한 거리, 현재 위치와 방향, 현재 격자판의 상태를 저장하고 백트래킹을 돌리면 답을 구할 수 있습니다. 이 방식을 이용하면 미션 11까지는 쉽게 만점을 받을 수 있고, 미션 12는 너무 경우의 수가 많아 만점을 받기 힘듭니다. 미션 12에서 점수를 더 얻기 위해, 탐색 우선순위를 랜덤으로 주고, 나왔던 최적해를 기반으로 백트래킹을 여러번 돌려서 더 좋은 해를 찾는 것을 계속 반복하니 395짜리 해를 얻을 수 있었습니다. 그 이후로 계속 프로그램을 돌려봤지만 더 좋은 해를 찾지 못했고, 99.9점으로 끝났습니다. (396짜리 해를 찾아야 만점을 받을 수 있습니다.)
그래프로 모델링한 후, 오일러 회로 알고리즘을 변형하여 푸는 방식도 생각해보았는데, 이 방식으로는 결국 풀지 못했습니다. 나중에 정해를 알게 되면 올리도록 하겠습니다.
수정) 정해는 connection profile dp를 이용하는 풀이라고 합니다. (+파란칸만 정점으로 놓고 그래프를 만든 후, 손으로 홀수 차수 점들을 적절히 연결해줘서 오일러 회로를 찾는 방식으로 푸는 것도 가능하다고 합니다. 지인 중에서 이 방식으로 풀어서 손으로 100점 받은 사람이 있네요.)
코드
더보기쓰인 코드가 너무 많고 만점도 아니기 때문에 코드는 따로 올리지 않겠습니다. (5000바이트 넘는 코드가 5개)
그대신 제 395짜리 답을 올리겠습니다.
17 18 ./..\./\@.-./..|./.\ ...|./\.\/\.../..\\. -\....\.../@\..\|... @/\///....\.@/\\.../ |.\..\//..\........\ \.//...-../....\\\/. ..\.\.../\..\\....\. .\..//\../.|./.\/./. ..|.\...\./.\/\/\../4일차 1번) 선물 상자
문제 요약
요세푸스 문제와 동일한데, 각 사람마다 목숨이 $A[i]$개인 요세푸스 문제입니다. ($M$칸씩 건너뛰면서 진행)
제한: $2 \le N \le 2000$, $1 \le M \le 10^9$, $1 \le A[i] \le 10^9$
풀이
더보기$N$이 작기 때문에, 시간복잡도가 $O(N^2)$인 풀이를 생각해봅시다. 1명을 퇴출시키는 과정을 $O(N)$에 할 수 있으면 문제가 풀립니다. 건너뛰는 값이 일정하기 때문에 누군가 퇴출되기 전까지 사이클을 형성하면서 계속 돌 것이고, 이 사이클의 원소 중 최소 원소가 퇴출된다는 것을 알 수 있습니다. 따라서, 사이클을 찾아주면 문제를 풀 수 있고, 원소의 개수가 $N$개 이하이므로 $O(N)$에 사이클을 찾을 수 있습니다.
시간복잡도는 $O(N^2)$입니다.
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; int main(){ int n, m, cur, cnt; scanf("%d %d", &n, &m); cur = (m-1)%n, cnt = n; vector<pair<int, int>> v(n); for (int i=0;i<n;i++){ scanf("%d", &v[i].first); v[i].second = i+1; } for (;cnt>1;cnt--){ /*printf("%d\n", cur); for (auto &x:v) printf("%d ", x.first); printf("\n");*/ int mn = 1e9, s = cur; do{ mn = min(mn, v[cur].first); cur = (cur+m)%(v.size()); }while(cur!=s); do{ v[cur].first -= mn-1; cur = (cur+m)%(v.size()); }while(cur!=s); do{ v[cur].first--; if (!v[cur].first) break; cur = (cur+m)%(v.size()); }while(cur!=s); cur = v.erase(v.begin()+cur) - v.begin(); cur = (cur+m-1)%(v.size()); } printf("%d\n", v[0].second); return 0; }4일차 2번) 파스칼 삼각형
문제 요약
$N$이 주어질 때, 파스칼의 삼각형에서 정삼각형 형태의 합이 $N$이 되는 경우의 수를 구하는 문제입니다. (무한히 많으면 -1)
제한: $1 \le T \le 4000$ (주어지는 정수의 개수), $1 \le N \le 10^{18}$
풀이
더보기맨 위 꼭짓점의 위치가 $(x, y)$이고 크기가 $sz$인 정삼각형 형태의 합을 $S(x, y, sz)$라고 정의합시다.
크기가 $sz$인 정삼각형은 $\binom{x+sz-1}{sz-1}$이상의 원소를 포함하고 있기 때문에, $S(x, y, sz) \le K$인 경우의 수는 $O(K^{\frac{1}{sz-1}})$개임을 알 수 있습니다. $sz \ge 5$면서 $S(x, y, sz) \le 10^{18}$인 정삼각형 개수를 계산해보면 대략 20만개이고, 이를 전부 나이브하게 합을 구해줘도 0.2초안에 모두 계산이 됩니다.
$sz \ge 5$인 경우 가능한 합을 모두 전처리했기 때문에, 정렬을 해놓고 각 쿼리마다 이분탐색을 하면 $sz \ge 5$인 경우 답을 빠르게 구할 수 있습니다.
이제, $sz \le 4$인 경우만 계산하면 됩니다. 파스칼의 삼각형의 성질을 이용하면, 다음 식들을 얻을 수 있습니다.
$$S(x, y, 1) = \binom{x}{y}$$
$$S(x, y, 2) = \binom{x}{y} + \binom{x+2}{y+1}$$
$$S(x, y, 3) = \binom{x}{y} + \binom{x+4}{y+2}$$
$$S(x, y, 4) = \binom{x}{y} + \binom{x+6}{y+3} - \binom{x+4}{y+2}$$
$y$의 값을 고정시키면 위 함수들은 모두 강증가하기 때문에 이분탐색으로 답을 구할 수 있고, $\binom{100}{50} \ge 10^{18}$이므로 $y \le 50$에 대해서만 계산해줘도 충분합니다. (엄밀히 따지면, $\binom{2n}{n}$은 스털링 근사를 적용하면 지수함수 꼴이므로, $y$의 최댓값은 로그에 비례합니다.)
$N$ 제한이 크기 때문에 저는 128비트 정수 자료형인 __int128을 이용하여 구현하였습니다. $S(x, y, 4)$의 식에서 -가 붙는 항이 있기 때문에, $x$의 이분탐색 범위를 좀 넓게 잡아야 합니다. 고정된 $y$에 대해 $\binom{x+6}{y+3} \le 10^{21}$인 $x$ 범위에서 이분탐색을 하니 100점을 받을 수 있었습니다. (+ 항만 있도록 식을 변형해서 $10^{18}$이하 범위에서 풀어도 될겁니다.)
시간복잡도는 대략 $(O((MAX^{\frac{1}{4}}\log{MAX} + T(\log^2{MAX}))$ 입니다. ($MAX = 10^{18}$)
코드
더보기#include <bits/stdc++.h> #define int long long #define ll __int128 using namespace std; vector<ll> NCR[200000], v; ll ncr(ll n, ll r){ if (r==0) return 1; if (r==1) return n; if (r==2) return n*(n-1)/2; if (r==3) return n*(n-1)*(n-2)/6; if (r==4) return n*(n-1)*(n-2)*(n-3)/24; if ((int)NCR[n].size()<=r-5) return 1e24; return NCR[n][r-5]; } ll calc(int sz, int x, int y){ ll ret = 0; for (int i=0;i<sz;i++){ for (int j=0;j<=i;j++){ ret += ncr(x+i, y+j); if (ret>1e24 || ret<0) return 1e24; } } return ret; } ll mxval[101] = {0, (ll)1e24, 1414213562374, 181712061, 2213366, 164378, 29941, 9071, 3768, 1929, 1143, 752, 535, 404, 320, 263, 223, 194, 172, 155, 142, 131, 123, 116, 110, 106, 102, 98, 96, 93, 91, 90, 89, 87, 86, 86, 85, 85, 84, 84, 84, 84, 84, 84, 84, 84, 84, 85, 85, 85, 86, 86, 86, 87, 87, 88, 89, 89, 90, 90, 91, 91, 92, 93, 93, 94, 95, 96, 96, 97, 98, 98, 99, 100, 101, 102, 102, 103, 104, 105, 106, 106, 107, 108, 109, 110, 110, 111, 112, 113, 114, 115, 116, 116, 117, 118, 119, 120, 121, 122}; void solve(int n){ scanf("%lld", &n); if (n==1) {printf("-1\n"); return;} int ans = upper_bound(v.begin(), v.end(), n) - lower_bound(v.begin(), v.end(), n); //printf("%lld\n", ans); if (n==2) ans++; else if (n==3) ans += 3; else ans += 4; //printf("%lld\n", ans); //for (int i=0;i<70;i++) printf("%lld ", mxval[i]); for (int i=2;i<=100;i++){ if (mxval[i]<=i*2) break; int l = i*2, r = mxval[i]; while(l<r){ ///size 1 int m = (l+r)/2; ll tmp = ncr(m, i); if (tmp<n) l = m+1; else if (tmp>n) r = m; else{ if (m==i*2) ans++; else ans += 2; break; } } //printf("%lld %lld\n", i, ans); l = i*2, r = mxval[i]; while(l<r){ ///size 2 int m = (l+r)/2; ll tmp = ncr(m, i) + ncr(m-2, i-1); if (tmp<n) l = m+1; else if (tmp>n) r = m; else{ if (m==i*2) ans++; else ans += 2; break; } } //printf("%lld %lld\n", i, ans); l = i*2, r = mxval[i]; while(l<r){ ///size 3 int m = (l+r)/2; ll tmp = ncr(m, i) + ncr(m-4, i-2); if (tmp<n) l = m+1; else if (tmp>n) r = m; else{ if (m==i*2) ans++; else ans += 2; break; } } //printf("%lld %lld\n", i, ans); if (i==2) continue; l = i*2, r = mxval[i]; while(l<r){ ///size 4 int m = (l+r)/2; ll tmp = ncr(m, i) + ncr(m-6, i-3) - ncr(m-2, i-1); if (tmp<0) tmp = 1e24; if (tmp<n) l = m+1; else if (tmp>n) r = m; else{ if (m==i*2) ans++; else ans += 2; break; } } //printf("%lld %lld\n", i, ans); } printf("%lld\n", ans); } signed main(){ //freopen("output.txt", "w", stdout); for (int i=5;i<=101;i++){ NCR[i].push_back(1); for (int j=i+1;j<200000;j++){ ll tmp = NCR[j-1].back()*j/(j-i); if (tmp>1e24) break; NCR[j].push_back(tmp); } } for (int z=5;z<=100;z++){ bool flag = 0; for (int i=0;i<200000;i++){ bool flag2 = 0; for (int j=0;j<=i/2;j++){ ll tmp = calc(z, i, j); if (tmp>1e18) break; flag = 1, flag2 = 1; v.push_back(tmp); if (i!=j*2) v.push_back(tmp); } if (!flag2) break; } if (!flag) break; } sort(v.begin(), v.end()); int t; scanf("%lld", &t); for (int i=1;i<=t;i++) solve(i); return 0; }4일차 3번) 낙하 데미지
문제 요약
x축에 평행한 $N$개의 선분들이 있을 때, 각 선분에 대해 그 선분에서 땅까지 가면서 받는 낙하 데미지의 최솟값을 구하는 문제입니다.
풀이
더보기문제를 보면 아래 문제와 유사하다는 것을 알 수 있습니다.
https://www.acmicpc.net/problem/4008
4008번: 특공대
입력은 세 줄로 구성된다. 첫 번째 줄에 전체 병사들 수인 양의 정수 n이 주어진다. 두 번째 줄에 특공대의 조정된 전투력 계산 등식의 계수인 세 정수 a, b, c가 주어진다. 마지막 줄에 병사들 1, 2,
www.acmicpc.net
낙하데미지 식이 $(y_i - y_j)^2 + c_j$이므로 4008번과 동일하게 제곱항과 상수항들을 모두 상수 취급해주면 이는 직선의 방정식으로 볼 수 있고, convex hull trick을 적용하면 풀 수 있을 것 같다는 느낌이 듭니다. 그러나, 선분의 범위가 유한하기 때문에 $[s_i, e_i]$ 구간에 있는 직선들만 골라서 최솟값을 구해줘야 합니다.
이를 해결하기 위해, 세그먼트 트리를 만들어주고, 각 노드마다 convex hull trick에 쓰이는 스택을 만들어주면 됩니다. 구간 업데이트를 하기 위해 lazy propagation을 사용하면 propagate 과정에서 직선을 여러개 전달해줘야 할 수도 있기 때문에 시간복잡도가 보장되지 않아서 저는 lazy propagation을 사용하지 않았습니다. 그대신, 트리를 2개 만들어준다음 적절히 업데이트와 쿼리를 하는 방식으로 구현을 했습니다. 자세한건 코드를 참고하면 좋을 것 같습니다.
정렬을 하면 $y_i$값이 단조증가하기 때문에 $O(N)$ convex hull trick을 적용해서 풀면 시간복잡도 $O(N\log{N})$에 문제를 해결할 수 있습니다. (메모리 제한이 생각보다 빡빡합니다.)
코드
더보기#include <bits/stdc++.h> typedef long long ll; using namespace std; const ll INF = 2e18; struct Line{ int a; ll b; Line(){} Line(int _a, ll _b):a(_a), b(_b){} ll get(ll x) {return (ll)a*x+b;} }; inline double cross(Line &f, Line &g){ return (double)(g.b-f.b)/(f.a-g.a); } struct Li_chao{ ///why my li-chao tree O(Nlog^2N) solution TLE!!!! vector<Line> st; int pt; void init(){ st.emplace_back(0, 0); pt = 0; } void insert(Line f){ if (st.empty()) init(); if (st.back().a==f.a){ if (st.back().b<=f.b) return; st.pop_back(); } while((int)st.size()>1){ assert(f.a!=st.back().a); if (cross(f, st.back())>cross(st.back(), *(--(--st.end())))) break; st.pop_back(); } st.push_back(f); if (pt>=(int)st.size()) pt = (int)st.size()-1; } ll query(ll x){ if (st.empty()) return 0; while(pt+1<(int)st.size() && cross(st[pt], st[pt+1])<x) pt++; return st[pt].get(x); } }; struct Seg{ Li_chao tree1[1048577], tree2[1048577]; /*void init(int i, int l, int r){ tree1[i].init(); tree2[i].init(); if (l==r) return; int m = (l+r)>>1; init(i<<1, l, m); init(i<<1|1, m+1, r); }*/ void update(int i, int l, int r, int s, int e, ll _a, ll _b){ if (r<s || e<l) return; if (s<=l && r<=e){ tree1[i].insert(Line(_a, _b)); return; } tree2[i].insert(Line(_a, _b)); int m = (l+r)>>1; update(i<<1, l, m, s, e, _a, _b); update(i<<1|1, m+1, r, s, e, _a, _b); } ll query(int i, int l, int r, int s, int e, ll x){ if (r<s || e<l) return INF; if (s<=l && r<=e) return min(tree1[i].query(x), tree2[i].query(x)); int m = (l+r)>>1; return min(tree1[i].query(x), min(query(i<<1, l, m, s, e, x), query(i<<1|1, m+1, r, s, e, x))); } }TREE; struct Edge{ int y, s, e, c, idx; bool operator<(const Edge &E) const{ return y<E.y; } }a[200200]; ll ans[200200]; signed main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); int n; cin >> n; vector<int> vec; vec.push_back(0); vec.push_back(1e9+1); for (int i=0;i<n;i++){ cin >> a[i].y >> a[i].s >> a[i].e >> a[i].c; /*a[i].y = i; a[i].s = a[i].e = i*2+1; a[i].c = 0; assert(a[i].s>=1 && a[i].e>=1);*/ a[i].e++; a[i].idx = i; vec.push_back(a[i].s); vec.push_back(a[i].e); } sort(a, a+n); sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); for (int i=0;i<n;i++){ a[i].s = lower_bound(vec.begin(), vec.end(), a[i].s) - vec.begin(); a[i].e = lower_bound(vec.begin(), vec.end(), a[i].e) - vec.begin()-1; } int m = (int)vec.size()-1; //TREE.init(1, 0, m); for (int j=0;j<n;j++){ ans[a[j].idx] = TREE.query(1, 0, m, a[j].s, a[j].e, a[j].y) + (ll)a[j].y*a[j].y; TREE.update(1, 0, m, a[j].s, a[j].e, -a[j].y*2, ans[a[j].idx]+(ll)a[j].y*a[j].y+a[j].c); } for (int i=0;i<n;i++) cout << ans[i] << '\n'; return 0; }'일기장' 카테고리의 다른 글
코드포스 IGM 달성 후기 (11) 2022.01.31 NYPC 2021 본선 후기 (10) 2021.10.31 코드포스 GM(레드) / solved.ac Ruby V 달성 후기 (6) 2021.08.22 KOI 2021 고등부 후기 (6) 2021.07.25 CEOI 2019 Day 1 (1) 2021.07.22