USACO 2017 January Contest (Gold) 풀이

요즘 유사코 골드를 돌고 있습니다!

Balanced Photo

  먼저 소들의 키를 1~N 범위로 압축해줍니다. 그런 뒤 1~N번 소까지 순회하며 BIT를 이용해 키가 $[h_i+1, N]$ 범위에 있는 소들의 합을 $L_i$에 저장합니다. $L_i$를 채운 뒤에는 자신의 키도 BIT에 업데이트해줍니다. $R$ 배열은 순회 순서를 반대로 해서 채워줄 수 있습니다. 이 과정을 모두 마친 뒤 $Min(L_i, R_i) * 2 < Max(L_i, R_i)$를 만족하는 소들의 개수를 세 주면 됩니다. 시간복잡도는 O(NlogN)입니다. 간단한 자료구조 문제였습니다!

#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; pii arr[100009]; int l[100009], tree[100009], n; void update(int x) { while(x <= n) { ++tree[x]; x += (x&-x); } } int sum(int x) { int s = 0; while(x > 0) { s += tree[x]; x -= (x&-x); } return s; } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d",&arr[i].first); arr[i].second = i; } sort(arr+1, arr+n+1); for(int i=1; i<=n; i++) arr[i].first = i; sort(arr+1, arr+n+1, [&](pii a, pii b) {return a.second < b.second;}); for(int i=1; i<=n; i++) { l[i] = sum(n) - sum(arr[i].first); update(arr[i].first); } for(int i=1; i<=n; i++) tree[i] = 0; int cnt = 0; vector<int> stk; for(int i=n; i>=1; i--) { int r = sum(n) - sum(arr[i].first); if(min(l[i], r) * 2 < max(l[i], r)) ++cnt; update(arr[i].first); stk.push_back(r); } printf("%d",cnt); return 0; }

Hoof, Paper, Scissors (Gold)

  DP 문제입니다. DP값 두 개를 관리하면서 답을 구해나가는데, $DP1[i][j] =$ 1~i번째까지 최대 j번 바꿨을 때 최대 승수로 정의하고 점화식을 세우면, $DP1[i][j] = Max(DP2[i][j][0], DP2[i][j][1], DP2[i][j][2])$이고, 여기서 $DP2[i][j][k] =$ k는 마지막으로 바꾼 제스쳐의 종류, 즉 H, P, S 중 하나이고, 최대 j번 바꿨을 때 1 ~ i 범위에서 가장 많이 이길 수 있는 승수로 정의합니다. $DP2[i][j][k] = Max(DP2[i-1][j][k] +$ i번째에 이길 수 있는지의 여부(1 or 0)$, DP1[i][j-1])$입니다.

  점화식이 다소 복잡하지만, 먼저 N^2K DP를 짠 뒤 시간을 줄이려고 하다보면 이런 꼴의 점화식이 나오게 됩니다. DP1은 원래 점화식이고, DP2는 최대 연속 부분합 DP 같은 느낌이라고 생각하시면 될 것 같습니다.

#include <bits/stdc++.h> using namespace std; char arr[100009]; int dp[100009][22]; int dp2[100009][3]; int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) scanf(" %c",&arr[i]); for(int i=1; i<=n; i++) { dp2[i][0] = dp2[i-1][0] + (arr[i] == 'H'); dp2[i][1] = dp2[i-1][1] + (arr[i] == 'P'); dp2[i][2] = dp2[i-1][2] + (arr[i] == 'S'); dp[i][0] = max({dp2[i][0], dp2[i][1], dp2[i][2]}); } for(int i=1; i<=k; i++) { for(int j=1; j<=n; j++) { dp2[j][0] = max(dp2[j-1][0] + (arr[j] == 'H'), dp[j][i-1]); dp2[j][1] = max(dp2[j-1][1] + (arr[j] == 'P'), dp[j][i-1]); dp2[j][2] = max(dp2[j-1][2] + (arr[j] == 'S'), dp[j][i-1]); dp[j][i] = max({dp2[j][0], dp2[j][1], dp2[j][2]}); } } printf("%d",dp[n][k]); return 0; }

안대 낀 스피드러너 (원제 : Cow Navigation)

  한글 디스크립션을 중심으로 설명하겠습니다. 스피드러너가 두 사람이고, 한 사람은 오른쪽을 보고 시작하고 다른 한 사람은 위를 보고 시작한다고 생각하면 좀 더 생각하기 편합니다. 오른쪽을 보고 시작한 스피드러너를 R, 위쪽을 보고 시작한 스피드러너를 U라고 합시다. 이제 상태 BFS를 돌릴건데, (R의 X좌표, R의 Y좌표, U의 X좌표, U의 Y좌표, R이 보는 방향) 이렇게 다섯 가지 변수를 가지고 다니면 됩니다. U의 방향은 R의 방향에서 반시계방향으로 90도 돌린 방향이기 때문에 따로 들고 다니지 않아도 됩니다.

  상태의 개수, 즉 정점 수는 $4N^4$개이고, 이는 약 64만개 정도입니다. 이 정도면 충분히 시간 안에 돌 수 있습니다.

#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; struct node {int rx,ry,ux,uy,dd;}; char arr[22][22]; bool visited[22][22][22][22][4]; int dx[4] = {0,-1,0,1}; int dy[4] = {1,0,-1,0}; int main() { int n; scanf("%d",&n); memset(arr, 'H', sizeof(arr)); for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { scanf(" %c",&arr[i][j]); } } int cnt = 0; queue<node> que; que.push({n,1,n,1,0}); while(!que.empty()) { int sz = que.size(); while(sz--) { node now = que.front(); que.pop(); if(now.rx == 1 && now.ry == n && now.ux == 1 && now.uy == n) return !printf("%d",cnt); if(visited[now.rx][now.ry][now.ux][now.uy][now.dd+1 & 3] == 0) { visited[now.rx][now.ry][now.ux][now.uy][now.dd+1 & 3] = 1; que.push({now.rx, now.ry, now.ux, now.uy, now.dd+1 & 3}); } if(visited[now.rx][now.ry][now.ux][now.uy][now.dd+3 & 3] == 0) { visited[now.rx][now.ry][now.ux][now.uy][now.dd+3 & 3] = 1; que.push({now.rx, now.ry, now.ux, now.uy, now.dd+3 & 3}); } pii rnxt = {now.rx + dx[now.dd], now.ry + dy[now.dd]}, unxt = {now.ux + dx[now.dd+1 & 3], now.uy + dy[now.dd+1 & 3]}; if((pii){now.rx, now.ry} != (pii){1,n} && arr[rnxt.first][rnxt.second] != 'H') now.rx = rnxt.first, now.ry = rnxt.second; if((pii){now.ux, now.uy} != (pii){1,n} && arr[unxt.first][unxt.second] != 'H') now.ux = unxt.first, now.uy = unxt.second; if(visited[now.rx][now.ry][now.ux][now.uy][now.dd] == 0) { visited[now.rx][now.ry][now.ux][now.uy][now.dd] = 1; que.push({now.rx, now.ry, now.ux, now.uy, now.dd}); } } ++cnt; } return 0; }