Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2014-04-13

『乙』が生まれた日 00:16 『乙』が生まれた日 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 『乙』が生まれた日 - nodchipのTopCoder日記 『乙』が生まれた日 - nodchipのTopCoder日記 のブックマークコメント

2006年ICPC OB/OG会夏合宿、当時自分は新米スタッフとして参加していました。経験が浅く、競技者としての実力も無かったことから、幾何問題(Roads in a City http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2066)の準備が前日の夜までかかってしまっていました。M崎先生をはじめ、他のスタッフに手伝っていただき、申し訳なく思ったことを覚えています。

想定解答は動的分割メッシュで、アルゴリズムの性質上どうしても計算時間がかかってしまいます。また当時ジャッジシステムはPC^2を使用しており、システムの都合上、全テストケースが一つのファイルで提供されていました。そのためテストケースの数が15個までに制限されていました。このため、はじめの数個を手動テストケース、残りを自分の不完全な解答で誤差死誤答となるランダムテストケースとしようと思いました。

テストケースの作成中、ふと半徹のノリから最後のテストケースをビューティフルテストケースにしようと思い立ちました。そして「難問お疲れ様でしたと」いう意味あいを込めて『乙』を入れてみました。これを選んだ理由は、当時2chの影響を受けていたからだったと思います。

本番当日、本問題に本気で挑戦したのは1チームだけで、TLEWAを行ったり来たりしていました。ソースコードを読んだところ固定分割メッシュを実装しており、分割数を手動で二分探索しながらサブミットしているようでした。TLEなら分割数を少なく、WAなら分割数を多くするといった感じです。

ふと誰かにどのテストケースで落ちているのかという質問を投げかけられ、自分が調べてみたところ、一番最後の『乙』だけ誤差死していることが分かりました。この事実を他のスタッフに伝えたところ、どっと笑いが起こったことを覚えています。

結局挑戦したチームは分割数を最後まで探索しきっても解くことができませんでした。

問題解説でvisualizerで描画したテストケースを選手に見せたところ、一瞬の間をおいて大爆笑が起こったことも覚えています。以来、ICPC OB/OG会の幾何問題のテストケースの最後のビューティフルテストケースとして『乙』が使われるようになりました。

記憶を元に書き起こしているため間違いを含む可能性があります。間違った記述を見つけた方はコメントにてご指摘ください。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20140413
 |