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

競プロ歴半年のハムスターが、競プロのおかげで留学中に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、ありがとう競プロ、ありがとうみんな。