---
tags: IOI
---
# IOI2010 Day1-4 言語 (Language)

マラソン:running:

## 問題

https://oj.uz/problem/view/IOI10_languages
https://www.ioi-jp.org/ioi/2010/tasks/tasks_jpn/day1/t4_language/index.html

IOI では 56 の言語が使われています。 それぞれの言語の Wikipedia からランダムにページを選び、本文の連続する 100 文字を取り出してデータセットを作りました。
データセットでは、 1 つの文字に 1 〜 65535 の値がランダムに、 1 つの言語に 0 ~ 55 の値がランダムに割り振られています。
- 長さ 100 の数列 $E$ が与えられる → 言語を予測する → 答えが返ってくる

を 10000 回繰り返すとき、どれだけ正確に予想できるでしょうか？

| 正解率 | 得点 |
| ------- | ------ |
| 30.00 % | 30 点 |
| 38.34 % | 40 点 |
| 47.12 % | 50 点 |
| 55.88 % | 60 点 |
| 64.65 % | 70 点 |
| 73.43 % | 80 点 |
| 82.20 % | 90 点 |
| 90.97 % | 100 点 |
| 99.74 % | 110 点 |

Rocchio と呼ばれる手法があり、この手法は約 40 % の正解率になります。

> for e in $E$ {
> 　　for l in 0 .. 56 {
> 　　　　similarity[l] += (言語 l の文章に e が出現したか);
> 　　}
> }
> return argmax(similarity)

## N-gram

どの数がどの文字に対応するかがわからないので、文字の出現回数を上手く使って予測する必要があります。
各言語でしか使われない文字や単語があるはずなのでそれを上手く取り出しましょう。

文字列の N-gram とは、その文字列の長さ N の部分文字列全体のことをいいます。
上の Rocchio という手法では mono-gram についてしか見ていませんが、これを各 N-gram ごとにやってみましょう。

> for N in 1 .. 5 {
> 　　for e in N-gram$(E)$ {
> 　　　　for l in 0 .. 56 {
> 　　　　　　similarity[l] += (言語 l の文章に e が出現した回数);
> 　　　　}
> 　　}
> }
> return argmax(similarity)

N が 5 以上のものは面倒かつ効果が薄いので 4 で打ち切ります
1 つの言語でしか出現していない文字の効果を高めたいので、出現回数で割ります

> for N in 1 .. 5 {
> 　　for e in N-gram$(E)$ {
> 　　　　for l in 0 .. 56 {
> 　　　　　　similarity[l] += (言語 l の文章に e が出現した回数) / ( e が出現した回数);
> 　　　　}
> 　　}
> }
> return argmax(similarity)

N が大きい方が重要そうなので、係数 $C_N$ を掛けます

> for N in 1 .. 5 {
> 　　for e in N-gram$(E)$ {
> 　　　　for l in 0 .. 56 {
> 　　　　　　similarity[l] += (言語 l の文章に e が出現した回数) / ( e が出現した回数) * $C_N$;
> 　　　　}
> 　　}
> }
> return argmax(similarity)

係数を山登りで決めて、完成です

## 実装

https://oj.uz/submission/292157

92.27 %
101 点

#include "grader.h"
#include "lang.h"
#include <bits/stdc++.h>
using namespace std;
 
#define C(n) \
auto comp ## n = [](const array<int, n>& a){ uint64_t ans = 0; for(int i : a){ ans <<= 16; ans |= i; } return ans; };\
unordered_map<array<int, n>, array<int, 56>, decltype(comp ## n)> c ## n(1 << 17, comp ## n)
C(1); // mono-gram の頻度
C(2); // bi-gram の頻度
C(3); // tri-gram の頻度
C(4); // tetra-gram の頻度
array<double, 56> cnt;

const double A = 85.69436, B = 1066.034, C = 143.9561, D = 1719.933; // 係数

void excerpt(int *E) {
   cnt.fill(0);
   for(int i = 0; i <= 100 - 1; i++){
      auto& c = c1[{E[i]}];
      int s = accumulate(c.begin(), c.end(), 0);
      if(!s) continue;
      for(int i = 0; i < 56; i++) cnt[i] += double(c[i]) / s * A;
   }
   for(int i = 0; i <= 100 - 2; i++){
      auto& c = c2[{E[i], E[i + 1]}];
      int s = accumulate(c.begin(), c.end(), 0);
      if(!s) continue;
      for(int i = 0; i < 56; i++) cnt[i] += double(c[i]) / s * B;
   }
   for(int i = 0; i <= 100 - 3; i++){
      auto& c = c3[{E[i], E[i + 1], E[i + 2]}];
      int s = accumulate(c.begin(), c.end(), 0);
      if(!s) continue;
      for(int i = 0; i < 56; i++) cnt[i] += double(c[i]) / s * C;
   }
   for(int i = 0; i <= 100 - 4; i++){
      auto& c = c4[{E[i], E[i + 1], E[i + 2], E[i + 3]}];
      int s = accumulate(c.begin(), c.end(), 0);
      if(!s) continue;
      for(int i = 0; i < 56; i++) cnt[i] += double(c[i]) / s * D;
   }
 
   int ans = language(max_element(cnt.begin(), cnt.end()) - cnt.begin());
 
   for(int i = 0; i <= 100 - 1; i++){ // mono-gram を数える
      auto& c = c1[{E[i]}];
      c[ans]++;
   }
   for(int i = 0; i <= 100 - 2; i++){ // bi-gram を数える
      auto& c = c2[{E[i], E[i + 1]}];
      c[ans]++;
   }
   for(int i = 0; i <= 100 - 3; i++){ // tri-gram を数える
      auto& c = c3[{E[i], E[i + 1], E[i + 2]}];
      c[ans]++;
   }
   for(int i = 0; i <= 100 - 4; i++){ // tetra-gram を数える
      auto& c = c4[{E[i], E[i + 1], E[i + 2], E[i + 3]}];
      c[ans]++;
   }
}