IOI2010 4번 Language

작성일 | In |

문제 링크

  • https://oj.uz/problem/view/IOI10_languages

문제 출처

  • 2010년 국제 정보 올림피아드 4번(Day1 4번)

풀이

56점 풀이

문제에 나온 Rocchio’s Method를 그대로 구현해주면 56점이 나옵니다.
코드

98점 풀이

문장은 단어 단위로 이루어져 있다고 볼 수 있고, 단어들은 여러 문자가 연속적으로 나열되어있는 문자열입니다.
이 점을 이용해 Rocchio’s Method를 약간 수정해 이전 2~4개의 문자들을 해싱해서 함께 봐주면 대략 98점이 나옵니다.
코드

100점+ 풀이

이제 남은 2점을 위해 다른 방법을 고민해봅시다.
지금까지는 각 언어에 문자(혹은 문자열)이 등장하면 cnt배열의 값을 1로 바꿔주었습니다. 이번에는1로 바꾸는 것이 아닌, 1을 증가시키는 방법을 택해봅시다.
등장 횟수를 구할 때는 해당 언어가 등장한 횟수로 나눠주었습니다.
코드

이렇게 하면 0점에 정확도 2.5%가 나오게 됩니다.
문자(혹은 문자열)의 등장 횟수를 구할 때 해당 언어가 등장한 횟수로 나누는 것이 아닌, 언어 등장 횟수에 로그를 취한 값으로 나눠보았습니다.
코드
2.5%에서 2.7%로 증가했습니다. 그러나 여전히 0점입니다.

cnt배열의 값을 x라고 합시다. 문자(혹은 문자열)의 등장 횟수를 구할 때 x를 더하는 것이 아닌 x/(x+1)을 더해줍니다.
그리고 한 가지 아이디어를 더 추가해봤습니다.
cnt, cnt2, cnt3, cnt4의 값을 더해줄 때 각각 가중치를 줘서 더하는 방법을 선택해봤습니다.
여러 번의 시도를 통해 적절한 가중치를 찾아준다면 100점 혹은 101점을 받을 수 있습니다.
코드

전체 코드

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
#include "grader.h"
#include "lang.h"
#include <bits/stdc++.h>
using namespace std;

const int n = 100, m = 56;
const int mod = 80021;

int cnt[57][80808];
int cnt2[57][80808];
int cnt3[57][80808];
int cnt4[57][80808];
int lan[57];

int f(int a, int b){ //hash2
	long long ret = (long long)a << 16;
	ret |= b;
	ret %= mod;
	return ret;
}

int f(int a, int b, int c){ //hash3
	long long ret = (long long)f(a, b) << 16;
	ret |= c;
	ret %= mod;
	return ret;
}

int f(int a, int b, int c, int d){ //hash4
	long long ret = (long long)f(a, b, c) << 16;
	ret |= d;
	ret %= mod;
	return ret;
}

double f(int x){
	return (double)x / (x + 1);
}

void excerpt(int *arr){
	double mx = 0;
	int idx = 0;
	for(int i=0; i<m; i++){
		double now = 0;
		for(int j=0; j<n; j++){
			now += f(cnt[i][arr[i]]);
			if(j >= n-1) continue;
			now += f(cnt2[i][f(arr[j], arr[j+1])]) * 100;
			if(j >= n-2) continue;
			now += f(cnt3[i][f(arr[j], arr[j+1], arr[j+2])]) * 150;
			if(j >= n-3) continue;
			now += f(cnt4[i][f(arr[j], arr[j+1], arr[j+2], arr[j+3])]) * 100;
		}
		now /= log(lan[i] + 1);
		if(now > mx){
			mx = now; idx = i;
		}
	}

	int ans = language(idx);
	lan[ans]++;
	for(int i=0; i<n; i++){
		cnt[ans][arr[i]]++;
		if(i >= n-1) continue;
		cnt2[ans][f(arr[i], arr[i+1])]++;
		if(i >= n-2) continue;
		cnt3[ans][f(arr[i], arr[i+1], arr[i+2])]++;
		if(i >= n-3) continue;
		cnt4[ans][f(arr[i], arr[i+1], arr[i+2], arr[i+3])]++;
	}
}