(iwi)の日記

銅メダル獲得: 2012 ACM-ICPC 世界大会

22:09 |

ワルシャワで行われていた ACM-ICPC の世界大会にて，11 位を獲得し，銅メダルを受賞しました．日本チームのメダル獲得は 2003 年より 9 年ぶりになります．日本初の，3 人全員がレッドコーダーのチーム．日本で応援してくださった皆様の期待に応えメダルを獲得することが出来，良かったです．

OB/OG 会の皆様をはじめとし今まで指導してくださった皆様，特に世界大会で苦い思いをしそこでの反省を教えてくださった先輩方 (特に岩田)，本当に今までお世話になりました．我々のメンバーが以前のチーム達より単純に優れていたというわけでは決してなく，知見の蓄積によるコミュニティ全体としての成長の結果だと思います．（あと運）

メダルを獲得でき，皆様におめでとうと言ってもらえ，本当に嬉しいですが，一方で我々としては，これは納得の行かない結果でもあります．事前の過去問を用いた練習では，スコアが金メダル圏内から出ることは殆どなく，本気で金メダルを狙っていました．実際，序盤は本当に金メダル圏内に長らくつけていて，アドレナリンどばどばでしたが，後半で失速してしまい，2 問も書いたコードが受理されないまま終わってしまいました．本当に悔しい．コンテストが終わった後のチームは，完全にお通夜ムードでした．

我々は，5 年間，同じチームで ICPC に参加していました．少しずつ戦い方が変化してきて，最初の年と今を比べてみると，戦い方が全然違う．個人の能力の成長もありますが，それだけではなく，チームとして本当に成長し，チームで戦うということはどういう事がようやく分かってきたのだと思います．最初のうちは，「3 人いるのに PC 1 台しかないなんてふざけてるな」と思っていましたが，今では，それを活用できるようになり楽しめるようになりました．非常に面白い体験ができたなあと思います．

年齢制限により，ICPC はもう引退です．先輩たちがしてくれたように，我々も，上記の点のような得られた知見を次の世代に伝える等，日本チームを応援していきたいと思います．まずは近いうちに自分の意見や反省をまとめたエントリを書きたいところです．

プログラミングコンテストでのデータ構造 2

18:16 |

情報オリンピックの春合宿で「プログラミングコンテストでのデータ構造 2」というタイトルで講義をさせてもらいました．スライドは以下になります．

平衡二分探索木の話と動的木の話をしました．アルゴリズム的な説明だけでなく，実際にコードにする際に楽に実装するためのポイントにも重きをおいています．実装に関する話は，アルゴリズム系の講義資料等にはあまり書かれることが無いため，珍しい資料になっているかと思います．（そもそもとして動的木の話は珍しいですが…）

「プログラミングコンテストでの」というタイトルになっていますが，平衡二分探索木・動的木が本当に必要になる問題は少々稀で，プログラミングコンテストに関する話としてはかなり進んだ話になっています．一方，プログラミングコンテストに限らず，それらを実装したいと思っている人には少なからず役立つと思います．

タイトルの末尾に「2」がついているのは，同タイトルの講義を一度やっているからです．その時は，Union-Find 木，セグメント木，バケット法の話をしました．その時の資料も公開していますので，よければご覧下さい．

• http://d.hatena.ne.jp/iwiwi/20100328/1269790390

プログラミングコンテストチャレンジブック 第二版 発売中

22:28 |

第二版，発売しております！よろしくお願いします．

第二版の紹介は以下の記事を見てもらえればと思います．

• 第二版が出ます！プログラミングコンテストチャレンジブック - (iwi)の日記

ちなみに，新宿の紀伊国屋さんでは先行発売がされていました．

• 【新宿南店】どこよりも早く先行発売！『プログラミングコンテストチャレンジブック　第２版』 | 本の「今」がわかる 紀伊國屋書店

追記

Twitter でつぶやくと第二版が貰えるプレゼント企画がやってます．2/6 までです．欲しい方はどうぞ．

• Twitterで応募 -『プログラミングコンテストチャレンジブック』プレゼント | エンタープライズ | マイナビニュース

上のサイトでは 2 冊をプレゼントになっていますが，4 冊に増えたようです．

• Twitter のつぶやき

TeX で作った pdf にフォントを埋め込む

15:39 |

原稿提出が pdf の際，フォントを埋め込めと言われますが，僕は意外と苦労したので，方法をメモっておきます． 多分主に Times-Roman と Helvetica を埋め込むのに苦労． 環境は Ubuntu 10.04．

続きを読む

大規模グラフアルゴリズムの最先端

15:00 |

昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります．

当日は Ustream もされており，録画された発表もご覧になれます．

• http://www.ustream.tv/recorded/19713623

内容の流れとしては，以下のようになっています．

• 導入
• アルゴリズム界隈での話題
  • 最新の研究動向
  • 道路ネットワークでの最短路クエリ処理
    • 基礎的な手法：双方向 Dijkstra，A*, ALT
    • 最新の手法：Highway Dimension + Hub-Labeling Algorithm
• DB 界隈での話題
  • 最新の研究動向
  • 複雑ネットワークでの最短路クエリ処理
    • 基礎的な手法：ランドマークを用いた最短距離推定
    • 最新の手法：Core-Fringe 構造の木分解による活用
• HPC 界隈での話題
  • 最新の研究動向，Graph500
  • SMP マシンでの並列 BFS
  • クラスタでの分散 BFS：1D/2D 分割法

交通ネットワーク・ソーシャルネットワーク・Web グラフなどの大規模なグラフを処理するプラクティカルなアルゴリズムに関心があるアカデミックコミュニティとして，アルゴリズム界隈，DB 界隈，HPC 界隈を取り上げ，それぞれでの話題について触れています．最初に全体的な研究動向に触れ，特に 1 つのトピックとして最短路に関連した問題を紹介し，定番となっている手法と最新の手法について触れています．特に，最新の手法としたものは全て 2010 年以降のものとなっているので，結構ホットかもしれません．