BUSACO 2017 February Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다. 소가 길을 건너는 이유 시리즈 이고, 한글 번역이 되어있으므로 따로 문제 설명은 하지 않으려 한다.
백준에서는 https://www.acmicpc.net/category/396 에서 볼 수 있다.
Bronze 1
문제 설명 : https://www.acmicpc.net/problem/14467
문제 풀이 : 배열에 최근 위치를 저장해서 현재 받은 입력이 최근 위치와 달랐는지 판별하고 횟수를 세준다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include<bits/stdc++.h>
using namespace std;
int arr[101];
int main()
{
int n,i,a,b,cnt=0;
scanf("%d",&n);
for(i=1;i<=10;i++) arr[i]=2;
for(i=1;i<=n;i++)
{
scanf("%d %d",&a,&b);
if(arr[a]+b==1) cnt++;
arr[a]=b;
}
printf("%d",cnt);
}
|
Bronze 2
문제 설명 : https://www.acmicpc.net/problem/14468
문제 풀이 : 경로가 겹치기 위해서는 두 종류의 문자가 ABAB순서로 배치되어 있어야 한다. A부터 Z까지 임의의 두 문자를 잡고 (예를 들어 S,J) SJSJ 또는 JSJS 순서대로 배치되어 있는지 확인하면 된다. 인덱스를 저장해 놓고 풀면 끝.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include<bits/stdc++.h>
using namespace std;
int arr[3][50];
int main()
{
char a;
int i,j,n,ans=0;
for(i=1;i<=52;i++)
{
scanf("%c",&a);
n=a-'A'+1;
if(arr[1][n]==0) arr[1][n]=i;
else arr[2][n]=i;
}
for(i=1;i<=26;i++)
for(j=i+1;j<=26;j++)
if((arr[1][i]<arr[1][j]&&arr[1][j]<arr[2][i]&&arr[2][i]<arr[2][j])||(arr[1][i]>arr[1][j]&&arr[1][i]<arr[2][j]&&arr[2][i]>arr[2][j]))
ans++;
printf("%d",ans);
}
|
Bronze 3
문제 설명 : https://www.acmicpc.net/problem/14469
문제 풀이 : 먼저 도착한 순서대로 바로바로 검사를 받기 시작하는 것이 이득이다. 따라서 도착 시간에 대해서 정렬하고, max(전 사람이 끝나는 시간, 다음 사람이 도착하는 시간) 이 다음 사람이 검사 받기 시작하는 시간이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include<bits/stdc++.h>
using namespace std;
int arr[10101010];
int arr2[10101010];
int main()
{
int n,i,j,k,a,b;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&a,&b);
arr[a]+=b;
arr2[a]++;
}
int go=0;
for(i=1;i<=1000001;i++)
{
if(go>0) go--;
go+=arr[i];
n-=arr2[i];
if(n==0)
break;
}
printf("%d",i+go);
}
|
Silver 1
문제 설명 : https://www.acmicpc.net/problem/14464
문제 풀이 : 회의실 배정이 생각나는 정렬 기준 + 그리디 문제이다. 그때와 똑같이 가능한 마지막 시간으로 정렬을 하는데, 이때 어떤 닭을 배정해 주느냐에 따라 다른 소에 배정을 해줄 수도 있고 못할 수도 있다. 가능한 마지막 시간 기준으로 정렬을 했기 때문에 그리디하게 생각하면 가능한 가장 먼저 온 닭을 사용하는 것이 이득이라는 것을 알 수 있다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<bits/stdc++.h>
using namespace std;
#define va first
#define vb second
pair<int,int> arr[202020];
int crr[202020];
int chk[101010];
int main()
{
int n,c,i,j,k,l,m,cnt=0;
scanf("%d %d",&c,&n);
for(i=1;i<=c;i++)
scanf("%d",&crr[i]);
for(i=1;i<=n;i++)
scanf("%d %d",&arr[i].vb,&arr[i].va);
sort(arr+1,arr+1+n);
sort(crr+1,crr+1+c);
for(i=1;i<=c;i++)
for(j=1;j<=n;j++)
if(arr[j].vb<=crr[i]&&crr[i]<=arr[j].va&&chk[j]==0)
{
chk[j]=1;
cnt++;
break;
}
printf("%d",cnt);
}
|
Silver 2
문제 설명 : https://www.acmicpc.net/problem/14465
문제 풀이 : K개씩 그룹을 지어 보면서 그 안에 정상적인 신호등이 최대 몇개 있는지 확인하면 된다. 이때 매번 K개씩 확인하면 시간초과가 나기 때문에 Sweeping을 해주면 된다. (i~i+k)의 합을 이용해 (i+1~i+k+1)의 합을 빠르게 구해줄 수 있다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include<stdio.h>
int main()
{
int n,k,b,arr[100050]={0},x,min=0,i,j,mint=0;
scanf("%d %d %d",&n,&k,&b);
while(b--)
{
scanf("%d",&x);
arr[x]=1;
}
for(i=1;i<=k;i++)
min+=arr[i];
mint=min;
for(i=2;i+k-1<=n;i++)
{
mint=mint-arr[i-1]+arr[i+k-1];
min=min>mint?mint:min;
}
printf("%d",min);
}
|
Silver 3
문제 설명 : https://www.acmicpc.net/problem/14466
문제 풀이 : DFS를 통해 길을 건너지 않고도 갈 수 있는 블럭끼리 모두 그룹으로 묶어 준다. 그 후 모든 소들에 대해 임의의 두 소가 같은 그룹에 있는지, 다른 그룹에 있는지를 판별하여 그 수를 세면 된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include<bits/stdc++.h>
using namespace std;
int mapp[1010][1010];
int edg[102][102][102][102];
int vis[1010][1010];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,k,r,cnt;
int cow[101010];
void dfs(int x, int y)
{
int i,j,xx,yy;
vis[x][y]=cnt;
for(i=0;i<4;i++)
{
xx=x+dx[i];
yy=y+dy[i];
if(vis[xx][yy]==0&&edg[x][y][xx][yy]==0&&0<xx&&xx<=n&&0<yy&&yy<=n)
{
vis[xx][yy]=cnt;
dfs(xx,yy);
}
}
}
int main()
{
int i,j,a,b,c,d;
long long int ans=0;
scanf("%d %d %d",&n,&k,&r);
for(i=1;i<=r;i++)
{
scanf("%d %d %d %d",&a,&b,&c,&d);
edg[a][b][c][d]=1;
edg[c][d][a][b]=1;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(vis[i][j]==0)
{
cnt++;
dfs(i,j);
}
for(i=1;i<=k;i++)
{
scanf("%d %d",&a,&b);
cow[vis[a][b]]++;
}
for(i=1;i<=cnt;i++)
for(j=i+1;j<=cnt;j++)
ans+=cow[i]*cow[j];
printf("%lld",ans);
}
|
Gold 1
문제 설명 : https://www.acmicpc.net/problem/14461
문제 풀이 : 어떤 점에서 세 칸 이동해서 갈 수 있는 칸의 수는 16칸이기 때문에 이를 이용하여 그래프를 만들어 준다. 각 점에서 3칸이동해 갈 수 있는 점들에 대해서 시간을 가중치로 하여 간선을 만들고 다익스트라를 돌리면 된다. 이때 마지막칸에는 꼭 세칸을 이동해서 갈 이유는 없기 때문에 그 주변칸과 같이 고려해 주면 된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include<bits/stdc++.h>
using namespace std;
long long int n,t;
int dx[16]={1,-1,0,0,3,2,1,0,-1,-2,-3,-2,-1,0,1,2};
int dy[16]={0,0,1,-1,0,1,2,3,2,1,0,-1,-2,-3,-2,-1};
long long int arr[105][105];
long long int dis[105][105];
int main()
{
int i,j,k,l;
scanf("%lld %lld",&n,&t);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%lld",&arr[i][j]);
dis[1][1]=1;
queue<long long int> qx,qy,di;
qx.push(1);
qy.push(1);
di.push(1);
{
long long int x=qx.front(); qx.pop();
long long int y=qy.front(); qy.pop();
long long int d=di.front(); di.pop();
for(i=0;i<16;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(1<=xx&&xx<=n&&1<=yy&&yy<=n)
{
if(dis[xx][yy]>d+3*t+arr[xx][yy]||dis[xx][yy]==0)
{
dis[xx][yy]=d+3*t+arr[xx][yy];
}
}
}
}
long long int mini=1e18;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
int dd=n+n-i-j;
if(dis[i][j]!=0)
{
if(dd==3)
mini=min(mini,dis[i][j]+3*t+arr[n][n]);
if(dd==2)
mini=min(mini,dis[i][j]+2*t);
if(dd==1)
mini=min(mini,dis[i][j]+t);
if(dd==0)
mini=min(mini,dis[i][j]);
}
}
}
printf("%lld",mini-1);
}
|
Gold 2
문제 설명 : https://www.acmicpc.net/problem/14462
문제 풀이 : DP로 해결이 가능하다. DP[i][j]를 왼쪽 목초지의 i번째와 오른쪽 목초지의 j번째 까지 사용했을때 가능한 쌍의 최대 갯수로 정의하면 LCS처럼 DP식을 세워나갈 수 있다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include<bits/stdc++.h>
using namespace std;
int arr[1001];
int arr2[1001];
int dp[1001][1001];
int main()
{
int n,i,j,k,l;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&arr[i]);
for(i=1;i<=n;i++)
scanf("%d",&arr2[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
if(abs(arr[i]-arr2[j])<=4)
dp[i][j]=dp[i-1][j-1]+1;
}
printf("%d",dp[n][n]);
}
|
Gold 3
문제 설명 : https://www.acmicpc.net/problem/14463
문제 풀이 : ABAB 형태의 쌍을 세야하지만 제한이 50000이라 Silver 처럼 N^2으로 풀기에는 부담감이 있다. 어떤 숫자의 왼쪽이 L 오른쪽이 R이므로 LLRR이므로 L과 R사이에 L이 몇개 있는지 세면 된다. 이는 세그먼트 트리를 활용하여 NlogN에 풀 수 있다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include<bits/stdc++.h>
using namespace std;
int arr[101010];
int idx[101010];
int chk[101010];
long long int tree[202020];
int n;
void upt(int node,int s,int e,int loc,int val)
{
if(s>loc||loc>e) return ;
tree[node]+=val;
if(s==e) return ;
upt(node*2,s,(s+e)/2,loc,val);
upt(node*2+1,(s+e)/2+1,e,loc,val);
return;
}
long long int sum(int node,int s,int e,int l,int r)
{
if(e<l||r<s)
return 0;
if(l<=s&&e<=r)
return tree[node];
return sum(node*2,s,(s+e)/2,l,r)+sum(node*2+1,(s+e)/2+1,e,l,r);
}
int main()
{
int cnt=0,i;
long long int ans=0;
scanf("%d",&n);
for(i=1;i<=2*n;i++)
{
scanf("%d",&arr[i]);
if(idx[arr[i]]==0)
{
cnt++;
idx[arr[i]]=cnt;
}
}
for(i=1;i<=2*n;i++)
{
if(chk[arr[i]]==0)
{
upt(1,1,n,idx[arr[i]],1);
chk[arr[i]]=1;
}
else
{
upt(1,1,n,idx[arr[i]],-1);
ans+=sum(1,1,n,idx[arr[i]]+1,n);
}
}
printf("%lld",ans);
}
|
Platinum 1
문제 설명 : https://www.acmicpc.net/problem/14458
문제 풀이 : 일단 기본 형태의 가로지르는 쌍의 갯수는 Inversion Counting을 활용하여 Segment Tree도 O(NlogN)에 풀 수 있다. 이때 각 숫자로 인한 inversion의 갯수를 미리 계산해 둔다. 전체 수의 갯수가 7인데 마지막칸에 있던 숫자로 인한 inversion의 갯수가 2라면 이 숫자를 맨 앞으로 움직이면 inversion의 수가 4가 되어 2가 증가하게 된다. 이런식으로 한 개씩 추가로 목초지를 돌릴 때 마다 inversion의 수가 어떻게 바뀌는지 O(1)에 구할 수 있고, 이 중 최솟값을 뽑아내면 된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct poi{
ll idx1,idx2,gap;
};
poi arr[1010101];
ll tree[5050505];
ll sum(ll l, ll r,ll s,ll e,ll nod)
{
if(s>r||e<l) return 0;
if(l<=s&&e<=r) return tree[nod];
return sum(l,r,s,(s+e)/2,nod*2)+sum(l,r,(s+e)/2+1,e,nod*2+1);
}
void upt(ll idx,ll val, ll s,ll e,ll nod)
{
//printf("%lld %lld %lld %lld\n",idx,s,e,nod);
if(s>idx||e<idx) return;
tree[nod]++;
if(s==e) return ;
upt(idx,val,s,(s+e)/2,nod*2);
upt(idx,val,(s+e)/2+1,e,nod*2+1);
}
bool sf(poi a,poi b)
{
return a.idx2<b.idx2;
}
bool sf2(poi a,poi b)
{
return a.idx1<b.idx1;
}
int main()
{
ll i,j,k,l,m,n,ans=0;
scanf("%lld",&n);
for(i=1;i<=n;i++){
scanf("%lld",&m);
arr[m].idx1=i;
}
for(i=1;i<=n;i++){
scanf("%lld",&m);
arr[m].idx2=i;
arr[m].gap=m;
}
sort(arr+1,arr+1+n,sf);
for(i=1;i<=n;i++)
{
ans+=sum(arr[i].idx1,n,1,n,1);
upt(arr[i].idx1,1,1,n,1);
}
ll now=ans;
ll now2=ans;
for(i=n;i>=1;i--)
{
now+=arr[i].idx1-1;
now-=n-arr[i].idx1;
ans=min(ans,now);
}
sort(arr+1,arr+1+n,sf2);
for(i=n;i>=1;i--)
{
now2+=arr[i].idx2-1;
now2-=n-arr[i].idx2;
ans=min(ans,now2);
}
printf("%lld",ans);
}
|
'코딩 > USACO 문제 풀이' 카테고리의 다른 글
| USACO 2017 Jan 전체 풀이 (0) | 2020.02.21 |
|---|---|
| USACO 2018 Feb Gold 3 - Taiming the Herd (0) | 2020.01.31 |
| USACO 2018 US Open Gold 2 - Milking Order (0) | 2019.12.26 |
| USACO 2016 Feb Gold 2 - Circular Barn Revisited (0) | 2019.11.20 |
| USACO 문제풀이에 앞서... (0) | 2019.11.19 |