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 신기한 물체

모르겠다.