Hatena::Grouptopcoder

(iwi) { 反省します

TopCoder: [[iwi]] / Twitter: @iwiwi

2014-07-30

ICFP Programming Contest 2014 感想など

15:44 | ICFP Programming Contest 2014 感想など - (iwi) { 反省します を含むブックマーク はてなブックマーク - ICFP Programming Contest 2014 感想など - (iwi) { 反省します ICFP Programming Contest 2014 感想など - (iwi) { 反省します のブックマークコメント

去年同様,適当に書きたいことだけ書きます.


チーム

去年と完全に一致です.今年は 6 人とも 72 時間参加.

今年もチームの持つ幅広い面での力が発揮でき良かった.あと,チームが ICFPC にだいぶ慣れてきてかなりスムーズになってきた.皆,自分が何をやれば良いのかや他人の好み・使える/使えない(使うことを拒む)ツール等を概ね理解している.


やったこと

言語の策定などの方針会議(全員)
  • 例年問題文は長いので問題を解読するのに時間がかかる(仕方ない).CPU 仕様が 2 つもある.
  • GHC (Lambda-man AI) 用のプログラミング言語の策定が最重要の議題
  • CPU 仕様を考えると Lisp にしたくなる(し実際に Lisp 系を採用したチームも多かったっぽい)ので弊チームでも Lisp という声は上がる
  • しかし C ライクのプログラミング言語を作ろうという提案があり,検討の末,そちらを選ぶ
    • メンバ(特に AI を書くことになるであろう岩田とチョクダイ)の慣れ具合からいって Lisp は多分作った後がヤバイ
    • C ライクな言語でもコンパイラ作業はそんなにやばくなさそう
    • C++ へのトランスレータを簡単に作れる仕様にしておけばインタプリタ無しで実行したりシミュレータと結合したりできる
  • プログラミング言語はチーム内で B と呼ぶことに決定した
    • 勿論 B という言語が昔存在したことは皆知っているので正式名称は B14 ということにした
コンパイラ(wata + iwi)
  • Lightning に AI を出すために最も重要な部品ということで集中的に開発するために岩田と俺でのペアプロで開発した
  • 岩田をメインコーダーとして Java で開発
  • 翌日午前 6 時頃にはだいたいできた
  • その後はちょくちょく機能追加しつつ使用
  • マシンの仕様を上手く活用してグローバル変数を実現したりした
    • 普通にやると,グローバル変数を置いた場所が何段親のフレームだかわからなくなるので LD/ST できない
    • 関数を呼ぶ際に毎回 LDF するのではなく,最初の init 時に全関数 LDF して RAP しておくと,親フレームが共通になるので,親フレームの変数をグローバル変数として用いることができる
トランスレータ(tos
  • トランスレータというか include すると B のプログラムがそのまま C++ でコンパイルできるようにするものを作ってもらった
  • これでライブラリ開発等が手元でテストできるようになったし,シミュレータと結合すれば爆速実行できるようになった
ライブラリ (tos + iwi)
  • 主にデータ構造などの共通のパーツを Standard B14 Library,略して SBL として提供
  • 初日に必要そうなものは一通り揃える
  • 間接アクセスがマシンに無いのでランダムアクセスのためのデータ構造として tree のアクセスコストが重要になる
  • というわけで 2 日目に俺が固定長(2べき)の tree のライブラリを再帰呼び出しを完全に展開したベタ書きアセンブラとして生成するスクリプトを書いた
    • get は一段 5 clk で処理できる(256 だったら 8 段なので 40 clk +定数ちょい)
    • set はもう少し複雑(葉にたどり着いた後で新しいツリーをまた構築しないといけない)で確か一段 12 clk
シミュレータ,評価システム (imos + sulume)
  • コンソールでコマンドを打ち込むとエスケープシーケンスとかの色付けを使ってコンソール上でいい感じにゲームが表示されて見れる
    • 公式の Javascript 実装は計算を結構行うラムダ AI を突っ込むととてもじゃないけど遅すぎてやってられない
    • 一方,我々の実装ではサイクルリミットぎりぎりの AI でも割と見てられるような速度で動く
  • 公式の Javascript 実装と動作を完全に一致させた(!)
    • 公式 Javascript のキャンバスの出力をキャプチャしたものをデータにしてそれと完全に一致するように自動でテストを行う
    • 公式の処理系は undocumented っていうかもうバグとしか思えないものが結構あるのでそれをわざわざインプリするという作業があったらしいw
    • しかし公式 JavascriptHaskell かなんかから生成されているっぽいので実際の評価も恐らく全く同じ環境で行われるためこれは有益
  • その後,適当にラムダマン AI やゴーストを比較するために一杯実行してデータを並べるシステムができた
    • イモスが多分また金に物を言わせて分散しまくってる(いい話)
ゴースト AI (chokudai → tos → iwi)
  • 初日は B コンパイラができるまでの暇つぶし?でチョクダイがグリーディに近づくものをとりあえず書いてた
  • その後トス先生がそれを少しいじって先回りするものを作っていた
  • 最終日気がつくといつのまにかトス先生もラムダ AI を作り始めていて誰もゴーストを更新してない
  • ゴーストもかなり重要だろうということで俺がゴースト担当に回ることになって色々いじっていた
    • 基本的にはグリーディに近づくのだけれどマンハッタン距離にちょっと手を加えると近づく速度が上がった
    • あとは食われないように逃げる,ID を使って若干の多様性を持たせて散開させる,ぐらいしかやる時間がなかった
ラムダマン AI (chokudai vs. wata vs. tos → chokudai + wata)
  • チョクダイの AI は周りを若干 BFS したりして見て評価関数や特別処理を激しく tweak している系だと思う(多分)
    • 結構いい感じに動いて敵からも逃げるしそこそこ取るんだけど取り残しが結構多くて大きな盤面になってくるとゴーストが弱くても全クリはできない
    • 特に,周りを少ししか見ないので,周りを食べ終わってしまうと敵が追っかけてきてくれたりしないと硬直状態になってしまって点が凄い低くなったりする
    • 試しに敵から逃げまくるゴーストっていうのを放り込んでみたらものすごく点が低かった
      • これ故に一時期は逃げまくるゴーストを提出するのが正解なんじゃという主張もチームの中で結構あった
      • 後述の通り対策が実装されると共にこれはやめた
  • 岩田の第一世代 AI は遠い薬への行き方も上手く把握して効率的な全クリを目指すもの
    • 本当は全体での BFS がしたいのだが計算コスト的にできない,ランダムアクセスのために log がかかるため
    • ので BFS の代わりに適当に伝搬させるアルゴリズムにより毎ターンちょっとずつ情報を更新する
    • 伝搬にすればリストをなめながらうまくやれば線形時間でできる
    • (ただし BFS も実はできたのかもしれない:https://twitter.com/wata_orz/status/494306461200027648
    • 結構きれいにごはんをたべる,ただし逃げたりは未実装なので敵に即食われる
  • 岩田の第二世代 AI は上の伝搬計算をローカルに限る代わりに敵の情報もそこに入れるもの
    • 敵から巧妙に逃げるしご飯も効率良く食べるのでかなり強い
    • が,計算コストがやばくてなかなかサイクルリミットに納められない,収めようとすると見る領域がかなり小さくなってしまって結果として弱くなってしまう
    • ギリギリまで粘ったが上手く行かず残念ながら諦めることに
  • tos 先生の AI は盤面の危険度をグローバルに評価する何らかの関数を作る感じだったっぽいが間に合わなくて断念っぽい
  • 最終 AI はチョクダイの AI に岩田の第一世代 AI を追加で組み込んで合体
    • 硬直状態っぽい感じ(長いこと点が取れない)になったら岩田にバトンタッチする
    • 岩田の AI でグローバルな視点によりご飯に向かう
    • ご飯を食べ始めたらまたチョクダイにバトンタッチ
    • (実は評価を行う暇なく提出したのだが,終了後に出てきた評価の結果を見るに)特に弱いゴースト相手での結果が凄まじく向上

感想など

何よりヤバかったのが最終提出.岩田が第二世代を諦め,それではバトンタッチ機構で行こうと決めたのが 20:00.岩田とチョクダイのバトンタッチ AI 最終版ができたのが 20:55.残りの 4 人で提出のための作業をできるだけ即座に行えるように構えていたが,俺が submit ボタンを押すころには 20:59 を示していて本当に手が震えていた.それまでに何度か提出を済ませてはいたが,バトンタッチ機構はみるみる進化して行っていたのでできるだけ最終版を出したかった.終了後に行った最終的な評価結果を見ても性能は明らかに向上していたのでチーム全体の最後のこの頑張りは報われたと思う,本当に良かった.(ま,もっと早く判断しろっていう話は勿論ありますが,第二世代も結構行けそうだった(し行けてたら明らかに超強い)から難しい判断だったし,結果オーライってやつです.)

ライバルであるチョクダイと岩田の AI が最終的に力を合わせお互いの欠点を補いあうって少年漫画的な展開で燃えますよね.

最初は若干劣化マラソンの年に見えなくもなかったけど,なんやかんや結構面白かった.普通に良かったと思う.変わった CPU 仕様や計算資源への絶妙な制限が普段と違う考え方を要求してくるのが(辛かったけど)やっぱり面白いんだと思う.あとこれは毎年 ICFPC に共通だけど,普通のプログラミングコンテストは AI なら AI を書くだけで終わるが,AI を書くためのツール(e.g., コンパイラ, 評価システム)の能力やそれを作るまでの時間というのがどのぐらいの AI を書けるかに寄与してくるっていう総合力勝負っていうか多階層っていうかそういうところがやっぱり楽しいなって思う.

いろんな要素がある年はやっぱり人数(及び人材の能力の幅)が効く.6 人を超えるといろんな面で破綻すると思うし,今年もチームは極めて最善に近かったと思う.個人的には今年はいろんな貢献ができてよかった.コンパイラ(Java)もオリジナル言語(B14)もシミュレータ用ライブラリ実装 (C++) もラムダマン AI アセンブラ(GHC)もゴースト AIGCC)もそれらを生成するスクリプト(Ruby)も触ったのでかなり色々やった.AI にも自分のアイディア(伝搬)も入ってるし.(まあ個人参加の人は当然全部やるわけだけど)

結果には正直去年ほどの自信はないけど,それでも結構期待してます.

2014-07-11

ICPC 国内予選 2014

01:26 | ICPC 国内予選 2014 - (iwi) { 反省します を含むブックマーク はてなブックマーク - ICPC 国内予選 2014 - (iwi) { 反省します ICPC 国内予選 2014 - (iwi) { 反省します のブックマークコメント

とりあえずコードを置いておきます.ちなみに逆順で解いたので逆順で見ていくと include が増えていく(一応 ICPC なので前準備テンプレは使わないルール).


A-D


E

http://ideone.com/9sN2Bk

葉は行く必要がない.葉を削除すると,残りの辺は大体 2 回通らないといけないが,始点と終点を結ぶ経路上の辺は 1 回で済む.従って,葉を削除した後のツリーで直径を求めれば良い.double-sweep を使った.線形時間.


F

http://ideone.com/z15rAo

辞書順最小を作る典型手法であるところの,「可能性の判定を行えるようにして,可能性を保つ最小のものを貪欲に加えていく」をやる.ただし,可能性の判定条件が非自明で面白い.

「サイコロ」と見た瞬間に「面倒くさいだけの問題か……」となっていた今までのイメージを払拭する,大きなインパクトを持つ 1 問……!


G

http://ideone.com/Wahx7b

よくある円上の線分アレンジメントみたいなやつ.制約が良心的で助かる.基本的には円周上を移動すればよい.始点と終点に線分を引き,その線分上も通れるようにする.


ちなみに

19:00 から焼肉の会があったので間に合わせるために頑張って解いた.2 時間ちょいぐらいで終わった (A の最終更新が 18:33) .本当は一人でやる予定だったが,横に偶然問題を読み解法を吐く機械(別名:岩田)がありどうしても出力が流れてくる状況であったので,俺は実質解法をコードにする機械であった.こんなに coding-intensive なコンテストを過ごすのは久々で疲れ果てた.

追記:後ろから解いたのは,時間で切り上げないといけないかもしれなかったので,序盤より終盤の面白い問題を優先して解きたいと思ったからです


f:id:iwiwi:20140712013758p:image

ArryArry2016/05/03 08:51Fantomzeit – Dunkelheit oder Leere im frühen Mittllaeter? » Weltrekord für Ulrich Voigt sagte hierzu am 7. August 2009 um 17:48: [...] Ulrich Voigt eingestellt von jb  Diesen Artikel drucken Dr. Ulrich Voigt, dem schon unsere vorige Fundsache ...

JessieJessie2016/05/04 08:59I got swept up in cruise shriaap-ma when we were in Auckland this week and we had a different one docked up outside our hotel room balcony each of the 3 days. I have never been someone who wanted to go on a cruise, but after Jack and I waved goodbye to all the passengers waving back as they left, I have to admit, it’s now on my bucket list to do a cruise! http://zrtxrz.com [url=http://gdnkzxci.com]gdnkzxci[/url] [link=http://yuctuoqiqy.com]yuctuoqiqy[/link]

JaseminJasemin2016/05/08 12:26Wow that was odd. I just wrote an extremely long comment but after I clicked submit my comment di712#8&nd;t show up. Grrrr… well I’m not writing all that over again. Anyways, just wanted to say wonderful blog! http://phitkyrp.com [url=http://fjxvsrqyvzx.com]fjxvsrqyvzx[/url] [link=http://fdzkhhf.com]fdzkhhf[/link]

2014-06-08

"I hate math" とは?

14:25 |  "I hate math" とは? - (iwi) { 反省します を含むブックマーク はてなブックマーク -  "I hate math" とは? - (iwi) { 反省します  "I hate math" とは? - (iwi) { 反省します のブックマークコメント

f:id:iwiwi:20140608132159p:image:w450

↑これの話です.


いい話

時は遥か昔の 2012 年のこと.TopCoder Open という大会がフロリダで開催されていました.

真面目な参加記がここ http://d.hatena.ne.jp/iwiwi/20121009/1349796114 にあります.真面目な参加記によると,当時絶好調だった僕は,アルゴリズム部門のオンライン予選を突破しオンサイトに進出.さらに Semifinal Round でそこそこの順位を獲得し Wildcard Round に進出.そして,0 完続出の悲惨なスコアボードの中,単独で 1000 点問題を正解し 1 位で Final Round へ進出.Final Round での結果は残念ながら芳しくなかったものの,Wildcard Round での活躍が(多分)讃えられ,TopCoder Spirit Award を受賞しました.

……とてもいい話です!実際,この Wildcard Round は僕のプログラミングコンテスト人生において最も印象に残っているラウンドかもしれません.それどころか,結果発表にて僕の 1000 の正解がアナウンスされた瞬間は,僕の今のところの人生全体においても最も興奮した瞬間なのではないかとも思います.


f:id:iwiwi:20121002195412j:image:w450

f:id:iwiwi:20140608133852p:image:w450


オンサイトでのシステムテストの結果は,下の動画のように,ステージ上の画面で発表されます.(※この動画は Semifinal 1 のものです.Wildcard のものは無かった.)順位が下の人から 1 人ずつ発表されていき,通っていれば得点が確定,しかし落ちていれば得点を失い順位が下る.自分の結果が発表されるまでに発表された他の人達の結果は 250・500 共に大部分が fail でした.スコアボードがどんどん悲惨になっていったところで,なんと,1000 に唯一提出されていた自分のコードが pass!! これはたまらない!!! (贅沢を言うならば,このような奇跡が Wildcard Round ではなく Final Round で起こってくれていればもっと良かった……)




Coding Phase における絶望,そして "I hate math"

僕は,オンサイトでは 1000 から開く戦略を比較的よく採用します.この Wildcard Round でも 1000 から開きましたし,1000 を解ききることができたのはその作戦のおかげだと思います.

しかし,Wildcard Round の Coding Phase の後半では,実は以下のように絶望的な気分でした.

  • 1000 が僕には割とすんなり道筋が見えたので,他の人達も(しかも一部の人は僕より早く)解くと思った
  • 250 が数学ゲーで全然わからない
  • 500 は面倒ゲーなので今から手をつけるのはもう多分間に合わない
  • 他の人は 250 を瞬殺で提出している人が多い
  • しかし俺には 250 が分からない!! せっかく 1000 が解けたのに!!! 数学ゲーめ!!!!

というような感じで,「せっかく出だしは良かったのに,もう負けたな」と絶望的な気分になりました.冒頭の写真のようにコードに return "I hate math"; なんていう文を一時期コードに入れていたのは,こういう経緯です.1000 を提出し注目されていたこともあり,その状況は TCO'12 公式ブログの Petr による実況にすら記載されました.


f:id:iwiwi:20140608134238p:image


勿論最終的にはその文を取り除き,若干やけくその嘘解法を送りましたが,案の定落ちました.しかし,蓋を開けてみればそんな絶望の必要はなかったようでした.

  • 1000 は,結局他の人には提出すらされませんでした.難しかったらしいです.
  • 250 は,瞬殺で提出している人たちはほぼ全員間違っていたようです.別に math で特別引けを取っていたわけではないじゃないか……

"I hate math" の本意

というわけで,弁明させて頂くなら,僕は数学自体が嫌いなわけでは勿論ないです.ただ,コンテストをやっている人たちの一部は,僕よりずっと数学ができるという印象があります.数オリのメダリストが珍しくない世界ですし,実際,チーム戦ではおめさん (ICPC) やキタマサ (それ以外でたまに組んでた) が発揮する謎の技術が理解できないことも少なくなかった.なので,コンテストで数学ゲーが出ると相対的な能力の差により不利なので,大事なところでこれは勘弁してくれ~という気持ちだったということです.


その後

TCO'13(ワシントン DC)の Semifinal 1 では,ir5 が "I hate math" をやってました.

f:id:iwiwi:20140608142201p:image:w450



そして昨日の TCO'14 の Online Round 2B でもつぶやかれていました.


やはり数学ゲーは辛い!!!

2013-12-26

"データ構造をマージする一般的なテク" とは?

21:48 |  "データ構造をマージする一般的なテク" とは? - (iwi) { 反省します を含むブックマーク はてなブックマーク -  "データ構造をマージする一般的なテク" とは? - (iwi) { 反省します  "データ構造をマージする一般的なテク" とは? - (iwi) { 反省します のブックマークコメント

"データ構造をマージする一般的なテク" という言葉がじわじわとプログラミングコンテスト界隈に広まっている感じがします.「聞いたことがある表現だなあ」と思っていたらどうやら僕がそう呼んだせいらしい(ソース1, ソース2).

皆 Building 2 なんてマニアック気味な問題の解説をよく読んでいるなあと思います.難しめの問題の細部ということでスライドでは端折り気味になっており申し訳ないなあと思いますので,改めてこっそり解説をしておきます.


Union-Find での例

Union-Find のデータ構造といえば以下をサポートするものです.

  • void init(n) --- 0, 1, ..., n-1 というアイテムがバラバラのグループに入っている状態で初期化
  • void merge(a, b) --- アイテム a と b が入っている 2 つのグループを 1 つのグループにまとめる
  • bool is_same_group(a, b) --- アイテム a と b が同じグループに入っているか否かを答える

親を覚えてツリーを作ってグループを表現する手法をご存知だと思います.(あの計算量にアッカーマン関数の逆関数が出てくるやつです.ご存じなければこのスライドをどうぞ.)

しかし,以下ではそれとは違うアプローチでこれを効率的に実現します.(ちなみにその親を覚える手法は,以下の手法と区別するときは Quick Union などと呼ばれるようです.)


Quick Find アルゴリズム

以下のプログラムは Union-Find のデータ構造を何も知らない人に「これらの機能を実現して」と言った時にそこそこ書かれる可能性のある感じのものじゃないかと思います.

  • 各グループ g に所属するアイテムを vector<vector<int>> で全部普通に持つ(変数 g2i)
  • アイテム i が今どのグループに所属しているかをやはり普通に vector<int> で覚えておく(変数 i2g)
  • merge は普通に片方のグループをもう片方のグループに移動させるだけ
  • is_same_group は配列 i2g を見るだけ
vector<int> i2g;          // i2g[i] := アイテム i の所属するグループの番号
vector<vector<int>> g2i;  // g2i[g] := グループ g に所属するアイテムたち

void init(int n) {
  i2g.resize(n);
  g2i.resize(n);
  for (int i = 0; i < n; ++i) {
    // 最初はアイテム i はグループ i に所属
    i2g[i] = i;
    g2i[i].assign(1, i);
  }
}

// アイテム ia の所属するグループとアイテム ib の所属するグループを 1 つにする
// (ia と ib は違うグループに所属するものとする)
void merge(int ia, int ib) {
  int ga = i2g[ia], gb = i2g[ib];
  // グループ gb に所属する全てのアイテムをグループ ga に移す
  for (int j : g2i[gb]) i2g[j] = ga;
  g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end());
  g2i[gb].clear();
}

// アイテム ia とアイテム ib は同じグループに所属しているか?
bool is_same_group(int ia, int ib) {
  return i2g[ia] == i2g[ib];
}

残念ながら,お気づきの通り,偏って merge されまくると merge に毎回 Θ(n) 時間かかり計算量が全体で Θ(n^2) になってしまいお話にならない感じです.

ちなみに,一応,こいつには Quick Find アルゴリズムという名前がついているっぽいです.まあ確かに関数 is_same_group は O(1) 時間なので Quick という名を冠していることを辛うじて許してやろうか.


Quick Find Weighted アルゴリズム

しかし,なんと実は,上のアプローチは以下のように merge にほんの少し手を加えるだけで一気に優等生になります.

void merge(int ia, int ib) {
  // ia の所属するグループが ib の所属するグループより小さくならないようにする
  if (g2i[i2g[ia]].size() < g2i[i2g[ib]].size()) {
    swap(ia, ib);
  }

  // あとはさっきと同じ
  int ga = i2g[ia], gb = i2g[ib];
  for (int j : g2i[gb]) i2g[j] = ga;
  g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end());
  g2i[gb].clear();
}

merge をする時,グループの大小に気をつけ,大きいグループの方はそのままにして,小さいグループの方のアイテムだけを移動するようにする,それだけです.

一見,比較的自明な感じなので,ふつーの定数倍高速化かな?と思われるかもしれません.でも,実はこれは本質的な変化で,なんと merge の計算量は一気にならし O(log n) 時間になります.

ならし O(log n) 時間になるということは,ある視点に気づけば比較的簡単に理解できます.その視点とは,アイテム 1 つずつに注目して考えるということです.

  • 各アイテム i について,そいつのグループが変更される回数は O(log n) 回.
    • それはなぜかというと,グループが変更されるたびに,自分が所属するグループの大きさが 2 倍になるから.
      • つまり,最初はサイズ 1 のグループに居るけど,最初の移動後は少なくともサイズ 2,その次は少なくともサイズ 4,その次は少なくともサイズ 8……というように,自分の所属するグループは少なくとも 2 の指数で大きくなっていく.
      • なぜなら,自分がグループの移動をする時は,自分より大きいグループへマージされているから.
    • なので,全体で n 個しかアイテムがなければ,log_2 n 回以下しかグループの移動はありえない.
  • よって,n 個のアイテムが関わっている時,全体での計算量は O(n log n) で抑えられる.

というわけで実は,merge がならし O(log n) 時間で is_same_group が O(1) 時間というまともに使い物になる Union-Find のデータ構造が,こうやっても作れるんですね.これは Quick Find Weighted などと呼ばれるそうです.

(ちなみに,Quick Union に比べて is_same_group はこっちのほうが高速なので,こっちのほうが有利なシチュエーションというのもあるはずです.)


データ構造をマージする一般的なテク

この,大きさに気をつけて小さい方を大きい方にくっつけるという考え方を応用することで,色々な普通のデータ構造にマージ機能を追加することができます.

例えば,std::set<int> がいっぱいあって,全体では n 個の int が記憶されてるとして,これらをがんがんマージしていくという処理をしたい気持ちになったとしましょう.std::set には効率的なマージ機能は用意されていませんが,実は以下のように書くだけでマージ部分の全体の計算量は O(n log^2 n) 時間で抑えられます.さっきと同じく,大きい方に小さい方の中身を全部挿入するだけ.

// a, b をマージする.a に全要素が入り,b が空になる.
void merge_set(set<int> *&a, set<int> *&b) {
  // b のほうが a よりサイズが小さいようにして
  if (a->size() < b->size()) swap(a, b);
  // a に b の中身を全部入れるだけ
  a->insert(b->begin(), b->end());
  b->clear();
}

これは,挿入がサポートされているデータ構造なら何でもできます.一般的だ!*1 挿入が O(ほげ) のデータ構造なら,全体の計算量は O(n log n * ほげ) になります.


応用問題

他でも何度か使った気がするけれどすぐに思い出せるのはこれぐらいかなあ.ご存知なのあれば是非教えてください.


いろいろ
  • 順位キューでやりたかったら,併合もサポートする順位キューであるところの Leftist Heap や Skew Heap が普通にあります.普通に併合が(ならし) O(log n) でできます.
  • このスライドで言っている平衡二分探索木の merge とは違うことに気をつけてください.
    • スライドの merge は,主に列を表現するために木を使っていて,木 a と木 b を merge すると表現された列が連結される.
    • 今回の merge は,木なら,順序集合を表現するために使っていて,merge された木はやっぱり順序で並んでいる.
  • 挿入の回数は最悪 O(n log n) 回ですが,merge の操作がランダムと仮定すればなんと平均は O(n) 回であることも知られています.

*1:一般的というのはそういう意味であってこういう意味ではないw

2013-12-18

ICFP-PC の過去の日程

15:45 | ICFP-PC の過去の日程 - (iwi) { 反省します を含むブックマーク はてなブックマーク - ICFP-PC の過去の日程 - (iwi) { 反省します ICFP-PC の過去の日程 - (iwi) { 反省します のブックマークコメント

来年の大きな予定を決めるために,ICFP-PC の日程の傾向を調べることにした.毎年 72 時間なので開始する日だけ書きます.

日付情報ソース
20138/9俺の Google カレンダー
20127/13http://icfpcontest2012.wordpress.com/about/
20116/17俺の Google カレンダー
20106/18http://d.hatena.ne.jp/Irori/20100621/1277142304
20096/27http://d.hatena.ne.jp/Irori/20090630/1246382472
20087/12https://twitter.com/kmizu/statuses/855929456
20077/20http://save-endo.cs.uu.nl/

日付を感想に書いてくれる人ありがたいです.オフィシャルサイト消えすぎ.


追記

オフィシャルサイトは実は普通に結構生き残ってました(すみません).あと,ICFP 学会本体の日付が関連ありそうというアドバイスを頂いたのでそれも並べてみました.

ICFP-PC 初日ICFP 初日
2014???9/1
20138/99/25
20127/139/10
20116/179/19
20106/189/27
20096/278/31
20087/129/20
20077/2010/1

学会の日付は以下より調べました.

kinabakinaba2013/12/19 20:06Conferenceに優勝チームを招待するのが間に合うかの逆算をするので、会議本体の日程が影響するかもです。今年は早め http://icfpconference.org/icfp2014/ なのでコンテストが8月になることは無さそう

sumiisumii2013/12/19 20:55(一部は切れていますが)公式サイトへのリンクは http://en.wikipedia.org/wiki/ICFP_Programming_Contest の下の方にわりと揃っているかと。

iwiwiiwiwi2013/12/19 22:58ウオオ,kinaba先生,sumii先生,ありがとうございます!!
なるほど,8 月の確率が低そうというのが確認できれば結構良いという状況だったので超ありがたい情報です.
公式サイト,2011 っぽい URL にアクセスした時点で 2012 に飛ばされて諦めたのですが,2011 も移転していただけで,かなり残ってましたね.すみません.