언어
시간 제한10초메모리 제한256 MB
100개 기호로 이루어진 발췌문의 언어를 추측하고, 매 추측마다 서버가 돌려주는 정답으로 학습하며 10000회 동안 정확도를 최대화한다.
문제
각 위키백과 발췌문의 언어를 차례로 추측하는 대화형 프로그램을 작성해야 한다. 추측할 때마다 프로그램은 정답을 받으므로, 오래 할수록 더 나은 추측을 하도록 학습할 수 있다.
각 언어는 0과 55 사이의 수 L로 표현된다. 각 발췌문은 정확히 100개의 기호로 이루어지며, 1과 65,535 사이의 정수 100개로 구성된 배열 E로 표현된다. 1과 65,535 사이의 이 정수들은 임의로 배정되었고 어떤 표준 인코딩에도 대응하지 않는다.
위에서 설명한 대로 위키백과 발췌문을 나타내는 100개의 수 배열 E가 주어질 때, 프로시저 excerpt(E)를 구현해야 한다. 구현은 E가 추출된 위키백과 판의 언어에 대한 추측 L로 language(L)을 한 번 호출해야 한다. 채점 서버는 language(L)을 구현하며, 추측을 채점하고 올바른 언어를 반환한다. 즉, language(L) = L이면 추측이 맞은 것이다.
채점 서버는 입력 파일의 각 발췌문에 대해 한 번씩, 총 10,000번 excerpt(E)를 호출한다. 구현의 정확도는 excerpt(E)가 올바른 언어를 추측한 발췌문의 비율이다.
어떤 방법을 써도 이 문제를 풀 수 있다. Rocchio의 방법은 약 0.4의 정확도를 내는 접근법이다. Rocchio의 방법은 지금까지 본 각 언어 L에 대한 E의 유사도를 계산하고, 가장 유사한 언어를 고른다. 유사도는 E의 서로 다른 기호 중 언어 L의 이전 발췌문 어디에든 나타나는 기호의 총 개수로 정의된다.
입력 데이터는 실제 위키백과 문서에서 내려받은 것이며, 잘못된 문자가 몇 개 있거나 텍스트 조각이 있을 수 있다. 이는 예상된 일이며 문제의 일부이다.