TopCoder Open 2013 Round 3 進出 ＆ レーティング世界 4 位
昨夜の TopCoder Open 2013 Round 2A で 13 位を取り，Round 3 に進出しました．Round 3 には 2 回のサブラウンドがあり，どちらかで 12 位以上を獲得すれば世界大会進出です．
レーティングは 3297 に上昇． meret, tomek, Brunduk1 を一気に追いぬき，世界 4 位になりました． 自分の上には，現在，tourist, Petr, ACRush という人間卒業勢しか居ません（そして残念ながら彼らとは大差です）．
修士課程修了 ＆ 研究科長賞獲得
無事に修士課程を修了することができ，本日学位記を受け取りました．また，一緒に，情報理工学系研究科の研究科長賞を頂きました．
学位記授与式
学部の卒業式に相当する学位記授与式は，安田講堂が改修中のため，有明コロシアムで開催されました．僕らの学年は，東北地方太平洋沖地震の影響で学部の卒業式も中止になっておりまして，2 度も例外的措置を体験したことになります．
大規模ネットワークの性質と先端グラフアルゴリズム
本日，PFI セミナーにて「大規模ネットワークの性質と先端グラフアルゴリズム」というタイトルで発表をさせてもらいました．スライドは以下になります．
大規模ネットワークの性質と先端グラフアルゴリズム
View more presentations from iwiwi
Ustream の録画もあります．
内容としては，以下のようになっています．
- 現実世界のネットワークの特徴量と性質
- 次数分布
- 平均距離
- クラスター係数
- その他の特徴量
- 木っぽさ
- それらの性質を活用したグラフアルゴリズム
- セオリー方面
- 近接中心性の近似
- コンパクトルーティング
- 支配集合問題の近似
- プラクティカル方面
- 最短路
- 密部分グラフ列挙
- 可視化
- セオリー方面
タイトルは 1 年前にやった PFI セミナーと似ていますが，内容はあまりかぶっていません．今回は，グラフの性質とアルゴリズムの関係に焦点を置き，まずソーシャルネットワーク等のグラフが典型的に持つ性質を述べ，そのあとで，そういった性質を活用して良い性能を達成するアルゴリズムを紹介しています．
グラフの性質として述べたものは，基礎的なものが多いので，スケールフリーやスモールワールドといったキーワードなど，こっち方面の専門じゃない方でも聞いたことがある人も多いんじゃないかと思います．一方で，紹介したアルゴリズムは新しめのものとかちょっとマニアなものとかになってると思います．実際，僕が知る範囲では，こういったグラフの性質を活用したアルゴリズムというのはあまり多く無いと感じられ，かき集めるのが少し大変でした．
世界で闘うプログラミング力を鍛える150問 〜トップIT企業のプログラマになるための本〜
先行発売のお知らせ (11/7 追記)
以下の店舗で先行発売が行われているらしいです．
- 紀伊國屋書店 新宿本店 (https://twitter.com/KinoShinjuku/status/265658160222724096)
- 紀伊國屋書店 新宿南店 (https://twitter.com/kino_Minami/status/265405470548844546)
- ジュンク堂書店 池袋本店 (https://twitter.com/junkudo_ike_pc/status/265677297430978562)
- 有隣堂 ヨドバシAKIBA店 (https://twitter.com/yurindo_akb/status/265648944745426945)
- 丸善 丸ノ内店
なお，電子書籍版の発売も予定しているそうですが，調整中とのことで少し後になりそうです．
原著は既に第5版が発売されているアメリカのベストセラー書『Cracking the Coding Interview』の翻訳を行いました．11/13 発売らしいです．翻訳は，『Short Coding』の Ozy さんと『プログラミングコンテストチャレンジブック』の俺・岩田・北川で行いました．
世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~
- 作者: Gayle Laakmann McDowell,秋葉拓哉,岩田陽一,北川宜稔,Ozy
- 出版社/メーカー: マイナビ
- 発売日: 2012/11/13
- メディア: 単行本（ソフトカバー）
- 購入: 143人 クリック: 7,806回
- この商品を含むブログ (48件) を見る
本書の内容を一言で言うと「採用面接の攻略本」です．面接でエンジニアより出題される技術的な問題に上手く答えるために，アルゴリズムとデータ構造を中心とした様々な知識と考え方，そして問題例と解法が網羅されています．
問題の大部分はホワイトボードでのコーディングを想定した問題で，ひと捻り効いた問題もあり，プログラミングのパズルとして，プログラミングをする全ての人が楽しみながらコンピュータサイエンスの基礎知識や活用法を復習できる本になっていると思います．難易度は，プログラミングコンテストチャレンジブックに比べるとかなり易しめです．
日本でも一部では既によく知られており，ブログなどで取り上げられています．
マイナビブックスのページは以下になります．
以下は，監訳者まえがきの抜粋です．
本書はアメリカで既に第5版が出版され、Amazon.comでは100件を超えるレビューを持つベストセラー書の日本語版です。Google、Microsoft、Appleといった有名IT企業でエンジニアとして働き、多くの採用プロセスに関わってきた著者によって、より人気のあるIT企業の面接に合格するための、いわば「採用面接の攻略本」として書かれました。
しかしアメリカでのヒットもそのはず、本書の内容は「採用面接の攻略本」にしておくのはとてももったいないものになっています。それどころか、コンピュータやプログラミングを知るすべての人が、アルゴリズムを中心としたコンピュータサイエンスの基礎知識と活用法を楽しみながら学べる本と言えるでしょう。
本書はアメリカのIT企業における採用に関する詳細な説明から始まりますが、主な部分は面接で出題される技術的な問題例と、その解説から成っています。問題の大部分はホワイトボードでのコーディングを想定した問題で、プログラムを書く問題ということになります。豊富な経験を持つ著者が選りすぐった問題であり、どれも基礎的な知識をちょっとしたひらめきにより活用する良問ばかりです。
アルゴリズム的な問題と解説を中心とした本として我々は『プログラミングコンテストチャレンジブック』を執筆し、広い層に好評を博しました。本書はそれに類似した位置づけと言えます。特に知識の解説だけでなく、その活用法に重点を置いているという、珍しい特徴を共通して持っています。一方、我々の本ではプログラミングコンテストの問題を扱っていたのに対し、本書で扱われているのは面接の問題であるという違いがあります。本書の問題はトップ企業が面接で使う問題であり、そこにはトップ企業が求める能力が凝縮されています。また、仕様の曖昧な部分を自分で適切に設定する問題や、特殊な環境を想定したプログラムを書く問題も面接ならではと言えるでしょう。さらにオブジェクト指向設計、並列・分散システム、データベースというような発展的なトピックの問題までもが含まれています。
問題を通じてアルゴリズム等の力を身に付けたい人、プログラミングのパズルを楽しみたい人、近々面接を受ける人、逆に近々面接を行う人、アメリカの企業の文化に興味がある人など、さまざまな人に自分の読み方で活用してもらえればと思います。
以下，目次です．
- I．面接の流れ
- 概要 / どのように問題が選ばれるか / 面接準備予定表 / 評価プロセス / 正しくない答え / 面接時の服装 / 失敗トップ10 / よくある質問
- II．面接試験の舞台裏
- III．特殊な状況
- 経験のある志願者 / テスターとSDET / プログラム／プロダクト・マネージャ / 開発リーダー／マネージャ / ベンチャー企業
- IV．面接の前に
- 良い経験を得る / ネットワークを築く / 履歴書の書き方
- V．行動に関する質問
- 準備 / 対策
- VI．技術的な質問
- 準備 / 対策 / アルゴリズム5つの手法 / 良い、きれいなコードとは
- VII．オファーとその後
- オファーと不採用の取り扱い / オファーの評価 / 交渉 / 仕事をしていく上で
- VIII．問題
- [データ構造]
- Chapter 1 配列と文字列
- Chapter 2 連結リスト
- Chapter 3 スタックとキュー
- Chapter 4 木とグラフ
- [考え方とアルゴリズム]
- Chapter 5 ビット操作
- Chapter 6 頭の体操
- Chapter 7 数学と確率
- Chapter 8 オブジェクト指向設計
- Chapter 9 再帰と動的計画法
- Chapter 10 スケーラビリティとメモリ制限
- Chapter 11 ソートと探索
- Chapter 12 テスト
- [知識ベース]
- [追加練習問題]
- Chapter 17 中級編
- Chapter 18 上級編
- [データ構造]
- IX． 解法
- [データ構造]
- Chapter 1 "配列と文字列"の解法
- Chapter 2 "連結リスト"の解法
- Chapter 3 "スタックとキュー"の解法
- Chapter 4 "木とグラフ"の解法
- [考え方とアルゴリズム]
- Chapter 5 "ビット操作"の解法
- Chapter 6 "頭の体操"の解法
- Chapter 7 "数学と確率"の解法
- Chapter 8 "オブジェクト指向設計"の解法
- Chapter 9 "再帰と動的計画法"の解法
- Chapter 10 "スケーラビリティとメモリ制限"の解法
- Chapter 11 "ソートと探索"の解法
- Chapter 12 "テスト"の解法
- [知識ベース]
- [追加練習問題]
- Chapter 17 "中級編"の解法
- Chapter 18 "上級編"の解法
- [データ構造]
- X.謝辞
- XI.索引
- XII.プロフィール
……この内容では簡単すぎるという方は，以下の書籍をどうぞ．
![プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?](http://ecx.images-amazon.com/images/I/41bHxtpurqL._SL160_.jpg "プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?")
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本（ソフトカバー）
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る
- 作者: Ozy,やねうらお
- 出版社/メーカー: 毎日コミュニケーションズ
- 発売日: 2007/08/09
- メディア: 単行本（ソフトカバー）
- 購入: 5人 クリック: 306回
- この商品を含むブログ (68件) を見る
TopCoder Open 2012 : Spirit Award 受賞，アルゴリズム部門 4 位タイ
10 月の第一週にフロリダにて開催されていた TopCoder Open 2012 に，アルゴリズム部門のファイナリストとして参加していました．
Spirit Award 受賞
大変光栄なことに，今年，TopCoder Open Spirit Award を受賞しました．これは，参加者による期間中の投票により決められる賞で，各自，アツいと思った人やコミュニティに貢献している人へ投票します．英語が堪能でないこともあり，自分は英語圏の方々と比べ交流等の活動では活発なほうではなかったと思うので，オンサイトでの戦いっぷりが評価され人気を集めたのだと受け止めています．大変ありがたいと思います．
日本人がそこそこ参加しているので，組織票の影響なのではないかと思われるかもしれませんが，知る限り日本人からは一票のようですｗ（自分も驚いて一瞬そう思いました）
Wildcard Round
自分は，2 戦目の Wildcard Round で特に高い注目を受けました．上の画像のように，1000 点問題を唯一解き，1 位を取りました．他の多くの参加者が最も簡単な 250 点問題から解く作戦の中，自分は 3 戦とも 1000 点問題から開く戦略で挑んでおり，この回はまさにその戦略が炸裂した結果と言えます．
この回の 1000 点問題は，Petr が実況で珍しくわからないと言っていたり，後から他の選手らもかなり取り組んでいながら提出ができていなかったりと，かなり難しい問題と見られていました*1．しかも，より簡単とされる 250 点問題・500 点問題への解答が，次々と撃墜やシステムテストで落ちていく悲惨なスコアボードにおいて，最後に発表された僕の 1000 の結果は正解であり，大変に興奮しました．人生においてこんなに興奮する経験は確実に数えるほどだろうと思います．
その他：Semifinal Round，Championship Round 等
初戦の Semifinal Round では，序盤で 1000 を諦め，250 と 500 を解いて 4 位を取り，Wildcard Round に進出しました．あと 5 点で Wildcard ではなく直接 Championship Round 進出だったため，少し悔しく思っていました．（結果的に Wildcard Round が楽しかったのでよかったのですが．）
Wildcard Round で 1 位を取ったため，最終戦である Championship Round にも進出することができました．去年の TCO'11 でも Championship Round に進出しており，二年連続になります．二年連続で最終戦に進出しているのは，実は僕と ACRush だけで，より格上の選手たちであっても安定して勝ち残るのは非常に難しいのだということがわかります．（ちなみに，自分の去年の通過の仕方も少し似ていて，Semifinal で唯一 900 点問題を正解し通過したのでした．）
しかし，Championship Round は，残念ながらあまりうまく行かず，0 点で 4 位タイになりました．1000 点問題を最初にそこそこ詰めたのですが，あと一歩のところがわからず，500 に移ってしまいました．さらに，500 は比較的苦手なタイプの問題であるにもかかわらず，確証のないシンプルな解法が思いつき試したくなってしまい，そのまま実装しそれを弄り続ける泥沼にハマってしまいました．進出できること自体がそもそもとして非常に貴重な機会であり，そういう場でこういう戦いをしてしまい，大変悔しい思いをしています．
コンテスト以外では，オーランドということで，ディズニーワールドやユニバーサルスタジオに遊びに行きました．どちらも楽しかったです．
*1:自分はすんなりとアプローチできたため，比較的簡単だと思い，他の人も解くだろうと思いむしろ焦っていました．ラッキーにも，自分と相性の良い問題だったようです．
勉強か？趣味か？人生か？―プログラミングコンテストとは
情報科学若手の会に学生特別講演として呼んでいただき，プログラミングコンテストに関する話をさせて貰いました．
プログラミングコンテストについて理解と関心を持ってもらうことを目指しました．簡単な紹介からはじめ，面白さや問われるものについて話し，最後には「プログラミングコンテストの真相」と題して皆が気になっているかなと思う質問に答えてみました．
会場の雰囲気は非常に明るく，話していてとても楽しかったです．また，終わったあとも，多くの人から話しかけてもらい，面白かったと言ってもらえたり質問をもらったり，とても嬉しかったです．
また，発表させてもらったことだけでなく，他の人の発表や交流もとても有意義でした．いつもツイッターでひっそり眺めている人たちというのが結構居らっしゃって，お話をさせてもらうだけでも非常に幸せでした．
