Hatena::Grouptopcoder

(iwi) { 反省します

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

 | 

2011-05-15

UTPC\(^o^)/オワタ

23:54 | UTPC\(^o^)/オワタ - (iwi) { 反省します を含むブックマーク はてなブックマーク - UTPC\(^o^)/オワタ - (iwi) { 反省します UTPC\(^o^)/オワタ - (iwi) { 反省します のブックマークコメント

無事に UTPC 2011 が終わりました.準備たいへんで面倒だったけど,当日めっちゃ楽しくて,救われました.ミスジャッジ等も起こらず良かった.

解説は近いうちにうpります.

以下,思ったこと整理せず殴り書く.備忘録も兼ねて,というより完全に備忘録として,とにかく書く!!


準備はじめ

今年もコンテスタントがやりたかったですが,岩田にスタッフになれと強く言われました.

僕には,個人コンテストがやりたくて,長いこと温めてきていた問題セット案がありました.ソレを崩して問題を出すのはイヤだし,逆に準備も楽になるだだろうし,他の人たちがよければ,そのセットをベースとしたもので UTPC をしてはどうかという事を提案し,受け入れてもらったため,今年度の UTPC は僕のやりたい放題となりました.

問題

やりたい放題できる自分のコンテストをひらいてみたいとは長らく思っていて,少しずつ問題を貯めていました.

選別したいわけでも,トレーニングしたいわけでもなく,とにかく楽しめると良いと思っていたため,典型的な問題はなるべくやめたいと思っていました.

一方,データ構造とかツリーとか好き (ヘタの横好きですが) なので,そういう趣味っぽい問題を後ろの JKL に自重せずに入れた.

結果,自分的にはかなり満足できるセットになりました.

D (defunge)
  • 我々のコンピュータとか有限なメモリしか持ってないから,その上のプログラムの停止性とか余裕で判定可能なんでは.
  • というメッセージ (嘘)
E (First AC)
  • 最初のほうのための全探索する問題の候補としてやっつけでつくってみたけど,意外と興味深い感じになった.
  • 自分はさくっと O(n^2) の DPを思いついて満足していた
  • 岩田が,瞬殺はしてこなくて,?って思ったらいきなり O(n log n) で解いてきて吹いた
  • 貪欲,入れていく感じの貪欲じゃなく,入れつつ出してゆく感じの,斬新な貪欲だったので,結構アツいなと思っていた.
  • なので,貪欲で出したい気持ちはかなりあったが,難易度はすでに十分だったので, O(n^2) で出しておいた.
F (全域木)
  • 一番古いのはこれかもしれない,2年かぐらい前に作ったかも.
  • 元々は,与えられたグラフの上で独立な全域木を 2 つ作る問題が出したかったけど,自力ではとけなかった (マトロイドで解けます...)
  • じゃあグラフを特別なものに限定したらどうだ?って思った.
  • 「ロシアゲー」と呼ばれる種の問題.日本のコンテスト的には斬新かな.
G (三角形)
  • はじめ,連続6個で入り組むケースに気づかず, k 個でもいけそうだなとか甘いこと考えていてワロスだった
  • でかい配列をリニアーにスキャンしつつ各場所で局所的に全探索,っていうの,あまり見かけない手法な気がして楽しかった.
  • 変な探索っぽい解答の改善とデータの強化のいたちごっこを頑張った
H (キャッシュ)
  • 元々は,重み無しで考えてみて,あー貪欲とけるなーとおもってたら,アルゴリズムデザインにもろに解説されててなえた
  • おもみつけてみた.
  • 重み無しのとき証明を考えるとき,区間っぽい感じで考えていたので,自分的には最小費用流が一瞬でみえて瞬殺だった.
  • なので,慣れてる人は瞬殺だと思ったけど意外と 1 人にしか解かれなかった.
  • 部分点を,「重み全て 1」にしてたら,もっと解かれたかも?
  • F 以降の中だと圧倒的に典型度が高いと思っていて,そういう意味ではセットの趣旨的に残念…かと思ったけどむずかったらしく良かった.
I (ビット)
  • はじめは YES/NO問題だった(つくれるか?)
  • まぁそれほど大変じゃないしYESの時プログラムだしたら,プログラムを出力する斬新な感じの問題になって良いと思った
  • NO 消したほうが考えにくいことに気付いてNOやめた
  • まあつまり,可能である必要十分条件を考えようとすると,構成的な証明になって解ける.
  • 部分点はかなりヒントになってるとおもう.証明の方法がまるで同じ.
J (Treap)
  • 適当に考えてみたらとりあえずDPできて,簡単な DP 問題ないし,なんか DP 問題になるかな,とおもった.
  • そしたら意外と計算量が落ちて,さらに落ちて,アツい問題と化した.
  • FFT,かっこ良くて好きなので,FFT になってくれて嬉しかった.
  • Treap の説明をいっぱい書いて,ヤバそう臭を漂わせておいたけれど,「面白そう」と言ってこれに飛びついた人 (しかも意外な人) が複数居て吹いた.
  • 何ステップも考察をしなければいけないが,一方で,割と進めやすいステップを何段もという感じかもしれないとは思う.
    • でもまあ,「精度超えたらもう投げやりな出力をする」とか,ちょっと斬新で面白いと思った
  • 解いてもらえてめっちゃ嬉しい!
K (TSP)
  • 研究で到達可能性クエリ系のアルゴリズムのサーベイしてる際に考えました.
  • GRIPP index とかあのへん. でも今回はソレより遥かに単純に解けるようにした.
  • それでも,そこそこ大変なのではないかと思った.
  • でも,うまい実装を思いつくと,結構簡略化できるみたいで,思ったよりサクっと通せるらしい.
  • 座標はよく縮約するけれど,グラフを縮約する感じの問題は斬新なのではないかなあ
L (L-th)
  • 現在のプログラミングコンテストでのデータ構造系の難しい問題というと,セグメント木が多い.
    • DP + セグメント木,とか,僕は相変わらず好きです
    • しかし,今やありがちすぎるので,今 1 問またここで増やしても,誰の印象にも残らないかなあと思った.
  • あとデータ構造の難しい問題というと,平衡二分探索木を持ってこないと解けない問題というのも一応過去数問あるけど…
    • そういうので,持ってくるだけでなく,ちゃんと考える感じになってると,僕はかなり好き (印象に残ってる問題多い)
    • けどまあ,そういうのは,組んだこと無い人にハードルが高すぎて,よくないかなあと思った.
  • 新しい方向性として,永続データ構造を出してみたいと,ずっと思っていた.
    • 永続データ構造は,関数型言語を使って知った
    • これがアルゴリズムのパーツとして本質的に計算量を落とすことがあると昔気付いて,思い入れがある.
      • 例えば,3D の range tree で,直方体領域に含まれる点の数を答えるクエリを処理することを考える.
      • ナイーブにやるとクエリ O(log^3 n) で,FC すると O(log^2 n)
      • ここで,もし情報の更新がなければ,永続データ構造にしてやると O(log n) にできる
    • 別にそれ系の発想はよく知られたものだったので,新しいアイディアでもなかったのだけれど,とはいえ少しマイナーなアイディア.
    • 何より,実装も楽 (普通の木かくのと変わらん) だし,自分で思いつくことも十分可能
    • なので,プグラミングコンテストの世界で出てもおかしくないと思っていた.
  • なので,永続データ構造が効く問題を作りたいと思って色々考えていた.
  • それでこれができた.
  • そうしたら何気に,特別な場合として含んでいる K-th number が O((n + q) log n) で解けていてちょっと吹いた.
  • しかし,K-th number を同じく O((n + q) log n) で解ける Wavelet Tree も,がんばるとこの問題を解くのに使えてしまった.
    • Wavelet Tree は 2003 年とかだった気がして,本や基礎的な勉強だけじゃ知らない.
    • 先端のソレ系の業界だと,流行りに流行っていて,まあ知らない人は居ない.
    • そういう,現代の話とか知ってる,みたいな種の人が特をする問題というのもまぁ面白いかなということで良いことにした.
    • Euler-tour technique で木を列にしなきゃいけないし,普通のWaveletTreeを拡張しなければいけないし,普通に大変だし.

ところで,どうでも良いけど,自分が作る問題は,入力または出力が巨大な問題が多いなあとちょっと思った.そういうのが確かに好きな気がする.

そういえば,部分点の話

ある時まで,E までが簡単で,F 以降がこれでした.上位の人にはこれでも面白いかなと思ってはいたのですが,中位ぐらいの競技者が,E までを瞬殺し,それ以降なにもできないという,絶望のコンテストになってしまうのではと,突然気づき,焦りました.

で,まあ,フツーに最近アル感じの,部分点を付ければ良いかなと俺は安直に思ったんですが,部分点システムに潜む問題点なんかを指摘するスタッフもいて,かなり議論になった.部分点を設ける問題点は:

  • 細かい部分点で勝者が決まると思うと,部分点を取らなければいけない.
  • 部分点をとにかくガンガン早どきするコンテストになってしまいかねない.
  • また,部分点がありすぎると,部分点取りにキリがなく,それだけで時間がなくなる.
  • つまらない部分点を解いているか解いていないかのチマチマとした戦いになり,面白くなくなるかもしれない.

などなど.言われてみれば,たしかにと思う. そういうわけで,部分点のシステムは,かなりシンプルにすることにした.ご存知のとおり,

  • 点数を 20 点に固定し,1 問 1 枠 (差がチマっとしない)
  • 部分点は E から I までの 5 問のみ (多くしすぎない)

結果を見ると,そこそこうまく行ったと思う.これも,1 人じゃなく他の 3 人とやっていたおかげでかなり良い結論が出せて良かったと,他スタッフに感謝している.

特に,このシステムの良かった点として,

  • JKL の問題を解いた人が有利になる

というのがあった.例えば, J で 100 を取るのと,I で 100 を取るのは,一見同じようで,実は J の方が有利になる場合がある.それは I の 20 で楽に他の人に差をつけることができるかもしれないから. JKL は難しいつもりだったので,これは良かった.


ストーリー

ウチの大学のICPC系のOBがみんなG○○gleに入っていくという現象に対するアンチテーゼ…というわけではないです.

こんなストーリーを書いたせいで就職できなくなったり訴えられたりしたらやばいですね. チキる心もあったけど忙しくて悩む暇がなくてそのままになってしまった.

僕はこういう SF っぽくてディストピア感のある中二病なストーリーが好きなので,思わず,書いてしまいました.バルなんとかかんとか,とか,シュタなんとかとか,去年やっていて,それに大きく影響を受けた.

こんなストーリーを問題全体に適用しようと思ったきっかけは何だったかなあ. ちゃんと思い出せない….

ただ,自分の持っていた疑問は,プログラミングコンテストの問題にストーリーは要るのかということだった. しばしば,グラフとかの言葉で説明するよりも,何がしたいというシチュエーションを説明されたほうが分かりやすいということはあって,そういうストーリーは有意義だと思っていた. 一方で,適当に変な人が出てきて,変なことがおきて,じゃあ次のような問題をやります,みたいな唐突系ストーリーは,問題文長くなるだけなこともあり,楽しいと感じる時もあれば,嬉しくないと感じるときもあった.

なので,ストーリーと問題は別とし,「問題」セクションを問題文に作り,ストーリーを読みたくない人はストーリーを読み飛ばせるようにした.

まあ,より一層,参加者の皆に楽しんでもらい,印象に残してもらうという目的としては,かなり上手く行ったようで何より.

あと,ストーリーの続きが気になれば,後ろの方の問題文もみんな読んでくれる,みたいな作用があったかもしれない.

ところで,気になる: http://twitter.com/#!/highjellies/status/69322382870970368

準備:ソフト・ライブラリ

リポジトリは mercurial にした.自鯖使うならなんでもよかったけど,安定性を考えて借りてる coreserver の上に置きたくて,WebDAVが使えないので,hgweb.cgi が動けば使える mercurial が消去法的に選ばれた.

Wiki は普通に PukiWiki. メモを殴りガク感じ. 問題案を投稿したりというフェーズが今回なかったので,そこまで重要にはなってこなかった.

解答・IO・チェッカーの管理は,にゃあさまの rime を使った. これは神システムなので,こういう系のコンテストやるなら,使わないと確実に損.マジCOOL.自動でコンパイル・テストをやってくれて,見やすく出力される.結果を Wiki にまとめる機能もあり,いい感じ.わくわくする.

あ,でも Cygwin 上だと凄い遅くなって,シンドイらしいです. 知るかって感じだけど.

入力バリデータ・出力判定器は testlib を使った.例えば,スペースや改行の個数まで厳しく管理したり,余計な出力がくっついてると勝手に怒ってくれたり,何かとよく出来ているので,自分でやるよりは確実に楽.

ただ,rime の仕様と食い違っていて,ちょっと大変だった. どうにかしてほしい. 世界的 (少なくともロシア的)には testlib はかなりメジャーっぽい気がして,多分多くのジャッジシステムが testlib 系の仕様にあわせてつくってありそう. rime の仕様は何にあわせてあるんだ…?

あと,各プログラムが全てのケースに関して落ちるのか通るのかが rime で分からないので,結局 ruby で書いた自作スクリプトでまとめていた問題もあった.ただ,そいつはジャッジプログラムとかに対応させてない.できれば rime にソレを出す機能を付けてほしい.

問題文は,reStructuredText で書いて,基本的には rst2html をかけていた.数式が書きたかったので,TeX 記法で $a_i$ とか書いたやつをいい感じの HTML にするプログラムは自分で書いて適当に適用するようにしていた.

図は全て graphviz

PDF(印刷用)はwkhtmltopdfでHTMLから作った.本当は,せっかく問題文ソースを rst で書いてあるので,rst2tex をかけて,TeXからPDFにしようとはじめは考えていて,例えば図は全部 png だけでなく eps も用意してあったり,した. でも,出力されたTeXそのままでは当然ださいので,それに手を加えていい感じに変換するスクリプトを,書こう書こうと思いつつ書く時間がなくて,印刷は現地だけだし,HTMLからなら楽なので,結局HTMLからにしてしまった.

そうそう,あと,rime には,出力判定器をテストする機能があるといいなあ. 今回,出力判定器が必要となる問題が多かったけど,その出力判定器自体が正しく色々なものを判別しているのか,チェックするのが大変.

そういえば,入力ファイル名

今回,入力のファイル名に,入力の性質を入れる,みたいなのを試してみた.

例えば,F みたいな入力が 2 つしか数字なければ, 05_00100_020.in みたいな感じで,完全に情報が入る. (05 は採点される順番)

もう少し普通の問題だと,大きさと,入力の作り方,みたいなのをいれていた.

これは結構わかりやすくて便利なので,オススメである.もうやってる人も多いのかな?

例えば rime で落ちたときに,ホウ,こういうので落ちるのか,みたいになる.

さらに,今回はイモ先生にお願いして,ジャッジシステムで,審判側には元のファイル名が表示されるようにしてもらった.

これは,かなり快適で,ホウ,これで落ちるから,アレ系のミスだな,みたいなのがすぐ分かって良かった.


準備:分担とか

12 問全て,僕が問題文・IO を用意した. ぱなかった. しかし,共に一週間前に大体仕上げた. 結構な頑張りだと思うけど,愛する問題たちの準備だし,OK.

一方,改善の余地が大きいと思ったのは,マネージメント能力. 今回,僕がスタッフのリーダーとなったが,ただでも多くの仕事を受け持っているなか,雑務もめっちゃ多いし,当然だが他の人の動きは思い通りにはならないので,まあ,大変だった.

特に印象深いのは,プラクティスの準備. 僕が本編は頑張るから,残り 3 人でプラクティスはやっておいてと,かなり前から何度か言っていたが,ずっと放置されていた. なので,近くなってきてから,ジャンケンをさせてプラクティス準備のリーダーを決めた. ジャンケンさせないといけないとか,小学校かよと,ちょっと思ってしまったけど,重要だったかもしれないし,よくわからない. (結局プラクティスちゃんとできたので岩田とキタマサはありがとうございました.)

あと,この界隈には,デスマーチが好きな人が多い. 前日にやればいいよ〜と言う人が,困るのは,そういう人たちが大抵「ここどうすればいいの」みたいなことを作業を始めてから聞いてくることである.結果として,他の人もデスマに付き合わなければいけなくなったりする.あるいは,チェックの仕事を後回しにされているときに,ギリギリでチェックされて「ここだめだったよ」と言われると,そうそうに作業を終えていたはずの人がデスマになる.

愚痴っぽいけど,一般論として書いているつもりで,他スタッフを責めたいという気持ちは…まあ少しは無くはないけど,とにかく,どうにかする方法を見つけたいというのがとにかくのところ.

他スタッフには,基本的に本当に感謝していて,岩田にも,キタマサにも,eomole にも,ちゃんと重要な指摘をしてもらっていて,今回のコンテストが問題なく終えたのは本当に彼らのおかげですので.

会社と違って,給料や契約で縛っているわけでもなく,例えば罰を与えることができないので,マネージメントが難しいのかなとちょっと思った.けど,オープンソースのとかで上手くやっているところっていうのが世の中に多くあるので,頑張ると,上手くいくのかもなあ.

まああと,やはり取りまとめはなんやかんや多くの雑務をこなすことになって仕事多いということを,ちゃんと他のスタッフが理解してると良いと思う. 例えば自分は高校時代にホゲとかやってたし,大学のサークルでもピヨとかやってたので,ソレはよくわかっているのだけれど. やったこと無い人も多いよね.どうすると理解してもらえるんだろう?

会議

そういえば,今回,顔を合わせた会議を1度も行わずに準備を慣行した. これは僕の提案. JAG が凄い頻度で顔を合わせてることに疑問だったので.

その代わり,会議はメール+Skype という感じだった. 基本,なんかあったらメールを流し,決めなければいけなそうな時期になったら Skype 会議をやって決めてゆく.

ただ,Skype 会議は,人数が増えると,反応しない人,みたいなのが少しずつ出てきそうな気がする. アニメ見ながら聞くとかね.

今回は 4 人だったから上手くいったのかもしれない.テキパキやるのもコツかも.普通の会議でもそうだけど,議長は,議題と選択肢を予めある程度用意しておこう.

当日・開始前

まず,着てもやることないだろうから,集合を 10:30 に設定してるのは早すぎ?と思っていたのは甘かった.10:30 にしてよかった.想定しないトラブルはつきもの.

今回おこったのは,システムにログインできないという問題.意味不明なことに,あるルータを通して接続するとログインできず,別のルータを先生に持ってきてもらったらログインできた.あとでそのルータをジャッジ部屋でつなげたら,やはりまたログインできなかった.ぱない.

当日・Ustream垂れ流し

あと,今回は,解説だけじゃなく,コンテスト中もなんとなくコンテスト部屋の Ustream を垂れ流してみた. オンラインコンテストというのはなんやかんや世に溢れているので,オンサイト感をプッシュして,差別化したかったという気持ちがちょっとあったのかもしれない. とはいえ風景は別にそこまで面白くもないので,意味あるのかよくわからなかったけれど,コンスタントに 20 人以上が接続していた. まぁ開いているだけで観ていない人が多いとおもうけれど.

コンテスト中垂れ流すためには,垂れ流し用PCを1台用意するのが安定だなあと思って,僕はPCを2台持って行っていた.で,ThinkPadが壊れた(後述)時には,それを代わりに使っていたので,配信が止まった.すみませんでした.

Ustream Producer を使って,RIP で左下にデッドラインタイマーを出してた.アレは良かったと思う.


当日・コンテスト中

すっごい楽しい.でも,ミスジャッジを常に恐れなければならない. 興奮・緊張・恐怖・安堵の間をいったりきたりする.

  • 興奮:「うおー,ついにファーストアクセプタンスきたー!!」
  • 恐怖:「ゲッ,パッと見だいじょぶそうなのに WA だと…」

みたいな感じ.

結局,俺みたいな小心者は,検証に時間が追われる.まぁ分かっていたことなのですが,残念ながら時間がたりず,解説の準備も当日にするスケジュールにしてしまったので,解説のスライドはしょぼくなってしまった.ごめんなさい.うpするやつはマトモにします.

ミスジャッジはなかった (素晴らしい!) が,トラブルは多かった.

  • なぜか提出ソースが見れない人がいた
  • 「NG (実行失敗)」が何故かでた人がいた
  • 「自分のプログラムが正しければ,データにミスが含まれています」 という clar が来た (ぱない...)
  • Amazon EC2 使ってるせいで,たまに実行時間が安定しない (今後の課題)
    • 特に JKL の CPU 時間を多く食うものがやばくて,りんごさんの J が大変になってた.通って良かった.
  • ThinkPad が壊れる (コンテスト関係ない...)
    • c を押すと ce と入り . を押すと .o と入り,エンターを押すと 改行+\ が入る,みたいなぶっ壊れ方をした
    • linux からリブートして windows いっても同じ症状…
    • 放置してたら治った

ジャッジシステム

  • いも先生に,UTPC があるとしたらいもさんのジャッジ使わせてほしいとは,かなり前から言っていた.
    • いも先生ぺろぺろ
    • 過去使ってきた M-Judge はセットアップしにくいらしい.あと,ジャッジマシンが遅い.いつもUTPC序盤はキューがヤバイ.
    • 部分点システムがあるシステムがそもそも他にない
  • AtCoder というものを作るという噂もかなり前から聞いていた.
  • 結構開発はかなりギリギリになって,直前数日間でガーっと完成に持って行ってもらった.

AtCoderはゆっちーといもぺろさんの2人によって作られているのだけれど,彼らは相当にぱないチームであると感じた.ゆっちーは,何でも要望一瞬で聞いてくれるし,ぱなかった.

ちゃんと制作を間に合わせてくれて,とにかく感謝である.様々なUTPCに合わせた要望も聞いてもらったし.上手く行って,本当に良かった.感謝である.

一方で,僕はとにかくコンテストの成功を祈って,直前数日間は,様々な場所をクリックし URL 欄に色々入れ,数々の問題の報告した. それによってシステムは改善したわけだし,UTPC を上手く実施できたという実績も得られたので,向こうにとっても良かったのではないかな.

ちなみに,Amazon EC2 を使ってやっていて,最初は 5 台,中盤は 3 台,終盤は 8 台体制でジャッジしていました.簡単にスケールしてメッチャ助かる.

一方で,インスタンスを増やすのは一瞬ではないので,キューがすごいたまってからウオーってなるとちょっと大変だった.終盤は,おそらく部分点狙いの提出が増え,TLE が多発し,採点が遅くなり,キューがかなり詰まった.あと1時間だし,金とか安いもんだからぶちこみまくれーってことで8台になった.

あと,上にも書いたけど,実行時間がたまにやばくなるみたいで,どうにかしないと.

そういえば,問題やデータセットをセットアップしてもらって,実際に試してみるというのは,木曜昼からやった. 多くの問題点が出てきたので,早めにやってよかった.前日までデータ作ってる,みたいなスケジュールだったら,確実に徹夜になったり開始が遅れたりしてたと思う.

当日・解説

Ustream は最高で 100 人弱ぐらい行っていた気がする. スゲー!

そんだけ聞いてくれるわけだし,もっと気合入れられたら良かったなあ.悔しい.

本当なら,解説のスライドを何処かへアップロードした上で話をしたほうが良いよなあ.しかし,余裕なくて,考えなかった.

視覚的にインパクトのある全域木のキタマサ解法とか, FFT とか purely functional data structure とかの単語で盛り上がってもらえて良かった.

懇親会

話の種にと,順位表の印刷を先生にお願いしたけど,あれは役に立ったのかな?結構盛り上がってる部分が多くて良かったけど,盛り上がってない部分というのもあった,どうすれば良いんだろうなあ.

自分は幹事経験ほぼなく幹事力低いので,幹事やりにきてくれたあげさんには本当に感謝している.

二次会はカラオケに行った.にゃあさま・nodchipさんあたりがカラオケ結構好きなの知ってて,興味あったので,いけてよかった,楽しかった.

歴史と展望

2008 年に始まったUTPCも今年は4年目.元は,ymatsuさんを中心とするあのへんの世代の人たちが始めてくれた.ymatsuさんは最初のTopCoderの日本人ライターでもある.カリスマを感じる.ウチの研究室のOBで,研究室のボスもしばしば褒めてる.

2008年度のセットは,当時の自分が持ってなかったような新しい発想が要求される問題ばかりが並んでいて,とても勉強になり,感動した.今となっては,常識だから瞬殺,みたいな問題も多いけど,それが常識と化したのは,彼らのおかげである部分もあると思う.

2009年度のセットは,王道系ながら難しい問題というのが多く並んでいて,やはり感動した.幅広い王道ジャンルをカバーし,高度な知識などは要求しないが,それでいて各問題が難しくて,にゃあさまを中心としたプロブレムセッター達の高い実力を感じた.あと,問題設定がねこに統一されてるのも斬新で面白かった.

個人的に2010の問題セットはあまり好きではない.実装偏重.問題設定も消えた.印象に残ってる問題もキタマサの多項式の問題ぐらいかなあ,アレは凄い.でもまあ,実装偏重だと,暇な人はでず,皆手を動かしてられるので,そういう意味では,幅広い層に楽しんでもらうという趣旨に対する一つのアプローチなのかなあ.

それで,今年. 今年は 160 人ぐらいの人が参加してくれて,過去最高となった. これも,先輩たちがこのようなイベントを開始し,また質の高いコンテストとして実施してきてくれたおかげである. ありがたい.

このまま運営してても普通に良イベントだとは思うけど,もっと進化できるともっとよくなるかもしれない.

自分の妄想としては,適当にスポンサーが着いてくれると,賞品とかが設定できて,もっと盛り上がるかもしれないなと思う.例えば,ウォータールー大学のサークルがやってるコンテストにはGoogleがスポンサーについてるし,昨日のUVaのFudan大学のコンテストにもGoogleがスポンサーについてた.例えば,上位 10 人に入れたら T シャツ貰えたら,結構うれしい.あくまで妄想.どっか羽振りの良い企業がサクっとTシャツ10枚ぐらいくれてもいいんでは.

スポンサーが着くと,それだけ何らかの責任みたいなのも負うようになるので,もちろん慎重にならなければならないと思う.大人の事情みたいなのよくわかってなくてこわい.

あと,別の妄想としては,他の大学の大学有志プログラミングコンテストと連携できたらもっと盛り上がったりするかもしれないなと思っている.京大の人たちも有志のコンテストを企画しているという噂を聞いていている.あと,会津の人たちはすでにたまにやってる.例えば,総合優勝を作るとか,どうかなあ.年間チャンピオン,みたいな感じになって,結構アツい気もする.ただまあ,調整とか,大変かもね.

まああくまで妄想である.そもそも来年はまた選手に戻るかもしれない.


なんか

眠いけど寝られないからなんか書くかと思って,気づいたらノリノリでいっぱい書いてた.

でもまあとにかく,なかなか貴重な経験をしたと思うし,色々書いておいて忘れないようにするのは良さそう.

楽しかったー.

shindanninshindannin2011/05/16 10:27iwiさん・開催者のみなさん、お疲れ様でした。自分は急な仕事が入り参加できなかったのですが、皆さん大満足だったのではないでしょうか?あれだけの問題・ストーリーはすごかったですね。個人的にはストーリーはなくてもいい派なのですが、それでも楽しめましたよ。
UStream放送のほうはあとで録画をみようかなと思ったのですが、みれませんでした(確か放送中に放送する側が録画ボタンを押してないとだめだったはず)ぜひ来年は録画もお願いします!

iwiwiiwiwi2011/05/16 12:51ありがとうございます.おかげさまで,楽しかったと言ってくれる人が多く,良かったです.
Ustreamの録画ボタンは,存在を知りつつ,忘れてました.ごめんなさい.(あるいはグダグダな解説を録画したくないという気持ちもあったかもしれません…)
あと,システムに関するご指摘も,ありがとうございました.

jelliesjellies2011/05/16 17:41・この記事について。準備はじめ、問題、ストーリーのところはよく理解できた。準備以降は同じ日本語だとは思えなかった。自分にはスタッフは無理なようです。
・ATCODERの仕様について。「コンテストトップ、質問する、自分の解答一覧、順位表」のリンクが、各問題の問題文が表示されている画面にもあると便利だと思いました。
・ストーリーと問題文を分離するのはよいアイデアだと思いました。機会があれば今度やってみよう。
・1人で10問作ると、いろんな意味でセット全体に特徴が生まれていい感じでした。(※これはICPC合宿の作問を全部自分に投げていいよという意味ではありません)
・今年の4月あたりに、例の本がまた発売されました。http://amzn.to/jV0vAu
・デスマと言えばデススマイルズの略で通る幸せな世界で生きていきたいです。
・ちょうたのしかった。
・ぱない。

nyaasannyaasan2011/05/16 21:54コンテストの準備運営おつかれさまでした!自分はうっかり寝落ちしてしまったのが残念でしたが、問題は面白くて楽しませて頂きました。あと、二次会で噂に聞いていたきうぃさんのイケメンボイスを聞けてよかったです :)
そして rime へのフィードバックありがとうございます。普段はOB/OG会のコンテストでしか使っていないので他の環境で使ってみた話を聞けるのはとてもありがたいです。
バリデータの仕様はご想像の通り適当です。testlib を使ったことがないので、そちらの流儀も全然知りませんでした。逆に言うとこだわりは特にないので、testlib に合わせるなり、カスタマイズルールをちゃんと書けるようにしたいですね。他の点に関してもゆくゆく改善していきたいと思います。他にも気になる点があったら教えてください! (もしくはパッチを送ってください :) )

nodchipnodchip2011/05/16 22:53運営お疲れさまでした。ストーリー、問題内容のいずれも楽しませていただきました。
・「rime の仕様は何にあわせてあるんだ…?」・・・OB/OG会ではにゃあさん謹製のvalidator.hhという補助ライブラリを使ってします。validator.hhに含まれる入力関数を用いて入力パーサーを書くと、入力検証ができるというものです。testlibの方は触ったことがないのでわからないのですが、きっと似たような目的のライブラリだと思います。
・「各プログラムが全てのケースに関して落ちるのか通るのかが rime で分からないので」・・・設定ファイルで模範誤回答(?)を指定することができ、この解答はこのテストケースで落ちる、というのを確認できるようになっています。これでは不十分でしょうか?

iwiwiiwiwi2011/05/16 23:23>ざと
・前のICPC合宿向けのセットを作った時はざとが中心となって上手く行っていたし,大丈夫では
・AtCoderの要望は,伝えた瞬間に反映されました.(ぱない)
・1 人で全部までは行かなくても,中心となる人が明確に決まってたほうが雰囲気が出て面白いのかもなあ.
・例の本って言われても初めて見ますが吹いたw
・こっちも楽しかったです,参加してくれてありがとう

iwiwiiwiwi2011/05/16 23:35>にゃあさん
ありがとうございます.こちらも,皆様の美声が聞けて幸せでした :)

rime は本当に便利で,とても快適でした.

出力検証機は,rime の中だけでなくジャッジシステムでそのまま使えないといけませんので,その辺の仕様は広く使われているものと一致してると便利なのではないかなと思います.あまり多くのジャッジシステムの仕様を知っているわけではないですが,あの辺がデファクトスタンダードになっていそうな気がします.(もしかしたら妄想かもしれませんが…)

iwiwiiwiwi2011/05/16 23:46>nodchipさん
参加してくださいありがとうございました.楽しんでもらえたようで,何よりです.

入力検証機より,出力検証機の話のつもりでした. 入力検証機は eomole さんが validator.h を使って書いてくれて,上手くいっていました.

自分の入力管理の仕方だと,入力のファイル名は安定しなかったので,その機能は使いませんでした.例えば,「あ,序盤にこのケースも入れよう」とかやると通し番号が 1 ズレる,みたいなことが平気で起こったり,あるいはファイル名に入力の性質を入れてると,乱数のために毎回ファイル名が変わったりします.また,ランダムに生成するようにしている入力ファイルとかだと,ある程度の確率で嘘解法が通ったりするので,確実に落ちるとして指定するのは微妙かなあと思いました.

自分が知りたいと思ったのは,「このケースでは落ちる?」ではなく,「どのぐらいのケースで落ちる?」でした.例えば,適当にいろんなバリエーションの入力つくって,無事に嘘解法が落ちたと思って安心したら,実は 1 ケースでしか落ちていない,みたいなことはちょっと. どのバリエーションのテストケースが強いかな,とかも知りたい.

leflef2011/05/17 23:56すでにそこらじゅうからオファーが来てそうですが、Tシャツぐらいならスポンサー出来るかと思います。

iwiwiiwiwi2011/05/18 02:46おお,また来年なのでしばらくどうなるかわかりませんが,ありがたいです!

 |