COCI(Croatian Open Competition in Informatics) 2009/2010 contest #1
https://www.acmicpc.net/category/detail/83
1. BOJ 2920 음계
음계가 1 2 3 4 5 6 7 8
이면 ascending
, 8 7 6 5 4 3 2 1
이면 descending
을 출력하고, 나머지는 mixed
를 출력한다.
stl vector
비교 연산자로 간결하게 구현할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
vector<int> as = {1,2,3,4,5,6,7,8};
vector<int> ds = {8,7,6,5,4,3,2,1};
vector<int> in(8);
int main(){
for(int i=0;i<8;++i)
scanf("%d",&in[i]);
if(in==as)
printf("ascending");
else if(in==ds)
printf("descending");
else
printf("mixed");
}
2. BOJ 2921 도미노
도미노 위의 숫자는 up
, 밑의 숫자는 down
에 저장하고 Brute Force.
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
int main(){
int n;
scanf("%d",&n);
int ans = 0;
for(int up=0;up<=n;++up)
for(int down=up;down<=n;++down)
ans += up+down;
printf("%d",ans);
return 0;
}
3. BOJ 2922 즐거운 단어
핵심은 “단어에 포함된 밑 줄의 개수는 최대 10개”라는 것이다. 한 알파벳은 L
, L
이 아닌 자음, 모음 세가지로 분류할 수 있다. 밑 줄이 있는 칸에 알파벳이 들어가는 경우는 3가지이므로 전체 경우의 수는 3^10 = 59049
가지이다. 각 단어에 대해 즐거운 단어인지 확인할 때 $O(n)$이 걸리는데 $n$이 충분히 작기 때문에 Brute Force로 해결할 수 있다.
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<bits/stdc++.h>
using namespace std;
bool vowel(char c){
if(c=='A'||c=='E'||c=='I'||c=='O'||c=='U')
return true;
return false;
}
char s[101];
long long solve(int idx,bool L){
long long ret = 0;
for(int i=idx;s[i];++i){
if(s[i]=='_'){
s[i] = 'A';
ret += 5LL*solve(i,L);
s[i] = 'B';
ret + 20LL*solve(i,L);
s[i] = 'L';
ret += solve(i,true);
s[i] = '_';
return ret;
}else{
if(s[i]=='L') L = true;
if(i-2>=0){
if(vowel(s[i]) && vowel(s[i-1]) && vowel(s[i-2]))
return 0LL;
if(!vowel(s[i]) && !vowel(s[i-1]) && !vowel(s[i-2]))
return 0LL;
}
}
}
return L;
}
int main(){
scanf("%s",s);
printf("%lld",solve(0,false));
}
4. BOJ 2923 숫자 게임
모든 $(a_i,b_i)$ 쌍 중 $\max(a_i+b_i)$가 가장 작으려면 $a_i$는 오름차순으로 $b_i$는 내림차순으로 쌍을 지어주면 된다(귀류법으로 간단하게 증명할 수 있다). 문제는 매번 숫자를 추가하고 ‘모든 쌍에 대한 합의 최댓값의 최솟값’을 찾야아 한다.
$N$은 $100\,000$이지만 각 숫자의 범위가 $[1,100]$이므로 우선 $a_i$와 $b_i$를 버킷정렬한 뒤 각 버킷을 유지한다. 버킷을 유지하는 이유는 숫자를 $O(1)$만에 추가할 수 있고, 모든 숫자를 $[1,100]$의 index로 압축해서 다룰 수 있기 때문이다. $A$의 버킷을 오름차순으로, $B$의 버킷을 내림차순으로 이동하면서 모든 $(a_i,b_i)$쌍을 확인할 수 있다. 버킷은 최대 $100$개이기 때문에 각 라운드에 대해 숫자를 추가하고 값을 찾는데 $O(100) = O(1)$가 걸린다. 전체 시간복잡도 $O(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
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> A(101), B(101);
int solve(){
int ret = 0;
vector<int> X=A, Y=B;
for(int i=1, j=100; i<=100 && j>=1;){
if(X[i] < Y[j]){
if(X[i]){
ret = max(ret, i+j);
Y[j] -= X[i];
}
i++;
}else{
if(Y[j]){
ret = max(ret, i+j);
X[i] -= Y[j];
}
j--;
}
}
return ret;
}
int main(){
scanf("%d",&N);
while(N--){
int a, b;
scanf("%d%d",&a,&b);
A[a]++, B[b]++;
printf("%d\n",solve());
}
}
5. BOJ 2924 천재
Successor Graph가 주어질 때, 각 노드가 한 번에 한 개의 간선을 이동한다. $A \sim B$번째까지의 상태에 대해서 $C \sim (N-D)$개의 노드가 처음 상태의 노드와 완전히 일치하는 상태가 몇 개인지 출력한다.
우선 DFS를 하면서 각 노드가 가지는 사이클의 길이를 저장한다(하나의 노드는 길이가 1인 사이클). $C \sim (N-D)$번째 노드들에 대해 사이클 크기의 최소공배수를 찾으면, 몇 번마다 첫 상태와 일치해지는지 알 수 있다. 이로부터 $A \sim B$번째에 몇 번 일치하는지 역시 알 수 있다.
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<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
return b ? gcd(b, a%b) : a;
}
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
int N, A, B, C, D;
int s[500001];
int cnt[500001];
int solve(){
for(int i=1;i<=N;++i)
if(cnt[i]==0){
stack<int> st;
st.push(i);
for(int j=s[i]; j!=i; j=s[j])
st.push(j);
int size = st.size();
for(; !st.empty(); st.pop())
cnt[st.top()] = size;
}
int T = 1;
for(int i=1+C;i<=N-D;++i)
T = lcm(T, cnt[i]);
return (B+T-1)/T - ((A-1)+T-1)/T;
}
int main(){
scanf("%d%d%d%d%d",&N,&A,&B,&C,&D);
for(int i=1;i<=N;++i)
scanf("%d",s+i);
int ans = solve();
printf("%d",ans);
}
6. BOJ 2925 신기한 물체
모르겠다.