Coding Memorandum

幸運なことにTopCoderで賞金を頂くことができました。しかも$650も！
チーム戦のMarathon Matchということで，チーム分けに恵まれたのがラッキーでした。

そんなわけで受取の必要書類を揃えるため，Affidavit（宣誓供述書）の公証を受けにアメリカ大使館に行ってきました。この辺のところをメモしておきます。

・アメリカ大使館で公証を受けるためには予約が必要となります。アメリカ大使館のページから行います。私が行ったときには３日後以降しか空いていませんでした。わりと混んでいるようです。
・大使館では敷地入り口にセキュリティチェックの部屋があります。部屋の前に警察官がいて，公証だと告げると予約表のチェックを受けました。
・アメリカ大使館では，アメリカ市民サービス（公証はこっち）とVISAのサービスが行われていて，並ぶ列や入り口が分かれるような形になっていました。混んでいるときは，案内板に注意した方が良さそうです。（VISAの方は混むことがあるそうです）
・セキュリティチェックでは，携帯・その他電子機器を預けます。
・中庭を進んで大使館の入り口を入ると，案内の方がいて窓口を教えてくれます。
・２０分程待って，窓口に呼ばれました。パスポートとAffidavitを提出すると，会計用紙をもらうので会計窓口で$30払います。領収書をもらうので，それを窓口へ置いておきます。
・しばらく待つと，公証人（？）から呼ばれます。窓口越しに，右手を上げて宣誓しサインをします。向こうもサインをしてエンボスの判が押されて返されます。以上で完了です。

このAffidavitとW-8BEN(免税書類)をTopCoderへ郵送すれば良いようです。ちなみに，航空便で￥110でした。

CUDA Superhero Challenge 2 に参加しました。

CUDAには前々から興味があったのですが，なかなか触れる機会もなく，そんな中でASCII.technologiesの先月号でGPGPU特集があり，TopCoderでもタイミング良くCUDAのコンテストが行われるということで，今回チャレンジしてみました。ちなみに，ASCII.Technologiesの記事はHack The Cellでお馴染みの(株)フィックスターズさんによるものでした。

 今回の問題は，N台の飛行機のメンテナンスを行う問題で，1日に1台，飛行機は1日ごとにいる位置が異なるという条件でメンテナンスする人の移動距離をより少なくする順番を求めよというものでした。巡回セールスマン問題で，訪問する度に都市がシャッフルされるような問題です。

今回はCUDAのコンテストということで，如何に多くの経路を評価することができるかがポイントなのだろうと考えました。全通りはN!（30<=N<=100）なので，CUDAと言えども現実的ではないように思います。
色々考えたのち，動的計画法的なアプローチで行くことにしました。完全な動的計画法を実行すると，最大で100C50個の中間値を管理しなければならないため，かなり端折って各ステップでTop-Mのケースのみを拾っていくような方法を考えてみました。Tesla（C1060）の性能が未知なため，Mを計算時間の調整項目として残せる点も良いかと考えました。（最終的には，このMをどう決めるかで悩むことになるのですが･･･）

 結果としては最後にスコアが伸びず，暫定２０位で終えました。 本業が忙しい中では頑張ったのではないかと思います。おかげで土日を丸々つぶしてしまいましたが･･･

 今回，Teslaの計算パワーのすごさを体感しました。ローカルPC（CUDA DeviceEmulationですが）では実行が完了するのを待てないぐらいものが，１０数秒で終わります。コードを書き始めてから知ったのですが，C1060というのは演算コアが２４０個もあるんですね。これは先に知っておくべきだったと後悔しています。結局，半分も使い切れないコードとなってしまいました。たかだか十数個程度だろうと甘く見てました。

Superhero Challenge 3があれば，またチャレンジしたいと思います。

NASA-TopCoder Challengeに参加してました。
いつものMarathon Matchとは異なり，20人で1グループとなって，グループ内で競うというものでした。しかも，1グループに$1,000の賞金が設定されるという大判振る舞い。参加人数は480人までということで抽選となりましたが，幸運なことに参加資格を頂きました。

Group Aは個人戦，Grooup Bは5人１チームのチーム戦（４チーム対抗）という形で，私はGroup Bでした。割り当てられたグループが良かったため，スコアはほどほど（576.83 ： トップ集団は700点台）ですがグループトップの位置に付けています。Final Testの結果が楽しみです。

チーム毎にPrivate Forumが設定されているので，拙い英語でいろいろ書いてみたのですが，他のメンバは誰も書き込んでこない状況で残念でした。チーム戦であることを楽しみたかったのですが･･･
最終日に「LP-relaxation法で試してるけど（動いていないので）何か良いアイデアはないか」的な書き込みがあったのですが，最終日は自分のコードで手一杯で返信する余裕がありませんでした。もう少し早く書いてくれれば，良い議論のネタになったと思うのですが。この方は最後までsubmitしなかったので，完成しなかったようです。

今回のコードでは，（以前のMarathon Matchでも経験した記憶があることですが）VC++とG++で計算結果が異なる問題に行き当たりました。 いつもであれば細かい部分は気にしないのですが，今回はちょっとモチベーションも高いため，追跡してみました。手元にCDがあったUbuntuを入れてG++環境を急遽構築してみました。（最近のLinuxは何の苦労もなくセットアップ可能なんですね）

分かってしまえば単純なことだったのですが，STLのsortの実装が異なっていて同点のときの並び順が異なるというだけでした。知っていたことですが，机上では見抜けませんでした。

 今回の参加者はT-シャツが貰えるそうで，こちらも楽しみです。 

Marathon Match AgentMatching に参戦しました。

Event Calenderにも予定がなく，急に始まったこのMarathon Matchでしたが，折りしも夏休みに入ったところであり，また今回の問題は機械学習ということで学生のころの研究分野でしたので，何とかなるかもと淡い期待を持ちつつ参加することにしました。（賞金付きというのも魅力的でしたが）

しかしながら，コトはそんなに上手く運ばず，結構な時間をかけながら紆余曲折の末，何とかそれなりのスコアに到達できたというところで終わりました･･･

本問題の解法として，まずは機械学習ということでニューラルネットかID3（C45) かというのが頭に浮かんでいました。教師データが離散値であるのでID3で行けるのではと思い，試してみました。
ID3についてはWikipediaを参照してみてください。（そんなにメジャーなものではないと思っていたので，項目があることに驚きでした）
    http://ja.wikipedia.org/wiki/ID3

この方法での 結果はほとんどスコアが伸びず，ある程度手を入れてみたものの，わりと早めに見切りを付けることとなりました。教師データにノイズが乗っていることからも難しいだろうなとの予測もありましたので。
 

続いてはサポートベクターマシンにトライしてみました。サポートベクターマシンは，ここ最近よく目にするようになって，一度はさわってみたいなと思っていたので丁度良い機会でした。非線形の分類ができて，ノイズにも(ある程度)対応するとのことでしたので，結構の良い結果を得られるのではと期待を持って取り組んでみました。
サポートベクターマシンについては実装に関する資料がほとんどなく（理論の解説は多く見受けられますが），インプリにはかなり苦労させられました。この知見については，別記事でご紹介できればと思っています。

しかしながら，こちらの結果も芳しくなく，しかもID3よりも悪いという想定外の結果となってしまいました。誤差の許容パラメータが厳しすぎると学習が収束せず，緩くすると全て「真」（あるいは「偽」）となってしまい，収拾がつかない状況に。
このような結果を受け，今回の学習データは矛盾するデータが多く，分類するという考え方がそぐわないのだろうとの考えに至りました。
 

残り時間も少なくなり，残り2日しかない中で確率ベースのアルゴリズムを考えてみました。
学習データの重要そうな項目について，その各項目の値ごとに「真」となる確率を求めておきます。テストデータに対しては，各値ごとに「真」となる確率を引きだし，その確率値の重み付き和を求め，出力としてみました。（重みはシミュレーションで学習させる）

これが（やっつけアルゴリズムでありながら）意外なことに上手く行き，何とか満足できる位置までスコアアップしました。
もっと早くこれに到達できていれば，もう少し上位を狙えたような気がします。
 

久々のSRM。
このところ仕事が忙しく，なかなか時間が合いませんでした。

久しぶりに参加した今回のSRMはケアレスミスでスコアを大きく落とす展開となり，散々な結果となってしまいました。

Div2 500のCubeWalkingの問題(Div1 250と同じ)では，進行方向をx,y座標の増分dx，dyで管理してみたのですが，進行方向の90℃回転で次のようなコードを書いてしまいました･･･

if( *it == 'L' ){
    dx = dy;
    dy = -dx;
}else{  // *it=='R'
    dx = -dy;
    dy = dx;
}

250問題の方は終了間際でミスに気付き，再submitで最低点。

1000点問題は結構なコード量になりそうでしたので，心が折れました。