Hatena::ブログ(Diary)

yuizumi’s diary

2010-07-13

ICFP 参加記

遅くなってしまったが私の参加記を載せておく.時間軸に沿った説明はほかのメンバーのブログにあるので,ここは史記を見習って各個人の担った役割を記すことにしたい.問題文については大会サイトmr_konnさんの翻訳)を参照されたい.

  • chunjpブログ
    • 一次元総当たり法の実装.手法はシンプルながら初期の自動燃料製造システムにおいて重要な役割を果たした.終盤ではもっと特化した燃料製造系に置き換えられた.
    • 焼きなましソルバーの亜流版の開発.最終的には tanakh 版の性能がよくなったので,そちらに一本化されることになったが,中盤の頃はこちらでないと焼けない問題もかなりあったため,相応に貢献したはずである.
    • 計算資源の提供.解けずに残っていた自動車について 48 並列の計算環境を駆使して燃料を注入していった.地味であるが,結構な数の自動車に燃料を注入できたので効果は大きい.
  • gusmachineブログ
    • 問題文の本質の理解.開始して半日ぐらいはもやっとしか理解できずにいなたが,彼によって問題の数学的な理解が得られた.
    • 自動車の製造,検査,出荷.自動車の製造過程をおおむね一人で確立して,全 72 台の自動車を一人で製造,出荷した.
  • izumi_yusukeブログ
    • 自動車の表現法の解明.自動車の三進列表現の構造を解明した.後に phoenixstarhiro によって解析器が実装され,問題が解ける状態になった.
    • 掃除機の発明.終盤になって,大量の自動車が「記念提出」されるようになってきて,旧来の自動解答系の処理が追い付かなくなってきたので,(解けても解けなくても)一瞬で終わるスクリプトだけを実行するような自動解答系を作成した.後に nya3jp の手によって完全なものになった.
    • 追い込み.最後の 1 時間ぐらいの間,先述の掃除機では対応できない問題を目で見繕って,ひたすら手でスクリプトを実行するという実に泥臭いことをしていた.「あと 40 分もあるの?」とか暴言をはくほど重労働だったらしい.
  • nya3jpブログ
    • インフラの整備.ほかのメンバーの成果物を順次取り込みながら,全体としてひとつの強力なシステムにまとめあげた.彼は燃料製造にも自動車製造にも直接的にはほとんど関わっていないが,最初期(まだ三進列の解析も終わっていない頃)から最終盤まで彼のシステムがずっと大活躍しており,これなしには我々のチームがこれだけの成績をあげることはなかったと確信する.
  • phoenixstarhiroブログ
    • 回路(ゲート)の理解.いち早く「人間離れ」を起こして,最初の大難関であるゲートの中身の解明に成功した.
    • 回路構築法の開発.ゲートの解明からの流れで,任意の三進列を出力できるような回路構築法を設計した.
    • 符号系の解明.謎の表現として立ちはだかった三進列の仕組みは彼によってその解明の端緒が開かれた。後に izumi_yusuke と二人で長さと値は異なる符号体系を持っていることを突き止め,燃料と自動車の表現法の解明に繋げた.また,一般的規則(再帰的構造)を見いだしたのも彼である.
    • 燃料の表現法の解明.燃料の三進列表現の構造を解明した.もっとも,符号が理解できればほとんど自明であったし,そもそも符号系の解析と同時進行であった.
    • 特化型のソルバーの開発.特定の形をした自動車(だけ)に対して燃料を出力するプログラムを多数開発した.これらは先述の掃除機に取り込まれ,次々と自動車を処理していった.
  • tanakhブログ
    • 回路処理系の実装.上の phoenixstarhiro の成果をもとに回路のシミュレーター,生成系を順次実装した.土曜日の朝にほかのメンバーが起きたときには,すでに任意の ternary stream が提出できるようになっていて,みんなが驚くことに.
    • 焼きなましソルバーの開発.焼きなましによるソルバーを自動車の構造が判明してから数時間のうちに作り上げ,「無理ゲー運ゲーに変えた」.プログラムは終盤にわたるまで絶えず改良され続けて,まさにチームの収入の柱として働き続けた.

正式にチームに参加表明したのがほとんど開始直前で,しかも 5 位以内確定という実にいい思いをしてしまったので少々恐縮している.問題自体はとてもおもしろかったけれど,ちょっと謎解き(というかリバースエンジニアリング)の部分が多すぎたかなあ,とほかの人とそれほど変わらない印象を持っている.サーバーは概してよく動いており,運営の方々は相当頑張っていたのではないかと思われるが,そもそも最初から DoS が起こらないように問題を設計しろよ,という意見も一理ある.