Day 1 Task 4: 言語 (Language)

あなたは，Wikipedia の抜粋（下の例を参照）が順に与えられたときに，各々の抜粋がどの言語で書かれているかを推測する応答型のプログラムを書くことになった． プログラムは抜粋がどの言語で書かれたかを推測するたびに，正解を得ることが出来る． そのため長時間の実行後には，学習によって良い推測を行えるかもしれない．

それぞれの言語は 0 以上 55 以下の数字Lによって表される． それぞれの抜粋はちょうど 100 個のシンボルからなり，1 以上 65 535 以下の100個の整数からなる配列 E で表される． 1 以上 65 535 以下の整数はでたらめに割り当てられ，何らかの標準的な符号化には一致しない．

プロシージャー excerpt(E) を実装せよ． E は 100 個の数字からなる配列であり，Wikipedia の抜粋を上述の決まりに従って表したものである． あなたの実装は E が抽出された版の Wikipedia の言語 L を推測し language(L) を1度だけ呼ぶ必要がある． 採点サーバーは language(L) を実装している． language(L) はあなたの推測を採点し，正解の言語を返す． つまり，language(L) = L ならば推測は正解である．

採点サーバーは入力ファイル内の各抜粋ごとに1度，全部で 10 000 回 excerpt(E) を呼び出す．あなたの実装の正確さは excerpt(E) が正解の言語を推測した割合である．

あなたはこの問題を解くためにどのような手法を使っても良い． Rocchio と呼ばれる手法があり，この手法はおおよそ0.4の正確さとなる． この手法はそれぞれの言語Lに対して抜粋Eの類似度を計算し，最も似ている言語を選ぶ方式である． 言語Lに対する抜粋Eの類似度は，抜粋Eに現れるシンボルで，これまでに言語Lと判明した抜粋のうち少なくとも１つに現れるものの種類の個数と定義される．

入力データは本物の Wikipedia の項目をダウンロードしたものであり，不正な文字や，文章の不正な断片が少し含まれているかもしれない． これは予期されている事であり，課題の一部である．

例

説明のためだけに，56 言語それぞれの版の Wikipedia からの抜粋をテキストで表示したものを以下に示す．
  1. Yshokkie word meestal in Kanada , die noorde van die VSA en in Europa gespeel. Dit is bekend as 'n b
  2. المنتج الحدي Marginal Producer ، وهو المنتج الذي يجعل المنظم لا يكسب ربحا ولا يخسر ويحصل على دخل يكف
  3. "BAKILI" Futbol Klubu 1995-ci ildə Misir Səttаr oğlu Əbilov tərəfindən yаrаdılmış və həvəskаr futbol
  4. Квинт Фулвий Флак (Quintus Fulvius Flaccus; † 205 пр.н.е. ) e политик и генерал на Римската републик
  5. ইন্ডিয়ান ইনস্টিটিউট অফ সোশ্যাল ওয়েলফেয়ার অ্যান্ড বিজনেস ম্যানেজমেন্ট (সংক্ষেপে আইআইএসডব্লিউবিএম )
  6. 5. juni ( lipanj ) ( 5.6. ) je 156. dan godine po gregorijanskom kalendaru (157. u prestupnoj godini
  7. La Caunette és un municipi francès , situat al departament de l' Erau i a la regió de Llenguadoc-Ros
  8. Praha je malé městečko v Texasu , které leží cca 85 km na jihozápad od Austinu . Bylo založeno
  9. Graeme Allen Brown (født 9. april 1979 i Darwin , Northern Territory , Australien ) er en australsk
  10. Der Plattiger Habach ( 3.214  m ü. A. , nach anderen Angaben nur 3.207  m [1] )
  11. Το Νησί Γκρέιτ Μπάρριερ ( Αγγλικά : Great Barrier Island , Μαορί : Motu Aotea ) είναι νησί στα βόρει
  12. Sid Bernstein Presents... is a 2010 feature-length documentary film by directors Jason Ressler and E
  13. El término latino lex loci celebrationis aplicado al derecho internacional privado quiere decir: "le
  14. Apollo 5 oli kosmoselaev , mis sooritas Apollo programmi teise mehitamata lennu. Lennu käigus testit
  15. سیارک ۱۳۵۰ (به انگلیسی : 1350 Rosselia ، نامگذاری :1934TA )‏ هزار و سیصد و پنجاهمین سیارک کشف شده‌اس
  16. V. I. Beretti (myös Vikenty Ivanovitš Beretti , alk. Vincent Beretti ; 1781 Milano Italia – 18. elok
  17. Le 5 e bataillon de parachutistes vietnamiens (ou 5 e BPVN ou encore 5 e Bawouan ) est une unité par
  18. Amina Sarauniyar Zazzau,, wadda ta rayu daga shekarar 1533 zuwa 1610, ɗaya ce daga cikin ‘ya'ya biyu
  19. ב מתמטיקה , השערת רימן היא השערה שהציע בשנת 1859 ה מתמטיקאי ברנרד רימן , מגדולי המתמטיקאים של אותה ע
  20. Sudski proces Doe protiv Boltona je sudski proces iz 1973 . godine kojim je američki Vrhovni sud uki
  21. Owen Cunningham Wilson ( 1968 . november 18. , Dallas , Texas , Egyesült Államok ) amerikai színész
  22. Հայ Կաթողիկե Եկեղեցին պատկանում է Արևելյան Կաթոլիկ Եկեղեցիներին և այսպիսով ենթարկվում է Հռոմի Պապի ա
  23. Dionysios dari Halicarnassus ( Bahasa Yunani : Διονύσιος Ἀλεξάνδρου Ἀλικαρνᾱσσεύς , Dionysios putra
  24. Nnamdi "Zik" Azikiwe , bu onye isi-ala izizi Nijiria nwere. Ochichi ya bidolu na afo 1954 welu ruo n
  25. La Riserva naturale orientata Serre della Pizzuta è un'area protetta del dipartimento Regionale di S
  26. 石橋和義 （いしばし かずよし/まさよし，生没年不詳）は， �詳． 石橋氏 初代当主．初名氏義． 尾張 三郎を通称とし，官途は， 左近将監 → 三河守 → 左衛門佐 ． 足利直義
  27. კორბინ ბლიუ ( ინგლ. Corbin Bleu ; დ. 21 თებერვალი , 1989 , დაბადების ადგილი ბრუკლინი , ნიუ-იორკი , ა
  28. Та́рья Ка́арина Ха́лонен (Tarja Kaarina Halonen)); 24 желтоқсан , 1943 , Каллио , Хельсинки , Финлан
  29. 딜롱 ( Dilong )은 중국 랴오닝(Liaoning) 지방의 익시안층(Yixian Formation)에서 온전한 4구의 화석으로 발견되었다. 이 공룡은 가장 원시적인 초기의 티
  30. Сүймөнкул Чокморов - советтик актёр. Жетинин айынын 9 (ноябрь) 1939-жылы, Фрунзе шаарын жанындагы Чо
  31. D' Mirjam vun Abellin war eng Nonn a Mystikerin , och " Maria vum gekräizegte Jesus " genannt. Si as
  32. Panopea abrupta ( angl. Geoduck ) - jūrinių dvigeldžių moliuskų rūšis, priklausanti Hiatellidae šeim
  33. "Dzimis Latvijā" ir Liepājas dueta Fomins & Kleins 2004 . gada 23. februārī izdotais otrais albu
  34. I Ludwik Lejzer Zamenhof dia dokotera mpijery maso nipetraka any Polonia . Fantantsika izy ankehitri
  35. Седумстотини милиони малечки алвеоли во белите дробови , всушност се шупливи чаури - алвеоли прекрие
  36. Энэхүү шувуу нь Бутан , Хятад , Гонконг , Энэтхэг , Пакистан , Иран , Япон , Казакстан , Солонгос ,
  37. भारतातील महाराष्ट्र राज्याच्या नागपूर पासुन २१६ कि.मी. दूर असलेले एक गाव. ते वैनगंगा नदीच्या काठावर
  38. De Slotervaart was oorspronkelijk de waterweg die sinds de Middeleeuwen het dorp Sloten verbond met
  39. Macierz S (macierz rozpraszania, od ang. scattering matrix ) jest centralnym elementem w mechanice k
  40. A Hora do Rush 3 ( Rush Hour 3 , no original) é o terceiro filme da franquia Rush Hour . Dirigido po
  41. Coordonate : 51°34′0″N 12°3′0″E  /  51.56667 , 12.05 Brachstedt este o comună din landul Saxonia-A
  42. Гробницы императоров династии Мин и Цин — памятник Всемирного наследия ЮНЕСКО , состоящий из несколь
  43. Kovalentni radijus atoma - ponekad se naziva i valentni radijus. Kovalentni radijus je srednje rasto
  44. Koniecpol je mesto v Poľsku v Sliezskom vojvodstve v okrese Powiat częstochowski v rovnomennej gmine
  45. Hoxhë Vokrri vije nga Shqipëria ishte një klerik shqiptar i cili luftonte për Çështjën Kombëtare . A
  46. Гурдијеље је насеље у општини Тутин у Рашком округу . Према попису из 2002. било је 93 становника (п
  47. Underhållsstöd betalas ut av Försäkringskassan (FK) till en förälder som är vårdnadshavare och bor e
  48. இந்தியாவின் தேசிய நெடுஞ்சாலைகள் நடுவண் அரசின் தேசிய நெடுஞ்சாலைத் துறையால் பராமரிக்கப்படுகின்றன. பெரு
  49. Дар он зиндаги .маишат ,фаолияти мехнати,муборизаи ичтимои, русуму омол, хислат ва эхсосоти халк ифо
  50. ไฟทอฟธอรา อินเฟสทันส ( อังกฤษ : Phytophthora infestans ) คือเชื้อ ราโอโอไมซีท หรือ ราน้ำ ที่เป็นสาเห
  51. ABUL FAWARIS BERRANY - 11. asyrda Orta Aziýadaky oguz taýpalarynyň berrany dinastiýasynyň wekili. Ol
  52. Egemenlik ya da hâkimiyet , bir toprak parçası ya da mekan üzerindeki kural koyma gücü ve hukuk yara
  53. Темне фентезі (від англ. Dark Fantasy - темне, похмуре фентезі ) - піджанр літератури, який включає
  54. Paris By Night 84: In Atlanta - Passport to Music & Fashion (Âm nhạc và Thời trang) là chương tr
  55. ISO 3166-2:GU ni akoole ninu ISO 3166-2 , apa opagun ISO 3166 ti International Organization for Stan
  56. 下卡姆斯克 （ 俄文 ： Нижнека́мск ； 韃靼語 ： Түбән Кама/Tübän Kama ）是 俄羅斯 韃靼斯坦共和國 東北部的一個城市，位於 卡馬河 南岸． 2002年 人口22

サンプル入力ファイル grader.in.1 はこのような例を 10 000 個含む． サンプルの 56 言語は IOI 2010 において登録された「母国語」である． それぞれの抜粋は 56 言語から無作為に選ばれた言語で書かれている． そして，それぞれの抜粋は対応する版の Wikipedia から無作為に選ばれた項目の最初の段落から取られたものである． ファイルの各行は次を含む

公式の採点プログラムは，サンプルと同様の方法で選んだ 56 言語の Wikipedia からの 10 000 個の抜粋を利用する． しかしながら，採点プログラムはそれぞれの言語に異なる 0 以上 55 以下の数字を割り当て，それぞれのシンボルへ異なる 1 以上 65 535 以下の数字を割り当てる．

小課題 1 [30 点]

あなたが提出したプログラムは，採点サーバー上で 0.3 以上の正確さを達成しなければならない．

小課題 2 [最高80 点]

あなたのスコアは，114 * (α - 0.3) を最も近い整数へ丸めたものである． α はあなたの提出したプログラムの正確さである．

実装の詳細