CODE QUEST Normal, Extra 全問解説

問題

geek-out.jp

割と面白かったです。

毒沼ノ試練・超毒沼ノ試練

概要：フィールドを勇者が歩いて魔王までたどり着く。始め勇者はHPが36であり、魔王にたどり着くときにはHP50以上である必要がある。フィールドには、死神・毒の沼・回復エリアの3つがある。勇者は4近傍に移動可能であり、毒の沼ではHP--, 回復エリアではHP++である。死神にあたってはならない。このような操作列を構成せよ。

解法：chokudaiサーチすると2分くらいで解が見つかる。

docs.google.com

圧縮ノ試練・超圧縮ノ試練

概要：ag?からなる文字列が与えられる。?はaかgのどちらか好きな方に変更することを想定する。agからなる二値文字列について、aaaaaはa5に、gggggはg5に、aggaggaggは(agg)3のように圧縮できる。文字列を最短に圧縮せよ。

解法：区間DPで厳密解が求まりそうだが、ちょっとサボって全探索＋目でぐっと睨むをやった。

docs.google.com

連鎖ノ試練・超連鎖ノ試練

概要：最長しりとり問題を解け。

解法：実は最長しりとりは求められていなくて、DFSで適当に1分回すと求まる。日本語つらいのでpythonでやる。

docs.google.com

狙撃ノ試練・超狙撃ノ試練

概要：マッチしてはいけない文字列集合とマッチすべき文字列集合が与えられるので、それを満たす正規表現を作れ。

解法：Easyは普通にやる。Hardは「かつ」のパターンを知っていますか問題。

docs.google.com

ROBOMECH2017 参加報告

概要

ROBOMECH2017@郡山に参加しました。ROBOMECHは1300人以上のロボット技術者が集まる査読なし国内学会です。

僕は、「開リンク系の O(log2 n)非同期運動学計算法」というタイトルで発表しました。 10万関節くらいのロボットを想定すると、全センサを一度に集めること自体がオーバーヘッドです。センサを集めるのに忙しくしている間に、衝突など即時対応しなければならない事態が起きても、対応できません。そこで、一部のセンサ情報だけで、ロボットの状態や制御を正しく更新することが必要となります。これを高速計算する手法を提案しました。

競技プログラミングの人にわかるように書くと、行列を木構造に載せて、(1)行列更新 (2)パス上の行列上の積を出力、の2種類のクエリをHL分解でオンラインにした、というだけです。n<10万, q<10万。

結構共同研究の話ができて、3年前からの成長を感じました。

郡山では、ラーメンを5杯と日本割烹(7500円)を食べました。日本割烹のカウンターの隣で座ってたのが、僕の好きなロ万というお酒の酒造の社長さんでした。接待中だったので話しかけはしませんでしたが、面白い話がいっぱい聞けました。

目次

面白かった発表（特選）

ヒトの寝返り動作を規範とした索状移動機構の研究

ヒト寝返り動作計測から、3自由度寝返りロボットの制御。ヒトから抽出したスキルは、関節の動かし方の順序の抽象度。

静電植毛により耐久力が飛躍的に向上したMckibben型人工筋肉の開発

ゴムに毛を生やすだけで耐久性が20倍に向上（5万回->100万回）

膝を拘束しないパワードスーツと装着車の足の間に働く力情報を用いた状態推定に基づくアシスト制御

足先に発生する力の反力の方向へ速度を出す、というよくわからない制御を行うといい感じに歩行をアシストする。発表者は「なんでこれでうまくいくのかわからない」と言っていたが、手応え最大化制御の良い数学モデルになっているような気がする。

ヒトの手部筋骨格モデルを用いた力学的負担の最小化に基づく物体把握姿勢の生成

手の筋骨格モデルと1種類物体について、どんな持ち方(6種類)をすれば一般化力最小で持てるのか？を数学的に解析。これがヒトの実際の持ち方と一致するかを検証しようとしたが、これは一致しなかったというネガティブリザルトが得られた。僕の修士論文に近く、やっぱり0空間あるからそりゃね、という話を著者としていた。

ホームロボットのための転倒時起き上がり機構の解説

3輪台車のボディが風船起き上がり人形。転んだら車輪をたためば勝手に起き上がる。

コーティング式触覚センサの開発

円筒局面にスプレーで吹き付けると触覚センサになる。一次元。二次元のElectrickと何が違うのだろう？？ とりあえず僕のスマート円柱実験に使えそう。

フリースローにおける人の運動の感度解析と設計

軌道を与えると、話した瞬間などダイナミクスの拘束条件が変わる前に、初期状態からそのようなタイミングが目的達成に重要な変数化を算出。その結果、熟練者らしい動きの動画を生成することが成功。

イヌの軌道奇跡のための歩容とIMUを用いた速度推定

イヌのZ方向振動をFFT&Cut-off周波数を定める。すると最低周波数のモードが取れるので、これで極地検出する。この検出結果が、加速度0の点なので、ジャイロ0点が定まる。（今まで、人の歩行ではできていたが、イヌではやられていなかった）

タフロボット用軽量・低摺動・大出力油圧アクチュエータによるロボット脚の駆動

タフロボット用という意味がわからないが、鍛造マグネシウム合金を用いて3.6kg21MPa（！！）のジャンプロボット実現

RobotEye（ViewPLUS）

メカニカル高速3Dレーザスキャナ。1000万円で500m（リフレクタで1.3km）の範囲！信じられない。測定範囲を動的に限定することができて、空間分解能と精度を簡単にスケジュール可能。

ロハスの家

ロハス＋家の研究。家は大手シェアが小さい（気候風土にあったものが求められるので）。ロハスの家＝エネルギ自立＋材料自立＋水自立＋快適健康空間。 (第一号) ハイテク機器によるエネルギ自立＋地元材料 (第二号) パッシブデザイン（太陽の受け止め方を変える。ハイテクには頼らない）。材料自立（再生可能材）。 (第三号) 上記の融合。微生物でのディスポーザー＋地中熱（太陽エネルギーの時間差）。地中熱は地質の関係もあり（崩れるので）、他の国は国策でやっているのもあるが、日本は極めて普及率が低い→家の杭から地中熱を得る機構。 ハイテク機器はレア素材必要では？地元の素材を使う、というのには意味があるのか？ 水ってなんで言ってるの？→更新需要がメンテナンスコストを上回り、水インフラを保てないので。 一軒家なので、まだ東京だときつそ 冷暖房の普通の家との差のグラフとか、エネルギー消費量のグラフみたいなのがないとよくわからない

おもしろいもの

摩擦的特性を離床したロボット関節のための磁気粘性流体デバイスの開発

磁性流体は多層構造で大型だったが、両方固定したプレート1枚で摩擦制御できるようになった。ロボット先端クラッチに使える。

動きの人らしさ

トルク変動を時間方向に積分すると人間っぽい動きになる。ロボット実装としては、ダイナミクスから目標角速度計算をきちんと計算している。トルク最小だと実際に人間のやる動きとはかけ離れた運動になっているのが印象的だった。

救助犬に搭載した全方位カメラを用いた視覚オドメトリ

地図取るだけならイヌのモビリティに頼ったほうがいいよね。

ロボット間通信を可能にした円弧歯車形モジュラーロボットの設計開発

モジュラーロボットはダイナミクス活用するのが通信などあり大変。幾何学拘束を歯車形ロボにすることで陽に活用し、運動方程式を避ける。見た目が面白い

群ロボットシステムにおける自己位置推定法

各個体は、近くのロボットへの距離を知っている。各個体は、群ロボットの原点からの自己位置を推定する。方法は、予測距離以上なら近く、そうでないなら遠く、別途ランダムノイズを加える。

音場制御によるロボットナビゲーション

ロボットは音センサを搭載する。音が聞こえるか聞こえないかで行動を異とする。すると、場に従ったロボット制御が可能。

ロボットを介した人から人への作業教示におけるインタラクションのモデル化

人からロボットへの教示を行う。ロボットは、タスクを記号論理で記述し、曖昧性があるかを判定し、曖昧性があるならばそれを低減するような質問を返す。質問を返すときに、ロボットが関連位置を指を指す。学習済みのロボットは、逆に人に教えることができるというのがビジョン。

磁性流体を用いた逆可動性を有するベーン式ロータリーアクチュエータの開発

そもそも磁性流体アクチュエータがない（ほんまか？？）。可動性を有するとと言っているが、実際には摩擦を制御することもできるらしい。

剛性可視化マーカ機構

圧力をかけて剛性を固くするとジャミングのせいで色がつく

移動ロボットにおけるCANの脆弱性をついたDOS攻撃となりすましの実証

CANをハック。実際ハックしてなりすましができちゃったので、危ない。原理上乗っ取りもできる。環境次第ではセキュアなCANを使う必要。

3輪全方位移動内部ユニットを用いた球体型移動ロボットの走行方向制御

オムニ版スフィロ。ノンホロだから横に動いたり、振動低減ができたりする。こいつでサッカーしたくない？？

多孔質粉体の縮尺を利用したJamming Gripperの提案

コーヒー豆ではなく、縮むスポンジを使ったJamming。力は出ないが、小さいものもつかめる。縮むので吸盤の吸着もできる。

偏心構造を利用した小型かつ高性能な磁気式アブソリュートエンコーダの開発

ABS Enc.は位置決めセンサがいる。なので回転中心を偏心させると位置決めが要らなくなる。（光学式は埃が入るのでよくない）。モータにつけることを想定しているので、モータの磁場をキャンセルする技術も裏でやっているらしい。

手形状と物体形状の相関を利用した深層学習に基づく画像からの把持形状推定

単眼カメラ画像->鎌倉の把持形態をDNNで推定。妥当な指の位置みたいなのが予測できるといいよね、という話を議論した。

インフラ構造物に作用する応力の見える化〜ひずみ可視化シート〜

貼るだけでひずみが可視化ができる工具。

操作量の次元を考慮したクレーン吊り荷の制振制御の一設計手法

クレーンの荷物にIMUを載せておくだけで、熟練のクレーン制振制御を自動化

自動鉄筋結束ロボットの開発

そのまんま。こんなロボットの応用があったのだなあ。

操作者のプラニング技能の定量化に関する研究〜操作手順と操作意識に着目した特徴量の抽出〜

研究自体は企画倒れしているが、優先・視覚・まとめ運びなどのスキルを定量化し、教育に利用しようとしている気持ちは面白かった。

作動サスペンション機構を有する独立二輪駆動車両による斜め侵入での段差党派性に関する実験的検討

受動輪の旋回軸を固定することで、斜め侵入踏破性が向上する。

イオン導電性高分子・貴金属接合体を用いた形状と表面粗さを同時計測する触覚センサ

ひげ状触覚センサのIPMCから、形状とその微分による表面粗さ同時計測

多機能フリッパーアームを有する不整地移動体の開発

おにぎり型クローラで10cmレベルのかなりの不整地を移動可能。これ自体はそんなに凄くないが、倒立伸子に拡張可能だと思っていて、コミュニケーションロボットとかがもっとロバストになるといいなと思った。

面状全方位クローラ移動機構

変態機構で、2つのモータで全方位クローラを実現。クローラのそれぞれが横方向に動くベルトになっている。

リンク上の任意の位置に関節を配置可能な移動関節機構

リンク長を目詰まり現象的な感じでリンク長を変更する。

流体アクチュエータの駆動を目的とした微粒子励振による小型三方弁の開発

ピエゾで振動すると、目詰まりが解消されて弁ができる。ピエゾの周波数を変えると、近くの弁でも独立に弁の制御ができる。

防塵性を考慮した可視光・遠赤外線同軸カメラシステムの解析

赤外線は霧・砂塵環境下でも意外と見える。RGB-Infraredカメラをマジックミラーで実現しつつ、防塵性をサランラップで実現（サランラップは電子レンジから考えて赤外線も可視光も透過する稀有な素材）

蓄電・送電システムに搭載するフライホイールの開発

不安定な発電（太陽光など）は、瞬時的な電力が送られることがある。しかし、電池は瞬間電力に向かないので、余った電力をフライホイールでメカ的に蓄電。

ウェアラブルディスプレイのための手首凹凸計測による手指の動的運動認識

光学式触覚センサを腕に巻きつけて、指の形を推定。

3 DoF Wrist Mechanism for Tough Robotics by Hydraulic Artificial Muscles

油圧人工筋の3軸回展メカ。3軸目は結構つらいので、柔らかさを活用して今までのものを巻きつける形に配置、

Spring-Cam機構を用いた可変剛性足関節装具

歩行の足は非線形バネ的である。具体的には地面を蹴るタイミングでの剛性が線形バネより高い。これをカムで再現、微調整機能もつけた。

遠隔操作移動ロボットのための試験場の開発

原子力・災害救助用フィールドを作った。フィールドには、段差の高さ可変な階段や、不整地、その他、多くの種類がある。更には、通信障害を恣意的に起こす環境もある。水槽は温度・濁り度・水流を制御できる。これらによって、実機投入前にロボットの踏破性能の定量評価が可能。楢葉の原子力研究開発機構が開発したもので、利用者を現在募っている。5000円/1日（大学は半額）で使える。

高速ビジョンを用いた対象物体の実時間計測による人間機械協調の実現

石川研の高速ビジョンシリーズ。タスクは板を人間とロボットで持つ。人間が「遅れている」と認識するよりも早く、ロボットが人間の行動に馴染むように動力学計算と制御を行う。

人体荷重下を無摺動で滑り込むSlip-inマニピュレータの動作特性

インフレータブルロボットを、寝そべった病人や高齢者の背中や腰に「すべりこませ」、腰の褥瘡を解消する。

MRクラッチと空気圧人工筋肉を用いた装着型4自由度力覚提示装置の提案

人工筋とMRクラッチでアクティブ・パッシブな力覚を提示するマッスルスーツ…なのだが、コンセプト先行で5kgもある。あと、これは軽いマッスルスーツにもなっている（発表者はなぜか否定していたが）。

5軸球面パラレル機構の逆運動学と運動伝達性の解析

力覚提示用の5軸力を出力するメカを作る。変態設計。

分散運動学計算フレームワークに基づく運動学計算シミュレータの開発

研究の主張は意味不明（分散でない）だったが、逆運動学を収束計算で解く簡便な方法は面白かった。僕の手法をこれに適用すると、観測段の頻度が上がるので逆運動学が高速になる可能性がある。

外れ値処理を用いた確率的位置情報の統合による移動ロボットのロバストな位置推定

PFにセンサ確率密度を突っ込むときに、P(位置|センサ情報)の分布を計算し、多数決的に分布が違うものをウィルコクソンの検定で棄却する。ロバストネスが下がるが、GPSのような平均して外れ値が出るようなケースに使える。

Qualisys（企業）

厳しい環境で使えるモーキャプ。fMRI内部でもできる、水中でもできる、ケーブルがデイジーチェーンで楽、ソフトが軽い。

楢葉遠隔技術開発センター

日に5000円（大学は2500円）で、超すごい試験場が利用可能。階段・水中（温度・濁り度・塩分度）・段差など。

YVT-35LX(北陽)

三次元測域センサ。IMUが乗っていて自動で3D測定データを補正できる。

金属3Dプリンタ(富士通)

金属を5軸板上で、アーク溶接ワイヤーを溶かしながら積み上げて造形、そのあと5軸フライスで後処理する。ワークを全部削るよりも時間が早い。1500万円。

圧力分布測定システム（novel）

足に埋め込むインソール型分布圧力センサ。

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

これはCompetitive Programming （その2） Advent Calendar 2016 - Adventar の5日目の記事です．

概要

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

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

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

自己紹介

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

f:id:intelhamko:20170117083343p:plain

f:id:intelhamko:20170117083432p:plain

 

過去の話

2005年

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

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