生放送「TopCoderでプログラムしてみた」コメントランキング

Competitive Programming (1) Advent Calendar 2018 - Adventar 12日目の記事です。

はじめに

競プロを最初に始めたのが、TopCoderに初参加した、2008年7月18日だそうです。10周年、めでたい!そして、生放送「TopCoderでプログラムしてみた」も、おそらくほぼ10周年。また、放送は、たくさんのコメントによって、支えられています。本当にありがとうございます。

ランキング

ニコニコ生放送時代の、第284回~第2362回だけの集計ですが、コメントをランキングにしてみました。1位のみかんの人さん、4804コメント、どなた?となってしまいました…。たぶん、コメントビューワーとニコ生コメントのフォーマットの変更で、正確にとれていないです…。(krotonさんとskyaozoraさんのコメントが明らかに少ないし、他の方も抜けてそう…)なんで、その辺はご了承ください。
f:id:shindannin:20181212235310p:plain

ひとことコメント

1位 laycrsさん

TopCoderのレッドコーダーより上のクラス、ターゲット経験者。数々の名アドバイスで、わしの競プロ力を引き上げてくれて、本当に感謝じゃ。
f:id:shindannin:20181213013244p:plain

2位 chokudaiさん

誰もが知っているAtCoder社長で、競技者としてもまだまだ一流、というかマラソンマッチはいまだ世界トップクラス。コメントでも本当にお世話になりました。みょんみょん。
f:id:shindannin:20181213013250p:plain

3位 hasiさん

アルゴリズム・マラソンマッチの両方に強い、強豪コーダー。天下一プログラマーコンテストも主催して、現在も、国内の各種オンサイトコンテストに出場するなど、安定して活躍中。

4位 smjsamaさん

しめじたん。きゅうり氏とならび数々のネタツイートで盛り上げたが、レッドコーダーにいたるまでの苦難の道のりにも人々は泣いた。AtCoderに最近復帰したっぽい?

5位 有為さん

いまだに各種コンテストで世界トップの成績を出す、げきつよレッドコーダー。この精進量を長年続けている情熱には頭が下がります。全ての競プロ勢の精進の見本。

6位 nise_nabeさん

各種競プロbot等でも、貢献されているが、競プロにも復帰しましょう。

7位 びびすけさん

一時期に大量のコメントをくださり上位に。現在はアプリ開発を主にされているようです。

8位 hogeover30さん

競プロ界の毒舌エンターテイナーといえばhogeover30さんで、長年楽しませてもらっています。エンジニアではないのがポイント。だけど、ショートコーディング・マラソンマッチに強いので、そういった部分も注目されるべき!

9位 Mi_Sawaさん

初形式のプロコン、 Distributed Code Jamでいきなり世界4位を取るなど、明らかに天才の、レッドコーダー。

10位 krotonさん

おそらく真のコメント量は3位以内に入っていたはず。10年前から今に至るまで、長年競プロ界にいますが、本人自体にはいまだに謎が多い。krotonさんのことはみなさん良く知っている。YukiCoderへの貢献も大きいです。

11位 skyaozoraさん

ICPC銀メダル・TopCoder World Final経験もあり、すごく人当たりがよく競プロ好きなのが伝わってくる上級レッドコーダー。

12位 phylloさん

個人的には、競プロ勢が読みやすい、競プロ以外のトピックのブログがとてもおすすめ。

13位 Respect2Dさん

Respect2Dが主催された立命館大学のICPC合宿は、競プロがそれほど盛んではなかった地域でも合宿が始まる先駆けとなったので、その競プロ界での貢献は本当に大きいと思います。

14位 ぬさん

(どなたでしょうか!ぜひ教えてください!)

15位 yowaさん

マラソンマッチのスタートダッシュに定評があるけど、途中でニコ生・ゲームにいって、そして最後にまた帰ってくるレッドコーダー。おそらくわしと同年齢だと思われます。

おわりに

こう見てみると、コメントされていた方には、息の長い競プロの方が多いですね。これからも、続けていきましょう!一時休止しても、しれっと復活しましょう!

13日目は
bakamingさん→ICPC ボランティアスタッフの仕事内容の話 - kamingのブログ
n_vipさん→「ICPCで使ったエディタについてちょっと書く」
です。お楽しみに!

HACK TO THE FUTURE 2019予選の反省

beta.atcoder.jp
7位/519でした。
今回は、意地でも定番解答にはならない問題をchokudaiさんが作ってくるかなと思ったら、わりと定番だった。見えることを1つ1つ改善していけば、点が増えていきやすいタイプ。
…と思いきや、後半に、いろいろ考察をちゃんとしてれば、加点できる要素があったので、上位から下位まで、実力が出やすい問題だった気もする。
tsukammoさん、chokudaiさん、ありがとうございました!

良かったこと

  • 天才解法を考える誘惑に負けず、簡単なところから行ったのが良かった
  • 決勝に出れないのは分かっていたけど、ちゃんと最後までがんばった。もう衰える一方の年齢なので、老化防止のために、がんばるべきときにがんばるのは重要。

反省すべきこと

  • 残り2時間で伸びなかったのだけど、条件が変わった後の再考察が足りなかった気がする。
    • 焼きなまし法のマスの状態遷移の調整(開始5時間経過あたり)で、"#TD"はいらないということに気づく。ここで、TD#がなくなったことで問題の条件が大きくかわったので、高速化できる要素等がないか改めて考えるべき。今回の場合、TD#がなくなったことにより、命令Sはマスが.LRどれでも直進1歩になったので、マス変更の影響がなくなる。
  • 2Dフィールドで、何かを動かすというのは、マラソンマッチでは定番。それなのに、経路を圧縮するのを思いつかないのは、ダメ。
  • せめて焼きなましの温度調整は、自動化したほうが良かった気がする。30ケースで軽いからと、自動化しなかった。
  • 一部ソースコードが大変に汚い(ムダなif文など)。コード汚いと、基本遅いし、また、いろいろ試すのをためらう原因になるので、ちゃんと書きましょう。

解法

マスを'..LR'の割合で遷移させる焼きなまし法。10万ループぐらい。5度→0度で線形変化。評価関数はスコアのまま。

やったこと

  • 変更マスを通ったロボットだけ、経路を更新する。
  • ロボット経路を保存して、ロボットの途中位置から計算
  • マスは1次元配列で持つ
  • 遷移状態の調整。TD#を使わない。
  • 焼きなまし、変化スコアが悪くなったら計算途中早期打ち切り。
    • わりと重要テクニックで。これで焼きなまし回数が2万→10万ぐらいまで増え、13万到達。

やったけどボツ

  • 中央付近にLR少なめ
  • 中央付近はあまり変えない
  • ロボット0の箇所の評価点を、最初は高めに
  • 初期盤面を、高スコアのときの割合の'L''R'に合わせて配置

やらずにボツ

  • ロボットが4個・5個重なるケースにわずかに加点。そもそも、初期状態でも、ほぼ4,5がなかった。でも、やって損はなかったのでは。
  • 'S'の数の偶奇でロボットを分ける(壁にぶつかると無意味)

気づかなかったこと

  • 移動コマンドの圧縮。
  • 変更マスを通り、回転するロボットだけの経路を更新する。(上記の説明)
  • 初期L盤面。


  • kimiyukiさんの解答によると、「中央にDで縦棒を引いて土管のようなものを作るとLが実質小さくなるので速い」。kimiyukiさん、面白い形状をつくった改善が得意な印象があります。

最重要

復習しないとムダ。復習しないとムダ。復習しないとムダ。

Marathon Match 100 のゴミメモ!

下書きで終わっていた記事が、残っていました。ゴミメモのままでしかないのですが、脱線に至るまでの経緯が、今見るとおもしろかったので、そのまま投稿。



50位以内だと、懐かしの旧TopCoder時代のTシャツがもらえるマッチでした。まだ現役なので、老兵どもに負けるわけにはいかないのじゃ!

結果:76位/280(遠くへ行きたいです)

最初のメモ(開始2日目)

当時のメモで、あまりよく覚えてないのですが…。

ファーストインプレッション

  • 近くからしかとらない・縦しかとらない・横しかとらないという条件であれば、いろいろできる
  • 斜めどりはかなり難しい。
  • ダイヤに穴をあけるようにしても、端からきれいにとっても、取れる箇所はほとんど増えない。
  • とったことにより、どれが取れるようになるかの分析が最重要。
  • 距離を限定して焼きなましするアイディアは面白いかもしれない。ただ後半の焼きなましは疑問。
  • ビジュアライザ、最終的にどれとどれをペアで取ったのかは、見たいかも。
  • 無害でとれる
  • ハマり形(はまり形を事前に知ってれば、避けたり、評価値に入れたりすることも可能。)
  • 焼きなまし解法。
  • 遅延セグ木

なんか、うまい取り方を考えようとしてたっぽいですね!(なんで遅延セグ木と書いてるんでしょう…)

反省点:ファーストインプレッションの前に簡単な解法を提出せよ!!

まず、この問題のポイントとして、ほとんどのケースで全部とれます。最初に簡単にそれに気づくはずなのに、その条件なしで考えはじめると、複雑な条件で考えないといけなくなります。無駄に時間がすぎる。

あ、でも、いつも簡単な解法をやらずに失敗しているので、今回は絶対に簡単な解法を書こうと思ったんですよ。でも、なぜか感覚が麻痺していて、

  • せめて貪欲法で書きたいなぁ
  • なんらかの評価関数がほしいなぁ
  • これは取れる個数ができるだけ多くなるように
  • めっちゃ重くならない?
  • というか、これはどこから取るのがいいんだろう?
  • 考察へ移行

という感じで、簡単な解法すら思いつかず、なんか脱線するわけですね、自分をコントロールできない!すでに自我がない!あなたの生きている意味は?

そういうときは、ランダム!O(1)で最強!!
というか、超簡単な解法リストでも作って、機械的にやったほうがいいような気もしてきました。思いつかないんだから。












ファーストインプレッションの前に、簡単な解法

ランダムでとるのが思いつかないんですね…簡単な解法



(ビームサーチ解は捨てる!)

焼きなまし法(最終日)

評価関数

  • 解決されていないやつは、後半にとるやつのほうが被害が少ない。
  • エリアが広いこと自体をマイナスとしてもいいかも。(すぐに他のやつが入りこむので)

評価差分

囲われフラグは、orderは無視したもの。

  • 全盤面評価はひどいので直す。

- Swap Pos -> それぞれのRectごとに、スコアをキャッシュしておく。Rect別再計算
   →Orderも考えると、
→今囲んでいるやつ、各点の囲われフラグを解除
→新しく囲んだら、各点に囲んでいるフラグを追加

- Order change -> OrderをかえたRectの再計算。囲われているRectに対して+1,-1
点ごとに、囲われているRectを持つ必要がある。→これは問題!!!

 - Order Changeはなしにして、定期的にOrder計算と最終結果計算を行う方法はあるかも。
  面積でソートすれば、それなりに



- そもそも距離2のは無条件にとって良い。order無意味。

- Orderほんと必要?一意に決まるのに。
 - 分割エリアごと orderなら毎回

  • Forward形式に変更

近傍

  • SwapOrderをChange Orderにする(orderはfloatかdouble)
  • 移動をprogression ratioに合わせて、徐々に小さく(Swap Pos・Change Order両方)
  • Posを移動面積距離が大きい順にソートして、近くしか移動
  • だめな部分を狙って変更する?

温度管理
→ats式がよさそう。

大きい近傍

  • 分割統治(やるなら、端からとったほうが良さげ)

わるあがき

  • はじを優先的にとるランダム
  • 後半単純に遅いかも。
  • 失敗したやつを優先的のとるランダム(これは簡単なので、先にやっていいかも)
  • 焼きなましの結果を使う
  • 高速化版ランダムGreedy解法
  • ランダム途中からスタート解法

初期解

  • 最寄りペアからスタート
  • 貪欲解からスタートのほうがいいのでは!?まぎれが少ないし、一定の得点は保証される。逆より全然良い。ただし、

電ファミニコゲーマーの、手動ディープラーニング記事について

電ファミニコゲーマーで「1987年に手動でディープラーニングをしていた驚異の麻雀ゲームがあった」
news.denfaminicogamer.jp
という記事が多くの人に読まれたのですが、実際の内容はディープラーニングではありません。にもかかわらず、ディープラーニングというバズワードを持ってくる釣りは良くないという話です。

これについて、はてなブックマークなどを見ると、何割かの方は、おかしいということには気づいたようですが、特に修正される様子はありません。また、このインタビューを企画した、三宅陽一郎氏は、日本でゲームAIの第一人者として知られてます。おそらく、日本のゲーム開発者は物申しにくいと思うので、自分が書きました。

何が間違っているか?

  • 手動ディープラーニングではなく、評価関数の手動調整である」という説明で十分だと思います。例えば、宮路氏自身が良い動作に対するなんらか評価方法を持っていたとして、それに対して「手動山登り法」「手動焼きなまし法」等ということなら特に問題ないですが…。
    • パラメータ調整で、教師つき学習の手法をとることもできます。ただ、それをディープラーニングというのであれば、まだ無理な解釈をしないといけない点が4つぐらいあり、普通に考えると最適化をしたとしか思えません。
    • また、そもそも論として、評価関数を使った場合、たいていの人がゲームの結果をみてパラメータを調整するという作業を行います。これを手動ディープラーニングと認めると、おそらく1980年代からその他のゲームも手動ディープラーニングしていた!という話になってしまいます。
  • 些末ですが、記事にでてくるメタAIは、三宅氏がよく使う分類に基づけば、メタAIではなく、キャラクターAIでしょう。キャラクターの中で閉じているので。

良い点・同情できる点

  • インタビューの内容自体は興味深く素晴らしいと思います*1。 また、企画を提案した三宅氏も、ゲームAIのエヴァンジェリストとして、大変評価できます。
  • インタビューということで、宮路氏に気分よく話してもらわなければならないという事情は理解できます。仮に「手動でディープラーニングしてたんですよ」「いいえ。これは評価関数を手動調整しているだけで、評価関数(=効用)は、1980 年代から現在に至るまで継続的に用いられています。*2」と答えたら、それは宮路氏が気分を悪くするでしょうし。でもまぁ、やんわり何か指摘することはできたとも思いますが。

なぜ問題なのか?

しかし、これらを加味したとしても、わざわざ間違っている部分をタイトルに持ってきて、釣るのはどうなのか。おそらくタイトルが普通であれば、「宮路氏はディープラーニングを勘違いしており、まぁこれは評価関数の手動調整だけれども、それでも内容は大変素晴らしい」で、特に問題なく終わったでしょう。

電ファミニコゲーマー

まず、電ファミニコゲーマーは、意図的に、誇大タイトルをつけているので、明らかに良くありません。たくさん記事が読まれないと商売にならないのは分かりますが…。
記事の最後をみると、電ファミニコゲーマーは、ゲームAI用語辞典を作り、ゲーム業界の新しい時代の開発者たちのために、貢献しようとしています。その心意気は大変良いことなのですが、それであれば、なおさら、科学の最も基本的なルール、「嘘は良くない」「誇大タイトルは良くない」というのは気にしてほしいです。

三宅氏

三宅氏は、ある意味被害者といえなくはないですが、この記事は三宅氏の提案でなされたインタビューなので、さすがにタイトルのチェックは、できたのではないでしょうか。(OKと判断した可能性もありますが。これに関連した話は、次の記事で述べます。)

近年、ゲーム技術が専門化するにつれ、他の業界と共有できる技術問題も増えてきました。産学連携が大事ということは、以下の三宅氏自身の記事でも述べられています。

そして、大学へのアプローチも重要です。若い人には、大学でゲームAIを学びたい人が多いんです。ただ、日本の大学教官がこの分野に手を出すとイロモノ扱いされてしまうし、教えられる人もいない。ゲーム産業の方から地道なアプローチと継続的な貢献が必要です。

通常の研究者は、産学連携でも研究としての価値を求めます。そこで、このタイトルをみたら「間違ってるうえに、誇大広告。ゲーム業界は、科学的ではなくレベルが低い。かかわらないことにしよう」と思うかもしれません。それこそ、イロモノ研究者しか集まってこないのではないでしょうか?ぜひ、修正依頼してほしいです。

おわりに

もう1つ記事を、書く予定です。

*1:自分もぎゅわんぶらぁ自己中心派MSX版の1と2を持っていましたし、だいぶ遊びました。記事にでてきたネタも分かります。待ち時間でテンパったかがバレバレでした。

*2:三宅氏自身の記事、「ディジタルゲームにおける人工知能技術の応用の現在」人工知能学会誌 30巻 1号 pp.45-64

カナダで就職する際にしたこと

はじめに

10年前にカナダのバンクーバーで就職活動をして仕事(シニアプログラマー)を得たのですが、最近、海外就職を目指すアカウントからフォローされることが多いので、古い情報ですが、自分がどうやって就職したのか簡単にシェアします。

状況

  • 知り合いはおらず、コネは無かった。
  • 会社を辞めた直後。
  • ワーホリの年齢制限(30歳)を越えていた。会社からワークビザを出してもらう必要がある。
  • 海外就職する予定はなく、日常的に英語の勉強はしてなかった。TOEICは705点(R 375 L 330ぐらい)。英会話は絶望。
  • 貯金はそれなりにあった。

そこで、3ヵ月間バンクーバーの語学学校に通いながら、現地で就職先を探すという方法で、仕事を得ました。*1

英語力

英語力については、全然足りてませんでした。ただ、語学学校で気づいたのですが、日本人のTOEIC400~850点ぐらいまでの人がクラス分けされたとき、クラス分けテスト&面接をしたはずなのに、分布はTOEICの点によらず、ほぼランダムでした。日本人英語事情をよく知っている語学の先生ですら、その差を見分けられない。つまり、このレベルの英語力は、外国人からは「無」と見なされているのに違いない!ということで、開き直りました。3ヵ月ではたいした英語力にはならないという前提で、就職活動をしました。*2

頭を使って、自分にあった就職活動を

一番言いたいことです。普通にやったらダメなので、頭を使って、ダメもとでも行動していくしかないです。例えば、自分がした工夫で、思い出せるのを4つあげます。

1)現地のプログラマーのイベントに参加

現地でのゲーム業界の情報を知るため、また技術英語に慣れるために行きました。しかし、実際には、もっと良いことがありました。
常にレジュメを持って歩いていたので、イベントの休憩時間に、近くの席の人にレジュメを見せたら、みんな興味をもって、いいかんじに添削してくれました。(語学学校の先生にもお願いしたのですが、専門用語がいまいち伝わらなった)。これは大きかったです。

2)電話面接を避ける小細工

電話面接、とくにカメラ映像がない面接は、厳しいです。電話面接を避けるために、あえて日中は狙っている会社の近くの喫茶店で待機していて、電話がかかってきたら、「たまたま近くにいるので、ちょっとだけ会って直接話さない?」と持ち掛けました。この方法で、2つ電話面接を避けれました。

3)ランゲージエクスチェンジ

失敗例。英語力の劇的アップを狙いネイティブの友達を作りたかったのですが、語学学校にいると、現地の友達を作るのは想像以上に難しいです。語学学校のある地域で、日本人なんて珍しくもないですし。普通にやっていてはダメなので、あえて現地の大学(ブリティッシュコロンビア大学)に行き、張り紙をして、募集しました。しかし、おっさんというハンディキャップは大きく、最初の連絡が来た時にはすでに2か月半が経ってました。遅かった…。

4)プレゼン作戦

相手から面接で質問されると英語力のボロがでるので、できるだけ自分が会話の主導権を握ったほうが良いです。そこで、レジュメ・カバーレター以外に、パワーポイントの資料も送っておきました。そして、面接では、それを使って簡単なプレゼンをし、自分が過去に作った担当パートの技術解説をしました。図入りで説明しやすいので、英語力不足も準備で補えます。

これらの工夫自体を勧めているわけではありません。あくまで自分の例で、2)なんて、長期的な英語力の点を考えたら、むしろおススメしません。でも、とにかく頭をつかって、自分の状況に合わせて、どんどん行動していくのが良いと思います。

その他の注意点

目的

目的は、はっきりさせるべきです。「世界的な活躍をしたい」だけなら別に日本でもできますし、「海外で技術を学びたい」「海外で生活してみたい」というのはよく聞きますが、雇う側からしたら、いまいちな回答だと思います。

仕事力

英語のハンディキャップがある分、さすがに平均以上の仕事能力は必要だと思います。仕事能力をアピールして、普通に就職できる*3のなら、そのほうがいいと思います。

おわりに

他にも就職に影響を与えた幸運な要素(例:現地での日本人開発者への信用が高い)もいくつかありましたが、自分でしたことはこんなかんじです。みなさん、ぜひがんばってください!

*1:なお観光ビザで入国しましたが、そもそも就職目的での入国はダメな国も多いので注意。 そこは最初は空気を読んで、「語学学校がメイン!あとは業界調査(あわよくば就職活動…)」みたいなかんじのスタンスでいきました。

*2:就職活動中に、英語力ペラペラになって、就職するというのは無理と悟っただけで、仕事で英語力が不要と言っているわけではありません。むしろ、英語力は、立場が上になればなるほど重要になります。

*3:当時ですら、海外就職したいけどできない人向けの怪しい商売がいくつかあったので、食い物にされないように注意。

失敗談:飛行機に2度乗れなかった話

日本のプロコンに参加するため、シンガポール→日本→シンガポールの往復チケット(55000円)で帰国しようとしたのですが、寝過ごしてしまい乗れませんでした。ばか。しかも、ギリギリ間に合わないとかではなく、出発時刻25分前に、家で目覚めるという、惜しくもなんともない状況だったので、空港にすら行きませんでした(←ポイント)。

しょうがないので、別のチケットを取ることにしたのですが、落ち着いて考えたところ、シンガポール→日本→シンガポールのチケットを持っているわけだから、行きのチケットだけ改めてとれば、最小限の被害で済むと思い、別の航空会社の片道のチケット(37000円)をとりました。それで、日本へ。しかし、これが最悪の判断となることに…。

4日後、

日本→シンガポールへ帰る日、インターネットでチェックインしようとしたのですが、なぜか受け付けてくれません。電話で問い合わせてみたところ、なんと、席はないとのこと!?行きのフライトに搭乗しなかったので、NO SHOW扱いとなり、帰りのフライトも自動でキャンセルされてました…。そもそも、チェックインって、行きのチェックインと、帰りのチェックインで、別々だと思っていました…。

なんとかならないか聞いたところ、「1日遅らせれば、追加料金13万円で帰りのチケットを用意できる」と言われましたが、もうそれって2.5往復相当の絶望的金額…。あきらめました。結局、別な航空会社で、帰りの片道チケットをとることに(37500円)。往復チケットでいいのに、バラで片道チケットを2つとった分、さらなる損を重ねることに。
(平日だったため、行き片道37000円+帰り片道37500円程度でなんとかなりましたが、仕事で当日に帰らないといけないとかだったら、とんでもない損害になってたと思います)

ちなみに、大遅刻して乗れなかった場合でも、念のため空港のカウンターに問い合わせたほうが良いです。追加手数料を払えば、帰りのフライトだけは搭乗できる場合があるとのこと。ただ、その追加手数料も数万円かかり、しかも片道のチケットも別にとらないといけないので、たいていの場合は、往復チケットを取り直したほうが安いかと思います。でも、距離や航空会社で条件は違うと思うので、行きの飛行機に乗れなかった場合でも、航空会社の空港のカウンターに行くか、問い合わせると良いと思います。

まとめ

  • 往復チケットで、「行きは乗らず、帰りだけ乗る。」は不可能。
  • 通常は、また往復チケットを取り直したほうが良い
  • 遅れたとしても、航空会社に問い合わせよう。

おまけ

  • 慰め突発オフが発生しました。ありがとうございました!
  • 成田空港のAIボットが慰めてくれるので、良いです。

TCO Announcement Fun Round - WaterfallFishingの反省

2017年5月の、ちょっと古いマラソンマッチですが、忘れないようにするために、書きました。

問題

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16930&pm=14615

川の幅 W (2≦W≦200)
川の長さ L (5≦L≦100)
川には、岩がある。(5≦岩の数≦W*L/10)。ただし、岩の場所は、分からない。

まず、D日間連続で、魚が上流から下ってくる(4≦D≦20)。

  • 5≦魚の数≦100
  • 魚は、魚群の中心の位置M・標準偏差Sの正規分布で、まず上流に配置される。(0≦M≦W-1, 2≦S≦W/4)。M,Sも分からない。
  • 魚はまっすぐ下るが、岩にぶつかると50%の確率で左に1マス、50%の確率で右に1マスずれて落ちる。
  • 魚が、下流に下ってきた魚の数は、場所ごとに分かる。

f:id:shindannin:20180103184334p:plain

(範囲になっている変数は、テストケースごとに、ランダムに均一に選ばれる)

D日間分の下流に下ってきた魚の数の情報を用いて、D+1日目に落ちてくる魚の場所を予測し、罠をしかけて、できるだけ多く捕れ。スコアは、(捕まえた魚の数)/(罠を仕掛けた数)で決まる。与えられた計算時間は60秒間。

方針

機械学習で予測した。ただ、この問題、データが足りなすぎる、かつ、あまり当てにならない。魚群の位置M,Sは毎日変わるので、ここの予想が外れると、ほぼ魚を捕れない。そういうわけで、機械学習は避けて、確率の知識などで解答した人が多かったっぽい。
ただ、自分は機械学習でごり押しした。データ不足を補うために、自前でデータを生成した。やり方は以下の通り。

(1) 「岩配置」と「下流に下ってきた魚の数のデータ」のペアを、問題と同じ方法で200種類生成。
(2) 「岩配置」から、下流に下ってきた魚の数の期待値を場所ごとに求める。上流の魚の確率分布は、1000万回シミュレーションして求めた(数学強い方なら解析的に求められる)。上流での魚の確率分布と岩の配置を用いれば、簡単な期待値DPで、下流に下ってきた魚の数の期待値を求められる。これを機械学習の目的変数(予測したい値)として使用。
(3) 「下流に下ってきた魚の数のデータ」は、機械学習の説明変数(特徴量)の生成のために使用。最終的には以下を説明変数として用いた。

  • 下流の位置 X
  • 川の幅 W
  • 川の長さ L
  • 魚の数

さらに、Xの近傍のデータも説明変数に追加した。近傍をY (X-3 <= Y <= X+3)として

  • D日間で、Yに下ってきた魚の総数
  • D日間で、Yに下ってきた魚の割合の和
  • D日間で、Yに下ってきた魚の総数とXに下ってきた魚の総数の差

(4) あとは、自前のランダムフォレスト(そろそろ、自前Gradient Boosting系のものを用意しておきたい…)で50秒間訓練。
(5) 全ての位置Xで、下ってきた魚の期待値を予測し、もっとも期待値が大きい場所1か所に罠をしかけた。

まとめ

他人の解法と、自分の解法がズレてたおかげで、まさかの1位!機械学習しても2位のスコアとの差は大きくないのですが、不確定要素が多すぎるこの問題においても、機械学習が有効だったのは、自分でも驚いた。データ生成の仕方が重要。

実は、このマッチはあまり時間の余裕がなく、また直前のマラソンマッチのミスでレートを大きく下げていて弱気になり、参加する予定はなかったのだけど、tomerun氏の無言の煽り励ましツイートで、参加することになったのでした。マラソンマッチは、最後まで何が起こるかわからないので、皆さんも参加しましょう!