読者です 読者をやめる 読者になる 読者になる

競プロ歴半年のハムスターが、競プロのおかげで留学中に4ヶ月でロボットアルゴリズムを発明してトップ学会に論文通した話

これはCompetitive Programming (その2) Advent Calendar 2016 - Adventar の5日目の記事です.

概要

競プロ歴半年のハムスターが、競プロのおかげで留学中に4ヶ月でロボットアルゴリズムを発明して、ロボット系のトップカンファレンスに論文通した話をします。ありがとうAtcoder、ありがとうAOJ、ありがとう競プロ、ありがとうみんな。

このブログのメインコンテンツは「何が言いたいのか」の項です。時間が惜しい人は、ポエムを飛ばしてください。構成は、以下の通り。

  • ポエム
  • 何が言いたいのか=ポエムの解釈

自己紹介

TopcoderCodeforcesレーティングが逆相関するタイプのハムスターです。

f:id:intelhamko:20170117083343p:plain

f:id:intelhamko:20170117083432p:plain

 

過去の話

2005年

中学2年生。ゲームが好きだったので、C#シューティングゲームを作ったり、PHPPerl経済シミュレーションゲームを運営したりしていた。

2007年

高校1年生。高校のコンピュータ部部長になったので、中学生にバブルソートを教えてた。

2010年

大学1年生。東大に「実践的プログラミング」という競技プログラミングすると単位が来る授業があったので、履修した。履修者には、rngさんもいた。意味不明なレベルの高さだったので、単位を落とした。Topcoderにちょっと参加した。復習とか全くしていなかったので、緑と青で振動していた。

2012年

大学3年生。ロボコンサークルRoboTechの1年生のプログラミング能力が、個々人差大きすぎだったので、僕が適当に競技プログラミングの問題を作って、コードレビューする講習をしていた。

最近の話

2016年4月

ドイツ留学開始。

ドイツでロボットの研究をしようとするが、あまりにロボットを壊しすぎて、ロボットを工場送りにする。シニアリサーチャーの厚意で、「俺のロボットを貸してあげるけど、絶対壊すなよ!絶対だからな!」と言われながらロボットを貸していただく。でもロボットは壊さないと研究できないので、ロボット研究を諦める。そこで数理・計算論的な方向に行こうと決心する。ちょっと競プロ始める。

2016年5月

Atcoder ABC D問題とIOJ-ICPCの☆付き問題を解く、ゆるふわ勉強会を始める。後に、AOJ-ICPC 600点台を黙々と解き続ける狂気の勉強会と化し、誰もついていけなくなった挙句に自然消滅するとは、誰にも予想できなかった…。

docs.google.com

初めは、東大の知り合いを巻き込んだだけの勉強会だった。途中から、mayokoさん、btkさん、らてさんなども巻き込みながら、それなりの大きさの勉強会コミュニティとなった。

2016年6月

始めてのTopcoderでイエローコーダーになる。地味に嬉しかった。

2016年7月

どちらかというと研究の調査をしてた。具体的には自然な動きをするロボットが満たすべき運動方程式みたいなのを勉強していた。

2016年8月

ロボット研究のテーマを思いついた。yukicoderで言えば☆2.5くらい。簡単だったのでさっさと実装した。具体的には、適当にセグ木使ってオンラインクエリやるだけの問題だった。

2016年9月

ロボット系国際学会ICRA( International Conference on Robotics and Automation 2017)に論文投稿した。この学会は、ロボット系の学会では最高峰と言われている。そんなに難しい問題を解いていないし、まあ通らないだろうなあ、と思いながらSubmitボタンを押した。

ICRA 2017 | IEEE International Conference on Robotics and Automation 2017

ちなみに、締め切り日に寝坊したが、投稿締め切りを勘違いしていたので、論文投稿できた。負x負=正。

あと、問題を初めて作った。

intelhamko.hatenablog.com

これがドイツ最後の月であった。

2016年1月17日

始めての査読付き国際学会のACをもらった。 

何が言いたいのか

競プロ役に立たない競プロ役に立たないって言われて、自信なくしかけてそうな競技プログラマに向けて、競プロ普通に役に立つよ〜すごいよ〜って言いたかった。また、プロコンへの新規参入者を想定すると、魅力的な成功体験談がないとmotivateされないだろう。プロコンが役に立った!という一例がここにあるよ、ということを伝えたかった。

競技プログラミングは、専門外の人間がアルゴリズムを広範囲に勉強するのに重宝する。今回の学会へのAcceptは、AtcoderやAOJといったコンテスト基盤のみならず、助けあうtwitterでの競技プログラミングコミュニティがなければ実現できなかっただろう。

競技プログラミングの基礎的な経験だけでも、十分世界に通用する応用を構築できる。先述の通り、実際に解いた問題は簡単だったが、論文は通った。せいぜいCodeforces Div.1 A問題-B問題くらい、Yukicoder★2.5くらいだった。しかし、競技プログラミングをやっていない人にとっては難しい問題に見えるようだ。実際、ドイツ留学前の僕がこの問題を思いついても、解くことはできなかっただろう。生産性は、問題抽出と問題解決の掛け算なので、超絶難しい問題を解けば喜ばれるとは限らない。

競技プログラミングによる教育は、時間的に有利である。勉強に要した時間は、たった4ヶ月である。論文や書籍を読んでいるだけでは、洗練された教育プログラムであっても、決して4ヶ月で広範囲なアルゴリズムの知識を得ることはできないだろう。今後、アルゴリズムを勉強する人には、競技プログラミングを強く勧めたい。

競技プログラマのコミュニティは、生産的である。Twitterやブログなどで、リアルの顔も知らずに気軽に質問し合える関係は、実は世界的にも稀有なwin-winな関係に思える。適度なノブレスオブリージュを共有しながらも、高圧的ではなく、コミュニティに貢献するのが自然である雰囲気は、とても気に入っているし、生産的だと思う。

結局、何が言いたいのか

ありがとうAtcoder、ありがとうAOJ、ありがとう競プロ、ありがとうみんな。

yukicoder 456の作問と、冬の大三角と(^^*)のテスター記録

投稿型プログラミングコンテストであるyukicoderで、僕が作った1問でコンテストが開かれた。この問題は、yukicoderに1日1問アルゴリズムに関する問題を出すイベントである、yukicoder Advent Calendarの問題として出された。yukicoderは最近勢いのあるコンテスト基盤で、気軽に皆が問題を投稿できることが特徴である。16世紀のルネサンスのような、問題を出し合って解き合う雰囲気が楽しい。

No.456 Millions of Submits! - yukicoder

また、yukicoder Advent Calendarの他の2問(冬の大三角と(^^*))のテスターを引き受けた。テスターは、要するに査読者である。問題文が多義的でないか、非想定解がないか、愚直解で通らないか等をチェックする。

No.455 冬の大三角 - yukicoder

No.457 (^^*) - yukicoder 

Millions of Submits!

僕の問題は、炎上した。重要な順に以下の要因がある。

  1. 問題自体の不備(解答が複数あるのに1つだけ出せと問題文が言っていた)
  2. 制限時間の不備(powをfor文で回すと通る、というアホらしいことをして通る)
  3. そもそも定数倍高速化の問題(理論屋に嫌われる)
  4. ジャッジに異常に時間がかかる(yukiさんにwishしたらこの問題以降改善)
  5. 出力制限があり謎のランタイムエラー(yukiさんにwishしたらこの問題以降出力制限を明記)

問題自体の不備

今回、本来複数解あるのに、一つだけ出力せよと言っていた。これに気付かなかったのは、僕の頭が悪い。また、複数解があるのに僕とテスターが80 submitsして、500万テストケースに対する答えが一致するという奇跡が起きていた。本当にたまたま、僕とテスターが求めていたものが「あり得る解の中で最大のもの」であったため、コンテスト開始20分くらいに、問題文をわずかに書き換えることで対応した。

解決方法は、基本能力を上げるしかないので、

  • 僕がレッドコーダーになる
  • テスターがレッドコーダーになる、の二点である。

制限時間の不備

この問題では、浮動小数点aに対して、{a^n}を計算する必要があった。しかしnが小さくかつ整数だったので、pow(a, n)より for (int i = 0; i < n; i++) ret *= a; の方が高速だった。僕の実装力の低さにより事前に発見できなかった。これはチェックしたはずだったのだが、メモ化を一箇所忘れたため事前に発見できなかった。

これは、4つ解決方法があって、

  • 定数倍高速化の問題は作問がつらいので制約をめちゃめちゃきつくする
  • 僕がレッドコーダーになる
  • 問題で考慮すべき制約条件を網羅的にテスターと共有する
  • 利用できそうな制約を潰す(今回であればnを浮動小数点にする)

そもそも定数倍高速化の問題

結構根が深い問題で、定数倍高速化は嫌われる(許さんぞお前!みたいな扱いされることが多い)。

嫌われる原因は3つあると思う。

一つ目は、訊いている知識やアイディアがコンパイラの最適化でボヤけるから。ちょっと順番を替えたり、ループアンローリングするだけで通ってしまったら興ざめである。今回の問題では、訊こうとしているアイディアは明確だったが、制限時間が長くぼやけてしまった。なお、今回訊いていたことは以下の2点であった。以下のどちらかが思いつけば、通るようになっていた。(1) 二分探索内部の演算量を減らすための変数変換(logを取る、ランベルトのW関数を使うなど)。(2) 1次収束の二分探索ではなく、2次収束のNewton法や、3次収束のHalley法といったHouseholder Methodを使うと高速であること。

二つ目は、言語を限定しないと何を聞いている問題なのかわからなくなるので、C++を強要するから。C++を前提にして、TLを闇魔術を使わないタイプのライター解を書いて、時間制限をライター実行時間の+50%くらいにするのが良いのかな、と思った。複数言語で解答可能のようにすると、訊いているアイディアがボヤける。

三つ目は、理論屋はオーダーが下がるのを見るのが好きだから(知るか)。でも今回は、収束次元数が変わっているから、誤差要求仕様を計算量に含めると、多分オーダーも変わっているはず。

定数倍を頑張るのもまたプログラミングなのだから、プログラミングコンテストでそういうノウハウを醸成する基盤を除外するのは分野に健全ではないと思う。定数倍高速化を出すときには、それ専用の方法論を持つべきだと感じた。

ジャッジに異常に時間がかかる&出力制限

僕の問題が終わったあと、yukiさんにwishを投げたら即対応していただいた。神。

モチベーション

この問題のモチベーションは、数値計算ニュートン法を使う問題を見たことがなかったことである。ロボコン極値計算したくなった時に、ニュートン法が高速で感動した。その感動を伝えるために、定数倍高速化の問題を作った。そしたら、よくよく考えると競プロ的な逆関数が大概ランベルトのWで表されてしまってとてもつらい、という感じだった。思考停止して、ランベルトのW+Halley法を想定解としてぶん投げた。

テスター

テスターとしては、冬の大三角と(^^*)を引き受けた。

冬の大三角

スペシャルジャッジのバグに気づけなかった。テスターはきちんとジャッジまで気を配らないとなあ、と戒めた。

(^^*)

(1) 問題文が構造化されていなかったので、修正案の提案。誤読を避けるために強調すべきポイントの指摘

(2) {O(n^2)}が想定解だったが、筋肉を使うと{O(n \log n)}があるのが自明だったので報告

管理人のyukiさんが、問題文を編集したので読みやすくなった。テスターも、問題文を積極的に編集していったほうがいいのかなあと悩んでいる。また、想定解として{O(n)}を思いつけなかったので修練不足を感じた。

感想

また、問題の著作yukiさんと共同であるのだから、テスターとのやりとりは初めからyukiさんを混ぜるべきだと感じた。

博士課程教育リーディングプログラムフォーラム2016 参加記録

博士課程教育リーディングプログラムフォーラム2016に参加した。産官の人事へのアピールと、英語討論登壇(リーディングプログラム間のSNS活用によるコラボレーション環境構築)のため、このフォーラムに行った。アピールはうまくいった。英語討論会は、登壇だと思ったのに登壇できず、英語討論会と書いてあったのに英語で討論されず、人生最大のがっかり謎イベントだった。

博士課程教育リーディングプログラム フォーラム2016 | 11月11日(金)・12日(土) inヒルトン東京お台場

 

博士課程教育リーディングプログラムとは、「産・学・官の参画を得つつ、専門分野の枠を超えて博士課程前期・後期一貫した世界に通用する質の保証された学位プログラムを構築・展開する大学院教育」である。このフォーラムは、プログラムの参加大学が集結し、産官の人事と学生が交流したり、リーディングプログラムをより良くする方法を模索するフォーラムであった。なお僕は、東京大学のソーシャルICTグローバル・クリエイティブリーダー育成プログラム(GCL)に参加しており、他のプログラムに興味があったので、このフォーラムで他の博士候補生との人脈を作ろうというモチベーションだった。

 

 

一日目は、産官の人事へのアピールのため、ポスター発表をした。80%研究(僕の研究3つ)、20%経歴(ロボコンハッカソンフリーランスなど)の割合でポスターを作成した。この塩梅は良かったように思える。GCLからは、他に二人参加していて、一人は完全に研究、もう一人は完全に経歴に振ってポスターを作っていた。リーディングプログラムは、やはり研究が主軸であるが、それと共に社会人・行動力などを総合的に見られるので、両方をアピールできたのは良かったと思う。

 

二日目は、SNS活用コラボレーションに関する英語討論会だった。これは、僕の人生最大のがっかりイベントだった。英語討論会だと言っているのに、英語で討論がなされず、討論会中に聴衆の留学生から厳しい批判を受けていた。僕は登壇だと思っていたのに、壇上に席はなく、非常に謎だった。

東大からは、三人が討論申し込みをしていたが、なぜか壇上に僕たちの席はなく、聴衆として討論会に参加した。僕に関しては、僕と担当者の連絡の齟齬だったのだが、他の二人については未だに理由がよくわかっていない。これは慶応大学の学生が主催しており、他の様々なところでもトラブルがあったらしい。

一応、短い質疑応答時間で積極的に英語でコメントして、討論会そのものに貢献したとは言ってよいと思う。自分がイベントを主催するときには、こういう風にあまりいい加減な事をしていると、参加者(重要企業・優秀な学生・文部科学省など)の不信感を買う結果となるので、きちんとしないとなあ、と思う。

東大女子限定ハッカソン Teatime Hackathon 2016 参加記録

東京大学Teatime Hackathon 2016のメンターを、GCLのRAとして引き受けた。Teatime Hackathonは、東京大学の女子学生を文理・学部大学院問わず集めて行うハッカソンである。今回のテーマは「日常に感動を」であった。メンターは、女子学生の技術サポートをする仕事だった。

 

実際に学生が作った作品は、「人形が舞台的に自動装飾してくれるお皿ロボット」である。料理と皿が渾然一体となって完成していく様を感じることができるだろう。

“”原価何十円としないパスタ料理は、盛り付ける皿によって値段は数千円へ跳ね上がる(トリコより)。””

 

www.youtube.com

 

この作品のユースケースは、レストランと個人宅である。

レストランで、客が退屈に料理を待つ時間を有効活用して、皿の絵が「舞台的に」完成していく体験を提供できる。これによって、客は待ち時間の間、舞台的な自動装飾を楽しむことができるので、レストランは待ち時間を有効活用して付加価値を提供できる。客は、好みの柄を選ぶことができる。さらに、メイドカフェ・宇宙カフェなどでは、装飾の柄が、店のオリジナリティや価値にダイレクトに繋がる。また、チェーン店では料理人のスキルによって、装飾の質にムラができてしまうが、この皿を使うことで、美しい装飾を再現性高く施すことができる。更に、装飾にかける時間を短縮することで、仕事の効率化にも寄与する。

一方自炊では、どうしても皿が簡素になりがちである。レストランのフレンチやスイーツでは、皿の上のソースや粉砂糖の装飾が、料理を美しく演出する。自炊では時間的・技術的に到底作りえない美しい装飾を、この皿を使うことで、自宅で日常的に体験することができる。

 

今までにも、IoT的に皿を演出する作品はあったが、実際の食べ物を用いて装飾するというものはなかった。例えば、プロジェクションマッピングでレストランの待ち時間に動画を放映するものがあるが、放映と食が直接的に繋がっていない。放映されたソースは食べることができない。実際の食品で食べられる装飾を施すというのは、視覚・味覚的経験をダイレクトに繋げるという点で、従来にない革新的なIoTデバイスである。今後は、プロジェクションマッピングとの融合も視野に入るだろう。

 

www.youtube.com

 

この皿はiPhoneで操作できるIoTデバイスである。将来的には絵柄をインターネット上のカタログから好きなものを選ぶことができるようになるだろう。更に、絵柄をユーザ自らが作成してアップロードしたり、インスタグラムのように「人気絵柄アーティスト」が誕生したりするかもしれない。また、今はかなり大きな皿になってしまっているが、機構を「机に埋め込む」ことで、薄い皿の上で同じことができるだろう。また、装飾するフィギュアは、自由に選ぶことができる。例えば、各レストランごとのマスコットキャラクターで装飾することで、広告にもなるだろう。また、現在は「粉砂糖をどかす」だけだったが、カッターを持たせて「肉を切る」、コテを持たせて「肉に焦げ目をつける」と言った応用もできるかもしれない。

 

 

 

この作品は、技術的に高度な作品である。この皿はiPhoneアプリから操作可能である。マイコンとして、Arduino Unoが2台、Konashiが1台内蔵されている。ArduinoとKonashiはシリアル通信でつながっており、iPhoneからの指令がArduinoに伝わるようになっている。外観には、レーザカッターで作品名が刻印されている。また、内部のロボットは3Dプリンタで出力された部品を組み立てている。アクチュエータはタミヤのギアボックスで、エンコーダはアルプス電機のメカニカルエンコーダが使われている。アクチュエータはタイミングベルトとプーリーを介して、直動に変換される。このロボットはP制御で任意の二次元座標にエンドエフェクタを移動可能である。エンドエフェクタにはネオジウム磁石が装着されており、皿の上の磁石付きフィギュアを操作する。さらに、更に何か食べ物が載った瞬間を検知し、皿の縁がLEDの光で演出される。材料費・加工費は、合わせて約15000円程度である(材料余剰分も含めると25000円)。

 

f:id:intelhamko:20161202165244p:plain

f:id:intelhamko:20161202165141j:plain

 

 

僕は、この作品を作った「夜明けのはむチーズ」というチームのメンターだった。初めは、全部で7人(工学2人非工学3人メンター2人)のチームだったのだが、工学系2人とメンター1人が途中不参加となった。そのため、工学系のリソースが非常に少なくなってしまった。

 

全員の能力・バイタリティ・知識欲がすばらしかった。何を作るか決める段階から、長い会議にも関わらず生産性を落とさずにアイディアを出し続け、今回の作品の全体像を具体化した。また、女子学生にかなりの量の設計と実装を任せることができた。僕は、女子学生には不可能だろう設計のみを行った。僕が行った設計も、それに至る道を時間の許すかぎり教えながら、製作を行った。具体的には、「軌道設計用システム」「構造材の印刷」「回路設計」「プログラムの制御フロー設計」の四点は、不可能と判断して僕が設計した。逆に、例えば以下は女子学生が行った:「レーザーカッターの軌道計画」「外観の設計・デザイン」「ロボットのメカの構造設計」「回路実装」「P制御」「重さセンサイベントからのLチカプログラム」「実際のプログラミング」。ここまで来ると、東大のロボット学科(機械情報工学科)でも経験できないレベルである。チームとしても、全員の能力(というか才能)がうまいことバラけていて、相補的に製作を進めることができたので、非常にやりやすかった。

特にデザインは凄まじかった。チームロゴ、作品ロゴ、外観デザインなど。

f:id:intelhamko:20161202165056p:plain

f:id:intelhamko:20161202165028j:plain

  

しかし結果として、この作品は賞が取れなかった。恐らく参加チームの中で最もリソースを割いたにも関わらず、半分以上のチームに用意されていた賞が取れなかった。原因としては、作成した作品が技術的に高度で完成が当日の午前中だったこと、発表練習がなかったこと、発表10分前にArduinoが故障してデモがうまくうごなかったこと、作品の見た目は美しいが地味であること、ストーリーに口を出しすぎると僕の作品になってしまうのでスライドを任せっきりだったこと、初めから実装が重すぎたこと、などが考えられる。

 

個人的な反省は3点ある。1つ目は、学生の相当のコミットメントが必要なスケジューリングにしたことである。初めからギリギリいけるくらいかな、と思っていたが女子学生にロボコンのノリを暗に求めたのは反省している。アイディア出しの段階で、できるっちゃできるけど大変であることを明確に伝え、安全率をうんと上げて対応すべきだった。2つ目は、賞が取れなかったことで落ち込んでしまったことである。僕は技術サポートのためにいるので、落ち込むべきは賞が取れなかったことではなく、デモを完動させられなかったことについてである。特に開発終了1分前、僕が配線を間違えてデモが動かなくなったので、申し訳ない。3点目は、工学系学生が2人いなくなった段階で、運営に声がけするべきだった。

僕の負担が少し多かった。

 

審査員は、申請項しか審査しないのだなあ、という自明な感想を抱いた。僕も、きちんと訴求しなければ。

 

f:id:intelhamko:20161202165411j:plain

CODE FESTIVAL 2016 Final 参加記録

日本最大のオンサイトプログラミングコンテスト、CODE FESTIVALに参加した。プログラミングコンテストと言うが、実際にはアルゴリズムコンテストという感じ。僕はドイツ留学中に、このコンテストの予選を突破した。

http://intelhamko.hatenablog.com/entry/2016/09/26/111113

このコンテストは、大学生・大学院生・未就業者を220人(!)集めて開催される。人数が多いので、予選突破が容易である。むしろ普通の人間がこれ以外でオンサイトに参加するのは困難だと思う。220人のアルゴリズムスペシャリスト(主にTwitterなどでよく見かける人)と話す機会であった。実際に僕はTwitterのみで知り合いだった、多くの優秀なプログラマと会話できた。

 

コンテストは主に3つあった。(1) 本戦。10問3時間。1600点以上でパーカーがもらえる。 20位以上で賞金がもらえる。 (2) トーナメント。本戦の近い順位の人で戦い、勝ち残る。2問30分。突破ごとにステッカーがもらえる。(3) チーム戦。11人チームで、11問の問題を90分で解く。チーム対抗で戦う。パソコンはチームで1台。1人1問しか実装してはならない。

全コンテストを通じて、結果は散々だった。自分のアルゴリズム力もプログラミング実装力も全然ないことを自覚した。コンテスト中、ずっと帰りたかったレベル。

 

本戦では、1500点でパーカーがもらえず、136位/220人だった。10問はAからIまで番号が付いている。A-Dまではミスがなく、66分くらいでそれなりにすんなり解けた。ここまでで1500点だった。パーカーゲットには、Eの部分点かFかHの部分点を解く必要があった。Eが、点数も低く簡単そうだったので、2時間くらい取り組んだが、全く解けなかった。Eの部分点は明らかに凸凹していそうだったので、絶対DPだろうと思いながらも、思いつかなかったので嘘貪欲を書いて死んだ。

解けた問題は以下。A問題は、全探索+文字列比較。B問題は、{O(n^2)}までの値で必ず構成できるので逆から自明に貪欲。C問題は、対応逆にしてUnionFind。D問題は、mod Mの世界でカウントして、偶数個あるものはなるべく残したいので、奇数個の数字を優先に消化していく貪欲。

http://cf16-final.contest.atcoder.jp/submissions/991410

http://cf16-final.contest.atcoder.jp/submissions/991690

http://cf16-final.contest.atcoder.jp/submissions/991995

http://cf16-final.contest.atcoder.jp/submissions/993120

 

トーナメント戦では、0点で1回戦敗退だった。2問はAからIまで番号が付いており、部分点が多く設定されていた。初め、400点くらいが突破ボーダーかな、と思っていたが、ボーダーは100点(0点でなければ良い)だった。本番で、僕はA問題はグラフで筋肉が必要そうだったので、簡単そうな桁DPっぽいB問題にとりかかった。これは{O(n^3)}DPが自明だったので、実装しようとした。しかし、バグって実装が終わらず0点となったしまった。しかもバグの原因が本当に大馬鹿で、(string)"123">(string)"24"だと思い込んでいたせいだった。コンテスト後20分くらいデバッグして、B問題の{n \le 100}制約のみACさせた。dp(i, j, h) = s[0:i)にちょうどj回カンマを挿入して、最後にh文字カンマが入っていない時の最大値の最小。

http://cf16-tournament-round1group21.contest.atcoder.jp/submissions/997228

 

チームリレーでは、E問題を2分で一発ACさせた。時間節約という意味で貢献できたと思う。終わったあと、I問題をマヨ子さんと一緒に考えていたけれど、頂点4個の時のOKケースを1例挙げた程度の貢献しかできなかった。

http://cf16-relay06.contest.atcoder.jp/submissions/999117

 

その他の活動では、touristへの質問ライブ、コード川柳、書道コーディングをした。touristの質問ライブでは、12問中5問僕の質問が採用されてなんとなくうれしかった。 書道コーディングは以下。0完太陽はお気に入りです。

f:id:intelhamko:20161127190519j:plainf:id:intelhamko:20161127190535j:plain

f:id:intelhamko:20161127190621j:plain

 

ドイツ留学記録

2016年4月から半年間、ドイツ留学した。ミュンヘン工科大学のProf. Gordon Chengの研究室で、Marie Curie奨学金を受け取りながら触覚系のプロジェクトに採用して頂いた。リーディングプログラムから旅費も出る。この待遇は、金銭的にもキャリアパスとしても、とてつもなく良い。リーディング大学院の海外インターン要件3ヶ月も、余裕で達成できる。外国での研究経験もできる。幸運にも、至れりつくせりの支援を受けることができた。

財源はMarie Curie奨学金GCLだった。Marie Curie奨学金は、EUが全世界に募集をかけている奨学金である。このうち、Initial Training Networksという、博士学生向けの教育プログラムを利用していた。これは、奨学金の申請を学生が行うのではなく、指導教員が書類を書くのが特徴である。また、奨励金の金額が非常に多いことで有名である。具体的には、月収38万円(115円/ユーロ)だった。

 

事の発端は、M1の終わり頃に行った、卒論の英語デモだった。これが、その時の聴衆にいたアジア系の人にめっちゃウケた。この人がProf. Gordon Chengその人だったのだが、そのことは当時知らなかった。その後、M2の9月くらいにボスに呼び出されて、僕がProf. Gordon Chengから半年ドイツで研究をしないかと誘われている、と伝えられた。この時点で、留学のための奨励金も、東大のリーディングプログラムとの連携も万全、という状態だった。僕の知らないところで全てが整えられていた。正直、何が起きているのか全くわからなかった。

 

留学前の2015年9月から3ヶ月間、英会話をRare Jobで2日に1回学んでいた。修士論文と被りまくっていたが、英語の訓練は避けてはいけないと思って、修論提出2ヶ月前まで英会話を続けた。この効果はかなり大きく、留学直後の事務作業で、英会話で問題を起こすようなことはなかった。しかし、研究のディスカッションとなると全く話は別だった。深い議論ができなくて困るというだけではなく、色々な国籍の人の英語の「癖」に翻弄された。ロシア人の英語は今も全く聞き取れない。口語的に大量のリエゾンを混ぜてくるメキシコ人も、すみませんがゆっくり喋ってくださいと言わざるを得なかった。

 

研究そのものは、本当に冷や汗ものだった。初めはロボットを使って一発芸+解析をしようとしたのだが、いろいろな理由で無理だったので、6月から路線変更を強いられた。その後、修士論文から興味があった、動力学+制御の論文をひたすら読み漁っていた。古典かつ最高成績を誇る論文が分割統治法を利用していることもあり、競技プログラミングアルゴリズムを勉強することに決めた。しかし、この路線変更がうまく行かない可能性を考えて、ロボットはキープしていた。ロボットをずっと専有していることもあって、本来なら結果が出ていなければならない7月(3ヶ月目)での研究会では、周囲からの目が非常に厳しかった。

この後、2016/8/15くらいに、個人的に実用的で良さそうなアイディアがやっと出た。その後サーベイで先行研究と応用先を洗い出して、2016/8/25から2種類の手法の実装をし始めた。この後、2016/9/2に日本のボスに報告した。そうしたら、違う人からかなりネガティブな意見をもらって、やる気を消失し、ラスト1ヶ月の重要な時間を1週間くらい呆然と過ごしていた。その後、やる気を取り戻して2016/9/10に2つの結果をProf. Gordon Chengに見せたら、気に入ったと言われて、そのうち1つを2016/9/15締切の査読付き国際学会のICRAへ出すように指示された。その後、日本のボスにすぐ投稿許可を投げた。そうしたら、違う人からかなりネガティブな意見をもらって、やる気を消失し、投稿5日前の重要な時間を2日くらい呆然と過ごしていた。その後、やる気を取り戻して、頑張って論文を書いて投稿した。その後1週間くらい頑張ったら、A4にして22ページくらいの研究報告書が書けるくらいの分量の伝えたいことができた。

研究発表は、触覚系プロジェクトが主催するワークショップと最終ミーティングで行った。7月にロンドンのImperial Collegeで行われたEuro Haptics 2016のWorkshopで修士論文の報告をした。9月29日には、スコットランドのGlasgow Universityでドイツで行った研究を発表した。実は9/30に日本に発つつもりだったので、このミーティングには参加できないはずだった。しかし、このミーティングにはとにかく参加したかったので、飛行機の日程変更をしたり急にミーティング参加人数を増やしてもらったり、とにかく色んな人に迷惑をかけて何とか参加できることになった。

 

留学前後での、英語力の上がり方は微妙だった。スピーキングは頭をフル回転させれば言いたいことがほぼ言えるようになった。しかし、やはり脳内で構文解析しないといけないし、英語での議論はどうしても浅くなる。リスニングは「綺麗なQueen's English」以外の英語の癖に少し慣れた。綺麗な英語のリスニング能力もかなり上がった。どちらかというと、大量のメールを処理しなければならないので、Writingのスピードがめちゃくちゃ早くなったと感じている。もしかするとタイピングの速度が上がっているだけかもしれない。

リスニングの方が大変かつ重要だと感じた。聞こえないとコミュニケーションにならず、意味不明な返答をしてしまう。特に、質疑で英語がわからないと本当に困る。どうしても、自分がしゃべる英語から遠い英語は全然聞き取れない(逆に僕はアメリカ英語を喋っているので、MITの研究者とかはものすごく聞き取りやすい)。速いのも無理。自分が使わない慣用表現が入ると、聞き取れても意味不明なので、知らない単語は使っていくしかないなと感じた。今後はリスニングを重視していこうと決意した。

 

宿は2016年3月に、全てAirbnbで確保した。大量のトラブルがあったが、結果的にこれは良い選択だった。最大のメリットは、水道代電気代インターネット代支払いや生活必需品管理その他もろもろの管理を外注できることである。賃貸の相場より1万円程度高いが、完全にこれらのメリットが上回っていると感じた。あと、人と話せる。

 

研究者の間での日本のイメージは悪化してきている。最近のロボットのイニシアティブはアメリカ・韓国・中国に奪われている、という話をロシアのD1学生がしていた。逆にイギリスでは、日本は電気系とゲームとロボットが強い、と思われていてびっくりした。

アジア人っぽいなーと思うとほとんど中国人という感じで、月並みだが危機感を感じた。例えばエラスムス・ムンドゥス奨学金では、中国人が101人/1950人通っているのに対し、日本人は5人/23人しか通っていない、というかそもそも申請していない。さすがに申請率1%はどうなの。

 

ドイツは治安が非常に良く、人も優しかった。いいところ。

ドイツは親日的で、日本人はレアキャラ扱いされた。アニメが好きな人が多いらしく、酒場で3人くらい進撃の巨人の話をされた。始めAttack of Titanって何の話だと思っていた。どうやら、名前をドイツ人の名前から取ってきているのが好感らしい。

ドイツ料理はかなりパワフルで、繊細さのあるものは少ないが、美味しいものは美味しい。肉や調理法でオリジナリティを出す店は少なく、グレービーソースにこだわっているところが多かった。個人的にはHofbraue houseのBearbratelという料理がおすすめ。あとLoewen Braueはソースがおいしく、スペシャリティはおすすめ。

yukicoder 423-426 作問記録

投稿型プログラミングコンテストであるyukicoderで、僕が作った4問でコンテストが開かれた。yukicoderは最近勢いのあるコンテスト基盤で、気軽に皆が問題を投稿できることが特徴である。16世紀のルネサンスのような、問題を出し合って解き合う雰囲気が楽しい。作問時のyukicoderの管理人とテスターとのやりとりは、自分の勉強にもなった。

 

作問の流れは、以下のようになっている。

  • 問題を作る
  • テスト入力を作る
  • 解説を書く
  • テスターと呼ばれる人とやりとりし、問題が正しく作られていることを確認する。問題のより良い解法を一緒に模索する。
  • 実際に問題を出す
  • コンテスト中の質問に答える
  • 最終的な問題の不備を修正する

作問の練習用に、AからCまではやるだけという感じの問題を作った。D問題は自分で作っておきながら難しすぎたので、らてさんと相談しながら{O(\sqrt{n})} 解を実装した。のちに、りあんさんと相談していたら{O(\log n})解が爆誕した。

 

テスターとのやりとりが非常に勉強になった。

C問題では難易度見積もりでテスターと議論があった。僕の難易度見積もりは★2だったのだが、確率問題なので★3とした。一方、テスターのbtkさんは数学的厳密解を出そうとしたために★4と見積もった。このテスター解(確率を行列演算で求める方法)が面白かったのだが、制約がキツいので誤差の問題でこれが通らない。テスター解を通すために、制約を緩和したのだが、それでも通らなかったのでテスター解を想定解とするのを諦めた。

D問題では、想定解は平方分割で{O(\sqrt{n})}解法だったが、テスターのりあんさんがO(\log n)解を出してくれた。これを想定解とするように制約をキツくする調整を行った。さらに、りあんさんはテストケースの追加指示・解説のミス指摘など、多くの貢献をしてくれた。考察が終わってみると実装も比較的軽く、綺麗なコードになるのでいい問題になったと思う。勉強にもなったし、いい問題になったと思うが、問題完成がコンテストの10時間前だった。

 

AがWA祭りになった。コーナーケースの問題を出そうとしていたから、予想していたのだが、さすがに一発ACが10%しかいないのは、問題がダメだったなあと思った。leading zerosの厳密な定義を書いていなかったのもよくなかった。

 

Dはコンテスト中に★4から★5に格上げされた。★4にしたのは、解答を聞いてみればただのsegment treeなのと、この解答を出してくれたテスターが黄色だったから。黄色上位なら解けるだろうと思っていた。甘かった。実際には、btkさんと、LGMレベルのantaとyosupoさんの3人しかコンテスト中に解けなかった。

 

Dの非想定解{O(q^2})が出た。初期値が単位行列であることと、クエリ数が小さいので疎であることを利用した解答だった。やはり作問に自分のアルゴリズム力が重要であることを再確認した。

 

Dのリアクティブの設定が上手く言っていなかった。コンテスト後に管理人に指摘され、リアクティブを問題文から消す羽目になった。クエリ先読みしても大して解法が増えなそうだったので、コンテスト後に問題文から全削除した。

 

D問題の解説が間違っており、数人の時間を無駄にした。数学的にきちんと書いたつもりだったが、一箇所添字が間違っていた。コンテスト後、解説をそのまま忠実に実装したkmjpさんとpekempeyさんがWAを出しまくっていて申し訳なかった。

 

総じて、楽しくやりとりしながら作問できた上、勉強になったので良い経験だった。