ICPC夏合宿 2011 day4

原案はいる君が7問、私が3問。testerは私といる君。いもすさんは問題文担当という振り分けにしました。私は原案を6問程度提出したけどセットの都合上3つは今回使わないことになりました。
testerとして全問解いた時の感想は「考えるのは楽だけど実装が重く一昨年までのICPCっぽい・中盤の難易度の問題が多い」でした。
予想としては1位には8完はされそう、9完は実装が重くて無理っぽい、10完したら神という感じ。他の人はまあ3〜6,7問くらいでバラけるかな？という感じ。
実際にはE,G,Jを除いてFirstACが70分未満でものすごく速く、解く問題がバラバラの割には8,9完されるまで結構時間がかかってて良い感じでした。あと全体的にジャッジのコードより短いコードで通されました。
問題の難易度は人によって意見がわれると思いますが、
B<

A問題

好きな問題1。平面走査をする時にUnionFindを使って繋がっているかどうかを判定すれば、穴あき・非連結・辺を共有しないとくっつかないという条件でも解けます。(というか解いた時は連結という条件しかないと思ってた)

B問題

やるだけ。特に言うこともない。

C問題

近い数値はなるべくくっつけた方がいいのは割と自明だと思ってたのでもっと解かれると思ってた。

D問題

原案担当＆好きな問題2。知識ゲーなんで知ってる人には簡単なんだろうなあと思ってたら本当に瞬殺されてて吹いた。
Dinic*1000を落とすためだけに特殊なinput(サンプル4のでかい版)を1つ入れたけど誰も引っかからなくて、なぜか5頂点の完全グラフからランダムに辺を削除・追加するケースで大量に落ちてて訳が分からんかった。あとグラフの問題のジェネレータを作るのがめんどいけどどうしたらいいんでしょうか。

E問題

原案を担当したいる君が解いてみると、行ごと処理して死にまくっててシュールな状態になってた。あと最初はW,H<=15くらいで無理ゲーだった。計算量を見積もるのは難しいですね。

F問題

原案担当。解法が自明な気がしてあまり考えてなかったら別解があって、「ああそうですね」という気分。あとN=1のケースが少なく、テストケースが弱い疑惑が(AOJでは追加されました)。

G問題

ビジュアライザが無いとデバッグが無理ゲーな気が。あとeha君が2時間くらいで解いてて驚いた。

H問題

問題文が読みにくいと言われたがそういうのを少なくするにはどうしたらいいんだろうか。

I問題

原案担当＆好きな問題3。元々は天才プログラマーのN君が邪教の館で悪魔合体をする問題。
どっかに行くバスの中で解けるかを考えていたら30〜60分程度で解けることが分かったんでそこまでやばくは無いと思ってたけど、KUPCのメンツに見せたら(考えてないだけかもしれんけど)全然解かれなくて「あれ？」ってなった。本番中には予想以上に解かれて良かったです。
ちなみに入力が小さいのは制約が意味ないことに気づけばもうokという気分だったので。ループを回して解くことは想定してませんでした。

J問題

実は9問セットだったと言われても仕方がない問題。解法を見ながらじゃないと解けませんでした。途中で解法に穴があると思ってテストしてみたら、ことごとく「4方向の2つまでしか開けられない」という制約で弾かれててすごかった。