KUPC 2011

KUPC Online Judge

KUPCのジャッジをやっていました。主に問題の作成とテストをしてました。てきとうに感想などを書きます。
大規模なコンテストの主催者側に回るのは初めてなので割と楽しめました。特に本番中は他の人の解答を見て遊んでた気がします。
コンテストの問題に無理ゲーは無いと思いますが、全問題を一人で解くのはかなりの実力がないと厳しいと思われます。各問題の感想(？)は以下のとおり。

A,B問題
  • Testerなのにショートコードして遊んでた。
C問題
  • プラクティス用のリアクティブ問題でてきとうに面白いのがないかという話になって、しりとりはどうかと挙げたら採用されてた。
  • しかも、いつの間にか本番用になってた。
  • 本番では予想以上にWAが多かった。というかC以降の問題が血みどろになってた。
D問題
  • 言われて見ると乱択が今まで出てきてないのはおかしい様な気分に。
  • 確率1で答えを返すんだったらいいじゃん。
E問題
  • 20分くらい掛けて区間篩を使えばいいだけということに気づく。
F問題
  • てきとうにメモ化再起すればO(NK)で解けるだろうと思ってやったらO(N^2K)になって困った。
  • 微修正してO(NK)にした。
  • logステップDPを使えばもっと計算量を落とせるという噂があったが使えないような気が。
G問題
  • 2部探索が分かれば乱択は思いつきそう。
  • 個人的にはDより思いつきやすい気が。
H問題
  • 最初整数しかだめと勘違いしてて無理ゲーだろと思ったせいであまり考えてない。
  • 問題文がおもしろい。
I問題
  • 30分くらいかけてDAGのパス被覆問題に落とせることに気づく。
  • 本番中に提出された短いコードがほとんどのケースでACになっててテストケースが弱いことに気づく。
  • ジャッジで話しあってリジャッジをすることに。急いでテストケースを作成して追加した。ご迷惑をおかけしたことをお詫びします。
J問題
  • ACM/ICPCアジア地区予選東京大会2010の懇親会でmiracさんと話し合ったことがきっかけで作られた問題。
    • 問題をジャッジの間で公表する1,2日くらい前にビビビと来て急にWが2倍になった。
    • 途中で最初の想定解法(上2行を決め打ちすると残りは一意に決まる)が間違いだと分かったけど、その時にはバックトラックで十分高速に解けることが分かっていたので、頑張って任意のケースで高速に計算できることを証明した。
  • テストケースを作るのに苦労した。というか全然でかい答えになるケースが見つからないという。
    • 最終的には7*48で答えが65536になるケースを見つけたけどこれ以上の物は無い気が。
    • サンプルは解法のヒントを与えない範囲で親切にしたつもり。
  • 難易度的にはもうちょい手を付けられてもいい気がするんだけどなあ。
    • 一人しか挑戦して無くて難しい問題を作るとこうなるのかあという気分になった。
    • しかし、hosさんには想定解通りにほぼ解かれていて嬉しかった。

最後に、来年もぜひやりたいと思いますのでジャッジをやりたい方募集中です。

追記

KUPCのサーバのhttpdが落ちてるらしいのでCとJの解説を置いときます。
Siritori.pdf(C問題)
KnightsOut.pdf(J問題)

追記2

Jで答えが65536になるケース。見つけるのにかなり苦労した。

48 7
2 0 0 2 0 0 2
2 0 0 2 0 0 2
2 1 0 2 0 1 2
2 1 0 2 0 1 2
2 2 0 1 0 2 2
1 2 0 1 0 2 1
1 2 0 1 0 2 1
2 2 0 1 0 2 2
2 1 0 2 0 1 2
2 1 0 2 0 1 2
2 2 0 1 0 2 2
1 2 0 1 0 2 1
1 2 0 1 0 2 1
2 2 0 1 0 2 2
2 1 0 2 0 1 2
2 1 0 2 0 1 2
2 2 0 1 0 2 2
1 2 0 1 0 2 1
1 2 0 1 0 2 1
2 2 0 1 0 2 2
2 1 0 2 0 1 2
2 1 0 2 0 1 2
2 2 0 1 0 2 2
1 2 0 1 0 2 1
1 2 0 1 0 2 1
2 2 0 1 0 2 2
2 1 0 2 0 1 2
2 1 0 2 0 1 2
2 2 0 1 0 2 2
1 2 0 1 0 2 1
1 2 0 1 0 2 1
2 2 0 1 0 2 2
2 1 0 2 0 1 2
2 1 0 2 0 1 2
2 2 0 1 0 2 2
1 2 0 1 0 2 1
1 2 0 1 0 2 1
2 2 0 1 0 2 2
2 1 0 2 0 1 2
2 1 0 2 0 1 2
2 2 0 1 0 2 2
1 2 0 1 0 2 1
1 2 0 1 0 2 1
2 2 0 1 0 2 2
2 1 0 2 0 1 2
2 1 0 2 0 1 2
2 0 0 2 0 0 2
2 0 0 2 0 0 2