IUPC가 5월 27일에 끝나게 되었다.
제 2회 IUPC때는 DP조차 모르는 상태로 참가해서 15등하고 좋아했었는데 1년이 지나 어느새 문제까지 내고 있게 되었다. (자격 미달이지만 ㅜㅜ)
개인적으로 내가 출제한 문제들이 디스크립션이 굉장히 후져서 참가자들에게 너무나도 미안했다..
CTP가 대상을 뺐긴것도 속상했고 ㅜㅜ 뭐 이외에도 문제 검수를 완벽하게 하지 못하여 디스크립션을 도중에 바꾸는 등 .. 탈많은 대회였지만 그래도 동아리 부회장을 맡으면서 처음으로 제대로 된 무언가를 진행했다는데 의미를 두기로 했다.
뭐 .. 이건 대회 운영 및 문제 출제를 하면서 느낀 개인적인 감상이고 대회에 대해서 얘기를 해보자면
우선 제 1,2회 IUPC가 33~38정도의 팀이 참가를 하여 진행해서 이번에는 40팀 정도의 참가를 예상하였으나
등록을 무려 52팀이나 하였다. 요즘 취업에 PS나 코딩시험이 거의 필수가 되어가는게 한몫 한것같지만
IUPC는 3인 1팀으로 지원을하기 때문에 52팀이라하면 150명이 넘는 사람이었기 때문에 예산을 재조정하는 경우까지 발생하였다..
물론 7팀은 no show를하게 되어 대략 45팀 정도 대회에 참가했다고 생각하면 될 것 같다.
대회 진행중이나 끝난 후의 스코어보드를 본 감상은 난이도 조절의 애매함이라고 느꼈다.
개인적으로 이번 대회의 상위권에서의 난이도 조절이 굉장히 잘된 것 같다고 느꼈다 1~6등이 전부 문제 수가 달랐기 때문이다.
하지만 하위권의 스코어보드가 처참했기 때문에 .. ㅜㅜ 5시간이나 되는 시간동안 지루함을 느꼈을것이라고 생각되서 미안해졌다 ..
최근 문제해결기법 수업등에서 여러 알고리즘을 다루는 문제도 많이 출제될 뿐더러 요즘 PS 공부를 하는 사람들이 늘었기 때문에 중 난이도의 문제를 적당량 풀 수 있을 거라 판단하고 많이 냈기 때문에 이런 결과를 보게 된 것같다.
뭐.. 모든 사람이 이런 공부를 하는것도 아니고 과제를 해야될 때만 찾아서 푸는 사람도 있고.. 이런걸 처음 접해보는 사람도 있을테니 하 난이도를 조금 더 쉽게 출제하여 no solve라도 없게 했어야하는데 이번 대회로 자신감을 잃는 사람들이 많아질까봐 괜히 두렵고 미안해졌다
음 후기를 쓰다보니 후회하고 징징되는 글이 되는거 같다.
사실 어떤 결과가 나오든 후회가 없기는 힘든법.. 그리고 사실 대회 준비는 개인적으로 매우 즐겁게 했기 때문에 전체적인 결과에는 만족한다. 위에 적은 소소한 부분들이 조금 걸릴뿐 ..
여기까지가 주관적이고 개인적인 나의 대회 후기이고 이글을 볼 사람은 없겠지만 혹시 모르니 대회 문제들 풀이라도 간략하게 적어야겠다.
A~L까지 12문제로 구성되었으며 나는 C,G,I,K를 출제했다
개인적으로 생각 하는 난이도는 C<A<L<J=G=I<D<G=B=K<E<F 라고 생각한다.
실제 대회 통계는 C<L<A<J<K=B<D=I<G=H<E<F 으로 약간은 다르게 되었지만.. 상 중 하 난이도로 비교를 했을 때는 비슷한 통계를 보였다.
풀린 문제 순서대로 간략한 풀이를 작성하겠다.
C.Calculate!
a에 b를 c번 XOR한 값을 출력하는 문제이다.
문제의 조건에서 c가 100자리 까지 들어올 수 있기 때문에 정수를 저장하는 자료형으로는 입력을 받을 수 없다.
bigInteger를 구현하여 c를 받는다고 하더라도 a에 b를 c번 직접 XOR할 경우 O(C)의 시간 복잡도를 가지게 되므로 TLE를 피할 수 없을것이다.
그럼 문제를 해결하기 위해 XOR의 특징을 이용해보자.
임의의 수 A에 A를 XOR 하게 된다면 0이 된다 (A^A=0)
임의의 수 A에 0을 XOR 하게 된다면 A가 된다 (A^0=A)
이 두가지 논리식을 이용하여 문제를 해결할 수 있다.
예를 들어 C가 5라면 A^B^B^B^B^B 를 출력해야 할것이다. 하지만 위의 논리식을 이용한다면 A^B로 식을 압축할 수 있다.
즉 C가 짝수면 A C가 홀수면 A^B를 출력하면 되는 문제로 바뀌게 된다.
C의 홀수 짝수여부는 C를 문자열로 입력받아 맨 뒷자리만 확인하면 된다.
<소스코드 ↓>
열기 접기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include < cstdio>
#include < algorithm>
#include < string>
#include < iostream>
using namespace std ;
typedef long long ll;
ll x, y;
string z;
int main() {
scanf ("%lld%lld" , & x, & y);
cin > > z;
if ((z.back() - '0' ) % 2 )
printf ("%lld\n" , x^y);
else
printf ("%lld\n" , x);
return 0 ;
}
cs
접기 L.감정이입
문제의 디스크립션이 장황하게 써있지만 사실 디스크립션을 전부 무시하고 출력란에 적혀있는 첫 번째 줄에 입력으로 주어진 두 이진수 B1, B2의 곱을 이진수로 출력한다. 한줄만 읽어도 되는 문제이다.
이진수의 곱셈을 직접 구현하여도 되고 이진수의 길이가 1이상 30 이하의 자연수이기 때문에 10진수로 바꾸어도 int 범위 내이므로 두 수를 int형 10진수로 변형 한 뒤 곱한 후(곱할 경우 수의 범위가 long long으로 커버된다.) 다시 이진수로 변형시켜도 되는 문제였다.
개인적으로 이런류의 구현을 처음 접해보는 사람에겐 후자의 방법을 추천한다.
여담으로 원래 처음 문제를 출제할 때 출제자인 kesakiyo형은 두 이진수의 길이를 최대 1000자까지 들어오게 하여 전자의 방법으로만 해결 가능하게 하려했지만 대회 시작 1주일전에 범위를 교체하였다. 그리고 이 판단은 그나마 하 문제를 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
#include < cstdio>
#include < algorithm>
#include < string>
#include < iostream>
using namespace std ;
long long x, y, z;
string a, b;
int r[101 ], f;
int main() {
cin > > a > > b;
for (int i = a.length() - 1 ; i > = 0 ; i- - ) {
if (a[i] = = '1' )
x + = (1 < < (a.length() - 1 - i));
}
for (int i = b.length() - 1 ; i > = 0 ; i- - ) {
if (b[i] = = '1' )
y + = (1 < < (b.length() - 1 - i));
}
z = x* y;
for (int i = 0 ; i < 63 ; i+ + ) {
if ((1LL < < i)& z)
r[i] = 1 ;
}
for (int i = 100 ; i > = 0 ; i- - ) {
if (! f& & r[i])
f = 1 ;
if (f)
printf ("%d" , r[i]);
}
return 0 ;
}
cs
접기
A.김식당
3가지 종류의 쿼리를 입력받아 처리해줘야 하는 문제이다.
N,M,T등의 제한이 적기 때문에 특별한 자료구조를 요구하지않고 벡터를 사용해주면 되는 문제였다.
다만 sort가 들어올 경우 주문 시간 별로 정렬을 해줘야하기 때문에 pair형으로 int를 두개를 입력받아 벡터에 삽입하여
pair의 첫번째 인자를 주문시간으로 주어서 sort를 이용하여 주문 시간별로 테이블을 정렬해주면 되는 문제였다.
complete의 경우 N이 크지않기 때문에 lower_bound등을 사용할 필요없이 벡터를 한번 훑어주며 찾은 다음 따로 표시를 해주어 출력이 안되게 해주면 됬다. (본인은 -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
#include < cstdio>
#include < algorithm>
#include < vector>
#include < iostream>
#include < string>
using namespace std ;
int n, m, x, y;
string q;
vector< pair< int , int > > vt;
int main() {
scanf ("%d%d" , & n, & m);
while (n- - ) {
cin > > q;
if (q = = "order" ) {
scanf ("%d%d" , & x, & y);
vt.push_back(make_pair(y, x));
}
else if (q = = "sort" ) {
sort(vt.begin(), vt.end());
}
else {
scanf ("%d" , & x);
for (int i = 0 ; i < vt.size(); i+ + ) {
if (vt[i].second = = x)
vt[i].second = - 1 ;
}
}
int f = 0 ;
for (int i = 0 ; i < vt.size(); i+ + ) {
if (vt[i].second ! = - 1 ) {
f = 1 ;
printf ("%d " , vt[i].second);
}
}
if (! f)printf ("sleep" );
puts("" );
}
return 0 ;
}
cs
닫기
J.나만 안되는 연애
문제의 조건을 살펴보면 남학교와 여학교간의 간선만 연결을하였을 때 모든 정점이 하나의 컴포넌트를 이룰 경우의 간선들의 가중치의 합의 최소값을 구하는 문제이다.
모든 정점들이 하나의 컴포넌트를 이룰 경우에 간선들의 가중치의 합의 최솟값은 MST(최소 스패닝 트리) 문제로 바꿔 생각할 수 있다.
이 문제의 경우에는 오직 남-여 로 이루어진 간선으로만 MST를 구성해야하고 그때 간선 가중치의 합의 최솟값을 출력하면 된다,
MST는 프림 알고리즘이나 크루스칼 알고리즘으로 구현할 수 있다.
나는 크루스칼 알고리즘을 사용하였다.
<소스코드 ↓>
열기 닫기
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
#include < cstdio>
#include < algorithm>
#include < vector>
using namespace std ;
int par[1001 ], n, m, u, v, d, a[1001 ], r, cnt;
char c;
int find(int h) {
return h = = par[h] ? h : par[h] = find(par[h]);
}
void merge(int x, int y, int z) {
if (a[x] * a[y] > 0 )return ;
x = find(x);
y = find(y);
if (x = = y)return ;
par[x] = y;
cnt+ + ;
r + = z;
}
vector< pair< int , pair< int , int > > > vt;
int main() {
scanf ("%d%d" , & n, & m);
for (int i = 1 ; i < = n; i+ + )
par[i] = i;
getchar();
for (int i = 1 ; i < = n; i+ + ) {
scanf (" %c" , & c);
if (c = = 'M' )a[i] = 1 ;
else a[i] = - 1 ;
}
for (int i = 0 ; i < m; i+ + ) {
scanf ("%d%d%d" , & u, & v, & d);
vt.push_back(make_pair(d, make_pair(u, v)));
}
sort(vt.begin(), vt.end());
for (int i = 0 ; i < vt.size(); i+ + ) {
if (cnt = = n - 1 )break ;
merge(vt[i].second.first, vt[i].second.second, vt[i].first);
}
printf ("%d\n" , cnt = = n - 1 ? r : - 1 );
return 0 ;
}
cs
닫기
K.소수 게임
누가 냈는지는 모르겠지만 대회 당시 디스크립션이 쓰레기같은 문제였다. 물론 지금은 수정되었지만 ... (ㅈㅅ합니다)
우선 소수를 판별해야 하므로 에라토스테네스의 체로 전처리를 해주자
이후 문제의 조건을 잘 살펴보면 라운드가 무려 10만이나 되므로 3번 째로 큰수를 적어도 log 시간에 처리해줄 수 있는 자료구조가 필요함을 알 수 있다.
본인의 경우 set으로 작성하였지만 priority_queue로 작성해도 되고 아예 변수 3개를 두고 3번 째로 큰 수를 갱신하는 방법을 사용해도 된다.
set을 사용할 경우 장점은 한번이라도 나온 수를 찾기 위해 어짜피 수를 저장해야하므로 set에 저장해주면 두가지 고민을 깔끔하게 해결해 줄 수 있다(?) 정도가 있다.
무튼 문제에서 얘기하는 순서에 따라서 질의를 잘 처리해 준 뒤 두 사람의 점수를 계산하여 답을 출력해주면 된다.
한가지 뻔한 함정을 팠는데 소수가 최대 500만 이하의 수가 들어오기 때문에 점수 계산을 long long 자료형을 이용해주어야 한다는 것..
문제가 어려워서 보단 디스크립션이 어려워서 못푼 사람이 많은 문제인것같다
<소스코드 ↓>
열기 닫기
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
#include < cstdio>
#include < algorithm>
#include < set>
using namespace std ;
typedef long long ll;
ll n, a, b, x, y;
bool p[5000001 ];
set< ll> sx, sy;
int main() {
for (int i = 2 ; i < = 5000000 ; i+ + ) {
if (p[i])continue ;
for (int j = i + i; j < = 5000000 ; j + = i)
p[j] = 1 ;
}
p[1 ] = 1 ;
scanf ("%lld" , & n);
while (n- - ) {
scanf ("%lld%lld" , & a, & b);
if (p[a]) {
if (sy.size() < 3 )
y + = 1000 ;
else {
set< ll> ::iterator it = sy.end();
it- - ;
it- - ;
it- - ;
y + = * it;
}
}
else {
if (sx.count(a) | | sy.count(a))
x - = 1000 ;
else
sx.insert(a);
}
if (p[b]) {
if (sx.size() < 3 )
x + = 1000 ;
else {
set< ll> ::iterator it = sx.end();
it- - ;
it- - ;
it- - ;
x + = * it;
}
}
else {
if (sx.count(b) | | sy.count(b))
y - = 1000 ;
else
sy.insert(b);
}
}
if (x = = y)puts("우열을 가릴 수 없음" );
else if (x > y)puts("소수의 신 갓대웅" );
else puts("소수 마스터 갓규성" );
return 0 ;
}
cs
닫기
B.너의 티어는?
사실 출제 의도는 확률DP를 의도하였지만 의외로 조합을 이용하여 그냥 확률을 계산하는 팀들도 꽤 있었다.(똑똑하시다 ..)
확률DP 해법은 dp[pos][w][l][d] <= pos번 경기하였을 때 w번 이기고 l번 지고 d번 비길 확률
으로 구성된 dp테이블을 전부 채워준 뒤 pos가 20인 테이블들을 확인하여 해당 티어에 배정될 확률들을 전부 더해준 뒤 출력하면 되는 문제였다.
점화식은 dp[pos][w][l][d]=(이길 확률)*dp[pos-1][w-1][l][d] + (질 확률)*dp[pos-1][w][l-1][d] + (비길 확률)*dp[pos-1][w][l][d-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
#include < cstdio>
#include < algorithm>
#include < cstring>
using namespace std ;
double dp[21 ][21 ][21 ][21 ];
double a, b, c;
double r[5 ];
int getpos(int w, int l, int d) {
int h = 2000 ;
h + = w * 50 - l * 50 ;
if (h < = 1499 )return 0 ;
else if (h < = 1999 )return 1 ;
else if (h < = 2499 )return 2 ;
else if (h < = 2999 )return 3 ;
else return 4 ;
}
double func(int pos, int w, int l, int d) {
if (w < 0 | | d < 0 | | l < 0 )return 0 ;
if (pos = = 0 )return 0 ;
if (w + d + l ! = pos)return 0 ;
if (pos = = 1 ) {
if (w)return a;
else if (l)return b;
else return c;
}
double & ret = dp[pos][w][l][d];
if (ret ! = - 1. 0 )return ret;
return ret = a* func(pos - 1 , w - 1 , l, d) + b* func(pos - 1 , w, l - 1 , d) + c* func(pos - 1 , w, l, d - 1 );
}
int main() {
scanf ("%lf%lf%lf" , & a, & b, & c);
for (int i = 0 ; i < 21 ; i+ + ) {
for (int j = 0 ; j < 21 ; j+ + ) {
for (int k = 0 ; k < 21 ; k+ + ) {
for (int s = 0 ; s < 21 ; s+ + )
dp[i][j][k][s] = - 1. 0 ;
}
}
}
for (int i = 0 ; i < 21 ; i+ + ) {
for (int j = 0 ; j < 21 ; j+ + ) {
for (int k = 0 ; k < 21 ; k+ + ) {
if (i + j + k ! = 20 )continue ;
r[getpos(i, j, k)] + = func(20 , i, j, k);
}
}
}
for (int i = 0 ; i < 5 ; i+ + )
printf ("%.8lf\n" , r[i]);
return 0 ;
}
cs
닫기
D.Defend the CTP!!!
문제를 요약하자면 1->C->N의 경로가 존재하는지 묻는 문제이다.
하나의 질문이라면 대답하는데 1->C까지의 경로를 확인하는 DFS와 C->N까지의 경로를 확인하는 DFS를 수행하여 해결할 수 있다.
즉 시간 복잡도는 O(N+M)인데
문제는 저 질문을 T번(<=100000) 물어보기 때문에 O(T*(N+M))이라면 당연히 시간초과가 날 것이다..
하지만 놀랍게도 단 2번의 DFS 만으로 모든 질문에 대한 답을 내놓을 수 있다.
우선 1번 정점에서 DFS를 수행하여 갈 수 있는 모든 정점에 체크를 해놓는다.
그리고 현재의 그래프의 간선의 방향을 전부 바꿔논 역방향 그래프의 N번 정점에서 DFS를 수행하여 갈 수 있는 모든 정점에 체크를 해놓는다.
그렇다면 우리는 문제에서 물어보는 1->C->N의 경로의 존재를 확인 할 때 두번의 전처리에 모두 체크가 된 정점만 경로가 있다고 대답할 수 있다.
이해가 잘 안된다면 한번 그림을 그려보면 납득할 수 있을것이다.
<소스코드 ↓>
열기 닫기
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
#include < cstdio>
#include < algorithm>
#include < vector>
#include < cstring>
using namespace std ;
vector< vector< int > > vt;
vector< vector< int > > rvt;
int n, m, t, x, y, a[100010 ], b[100010 ], r;
void dfs(int here) {
a[here] = true ;
for (int i = 0 ; i < vt[here].size(); i+ + ) {
if (! a[vt[here][i]])
dfs(vt[here][i]);
}
}
void rdfs(int here) {
b[here] = true ;
for (int i = 0 ; i < rvt[here].size(); i+ + ) {
if (! b[rvt[here][i]])
rdfs(rvt[here][i]);
}
}
int main() {
scanf ("%d%d" , & n, & m);
vt.resize(n + 1 );
rvt.resize(n + 1 );
for (int i = 0 ; i < m; i+ + ) {
scanf ("%d%d" , & x, & y);
vt[x].push_back(y);
rvt[y].push_back(x);
}
scanf ("%d" , & t);
dfs(1 );
rdfs(n);
while (t- - ) {
scanf ("%d" , & x);
printf ("%s\n" , a[x]& & b[x] ? "Defend the CTP" : "Destroyed the CTP" );
}
return 0 ;
}
cs
닫기
I.꽃길
음 내가 출제한 문제인데.. 사실 올해 삼성 기출로 알려진 진공청소기 문제였던가? .. 그 O(N^8)인가의 시간으로 완전탐색을 하는 문제를 보고 우리학교 학생들이 이 정도 문제를 다 풀어서 삼성 SW 역량 테스트에서도 좋은 결과를 내길 원해서 낸 문제이다.
사실 조건을 보면 알 수 있겠지만 N제한이 10밖에 되지 않기 때문에 O(N^6)으로 가능한 모든 위치에 씨앗을 심어보는 완전 탐색으로 해결할 수 있다.
두 씨앗이 꽃이 피었을 때 닿을 조건은 맨하탄거리가 2이하인 경우지만 이걸 생각안하고 그냥 닿는지 일일이 확인해줘도 넉넉한 시간에 통과할 수 있다.
<소스코드 ↓>
열기 닫기
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
#include < cstdio>
#include < algorithm>
#define INF 987654321
using namespace std ;
int dx[] = { 0 ,0 ,0 ,1 ,- 1 };
int dy[] = { 0 ,1 ,- 1 ,0 ,0 };
int n, g[11 ][11 ], res;
bool chk(int x, int y) {
return 0 < = x& & x < n & & 0 < = y& & y < n;
}
int func(int a, int b, int c, int d, int e, int f) {
if (abs(a - c) + abs(b - d) < = 2 )return INF;
if (abs(a - e) + abs(b - f) < = 2 )return INF;
if (abs(c - e) + abs(d - f) < = 2 )return INF;
int ret = 0 ;
for (int i = 0 ; i < 5 ; i+ + ) {
int x = dx[i] + a;
int y = dy[i] + b;
if (! chk(x, y))return INF;
ret + = g[x][y];
}
for (int i = 0 ; i < 5 ; i+ + ) {
int x = dx[i] + c;
int y = dy[i] + d;
if (! chk(x, y))return INF;
ret + = g[x][y];
}
for (int i = 0 ; i < 5 ; i+ + ) {
int x = dx[i] + e;
int y = dy[i] + f;
if (! chk(x, y))return INF;
ret + = g[x][y];
}
return ret;
}
int main() {
scanf ("%d" , & n);
res = INF;
for (int i = 0 ; i < n; i+ + ) {
for (int j = 0 ; j < n; j+ + )
scanf ("%d" , & g[i][j]);
}
for (int q = 0 ; q < n; q+ + ) {
for (int w = 0 ; w < n; w+ + ) {
for (int e = 0 ; e < n; e+ + ) {
for (int r = 0 ; r < n; r+ + ) {
for (int t = 0 ; t < n; t+ + ) {
for (int y = 0 ; y < n; y+ + ) {
res = min(res, func(q, w, e, r, t, y));
}
}
}
}
}
}
printf ("%d\n" , res);
return 0 ;
}
cs
닫기
G.총깡 총깡
이 문제 역시 내가 제출한 문제이다. 개인적으로 이 문제도 디스크립션이 지금 생각해보면 좀 후진것같다..
문제의 디스크립션을 일부로 복잡하게 한것도 있지만 출력 조건에서 오해의 여지가 있기 때문이다.
음 뭐 답부터 얘기해보자면 그냥 진서의 집부터 A형집과 B형집들로 최단거리를 구하여 A형 집과 B형 집 중 가까운 집과 그 거리를 출력하면 되는 문제이다.
한 정점에서의 부터 최단거리는 다익스트라 알고리즘을 이용하여 구할 수 있다.
여담으로 SPFA 알고리즘으로도 돌려보았는데 여유롭게 통과한다.
<소스코드 ↓>
열기 닫기
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
#include < cstdio>
#include < algorithm>
#include < queue>
#include < vector>
#include < cstring>
using namespace std ;
int n, m, j, k, x, y, z, h[5001 ], d[5001 ], r, f;
vector< vector< pair< int , int > > > vt;
int main() {
scanf ("%d%d%d%d" , & n, & m, & j, & k);
for (int i = 0 ; i < k; i+ + ) {
scanf ("%d" , & x);
h[x] = 1 ;
}
for (int i = 0 ; i < k; i+ + ) {
scanf ("%d" , & x);
h[x] = 2 ;
}
vt.resize(n + 1 );
for (int i = 0 ; i < m; i+ + ) {
scanf ("%d%d%d" , & x, & y, & z);
vt[x].push_back(make_pair(y, z));
vt[y].push_back(make_pair(x, z));
}
memset(d, - 1 , sizeof (d));
priority_queue< pair< int , int > > pq;
pq.push({ 0 ,j });
while (pq.size()) {
int here = pq.top().second;
int cost = - pq.top().first;
pq.pop();
if (d[here] ! = - 1 )continue ;
d[here] = cost;
if (r& & r < cost)
break ;
if (h[here]) {
if (! r) {
r = cost;
f = h[here];
}
else {
if (f + h[here] = = 3 ) {
f = 3 ;
break ;
}
}
}
for (int i = 0 ; i < vt[here].size(); i+ + ) {
pair< int , int > next = vt[here][i];
if (d[next.first] ! = - 1 )continue ;
pq.push(make_pair(- next.second - cost, next.first));
}
}
if (! f) {
puts("-1" );
return 0 ;
}
if (f = = 3 | | f = = 1 )puts("A" );
else puts("B" );
printf ("%d\n" , r);
return 0 ;
}
cs
닫기
H.섬 여행
정점에 가중치가 있는 그래프가 주어질 때 어떤 정점 A에서 간선을 타고 정확히 K번 이동하였을 때 도착한 섬의 가중치 중 가장 낮은 가중치를 출력하는 문제이다.
최솟값을 계산하는 전형적인 다이나믹 프로그래밍 문제이다.
dp[pos][state]를 어떤 정점 pos에서 state번 간선을 타고 이동하였을 때 도착한 섬의 가중치 중 가장 낮은 가중치라고 정의한다면
dp[pos][state] = pos에서 이동 가능한 모든 정점(V) : MIN(dp[V][state-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
#include < cstdio>
#include < algorithm>
#include < cstring>
#include < vector>
#define INF 987654321
using namespace std ;
int n, m, h[101 ], x, y, t, a, k, dp[101 ][501 ];
vector< vector< int > > vt;
int func(int pos, int state) {
if (! state)
return h[pos];
int & ret = dp[pos][state];
if (ret ! = - 1 )return ret;
ret = INF;
for (int i = 0 ; i < vt[pos].size(); i+ + ) {
ret = min(ret, func(vt[pos][i], state - 1 ));
}
return ret;
}
int main() {
memset(dp, - 1 , sizeof (dp));
scanf ("%d%d" , & n, & m);
for (int i = 1 ; i < = n; i+ + )
scanf ("%d" , & h[i]);
vt.resize(n + 1 );
for (int i = 0 ; i < m; i+ + ) {
scanf ("%d%d" , & x, & y);
vt[x].push_back(y);
vt[y].push_back(x);
}
scanf ("%d" , & t);
while (t- - ) {
scanf ("%d%d" , & a, & k);
printf ("%d\n" , func(a, k) ! = INF ? func(a, k) : - 1 );
}
return 0 ;
}
cs
닫기
E.Explore space
레이저와 방사능이 좌표로 존재할 때 레이저가 부수지 못한 방사능층의 개수를 구하는 문제이다.
레이저와 방사능 수가 10만이므로 log시간에 처리해 줄 무언가를 생각해줘야 한다.
우선 방사능과 레이저를 전부 입력 받은 뒤 레이저를 기울기순으로 정렬해보자
이 후 방사능의 양쪽 끝의 기울기를 계산하여 binary search를 통하여 해당 방사능을 부수는 레이저가 존재하는지 log 시간에 확인해 준다.
이 후 파괴되지 않은 방사능층의 개수를 출력해주면 된다.
<소스코드 ↓>
열기 닫기
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
#include < cstdio>
#include < algorithm>
#include < vector>
using namespace std ;
struct target {
double x, y, z, w;
};
vector< double > laser;
vector< target> tg;
int n, m, res;
int main() {
scanf ("%d" , & n);
for (int i = 0 ; i < n; i+ + ) {
target t;
scanf ("%lf%lf%lf%lf" , & t.x, & t.y, & t.z, & t.w);
tg.push_back(t);
}
scanf ("%d" , & m);
for (int i = 0 ; i < m; i+ + ) {
double x, y;
scanf ("%lf%lf" , & x, & y);
laser.push_back(y / x);
}
sort(laser.begin(), laser.end());
for (int i = 0 ; i < n; i+ + ) {
double l, r;
l = tg[i].y / tg[i].x, r = tg[i].w / tg[i].z;
if (l > r)swap(l, r);
int idx = lower_bound(laser.begin(), laser.end(), l) - laser.begin();
if (idx ! = laser.size() & & laser[idx] < = r)
continue ;
res+ + ;
}
printf ("%d\n" , res);
return 0 ;
}
cs
닫기
F.제3회 IUPC
N개의 A,B,C가 주어질 때 A X (B의 0부터 C 제곱) 들 중 중복을 제거한 수를 출력하는 문제이다.
얼핏보면 시뮬레이션을 돌린 뒤 set을 통하여 수를 계산해주면 될 것 같지만 계산을 할수록 수가 너무 커지기 때문에 해싱 또는 소인수 분해를 통하여 수를 관리해주어야 한다.
나는 소인수 분해한 수를 정렬 된 vector로 보관하는 방법으로 문제를 해결하였다.
<소스코드 ↓>
열기 닫기
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
#include < cstdio>
#include < algorithm>
#include < set>
#include < vector>
using namespace std ;
int n, a, b, c;
set< vector< int > > st;
vector< int > getprime(int x) {
vector< int > ret;
for (int i = 2 ; i < = sqrt(x); i+ + ) {
while (! (x%i)) {
ret.push_back(i);
x / = i;
}
}
if (x ! = 1 )
ret.push_back(x);
sort(ret.begin(), ret.end());
return ret;
}
int main() {
scanf ("%d" , & n);
for (int i = 0 ; i < n; i+ + ) {
scanf ("%d%d%d" , & a, & b, & c);
vector< int > pa = getprime(a);
vector< int > pb = getprime(b);
vector< int > pc;
st.insert(pa);
for (int i = 0 ; i < c; i+ + ) {
pc.resize(pa.size() + pb.size());
merge(pa.begin(), pa.end(), pb.begin(), pb.end(), pc.begin());
st.insert(pc);
pa = pc;
pc.clear();
}
}
printf ("%d\n" , st.size());
return 0 ;
}
cs
닫기
