KUPC 2012

KUPC Online Judge

今年もKUPCのジャッジをやっていました。今回原案を担当した問題はF,I,Kです。
去年の反省からDまでしか解けなくて暇になることが無いようにF以降の問題には部分点を入れています。また、KUPCでは実装が重い問題は出さずに、解法が思いつくまでに時間のかかる問題を出すようにしています。実際、宝探しの以外は普通に書いても2000B以下で書けます。ただ、この問題セットがたったの3時間で全完されるとはちょっと思っていませんでした。というか、I,J,Kがむずくて全完も出ないだろうと思ってた。
各問題の感想は以下のとおりです。

A,B,C,D

  • 簡単な問題群
    • よく名前を見かける人たちはここまで一瞬で解いていた。
  • 10問から11問に増えたのは、難易度をなだらかにするようにCが追加されたため

E

  • しりとりの次はじゃんけんだろうということでいる君が入れてた
  • 最悪ケースとかを想定して、完全ランダムも一番強い手を出し続けるのもWAだなあと思ってたら、両方組み合わせたらいけた
    • 皆てきとうにランダムとかやってWAくらってたけど、最悪ケースを考えて期待値を計算するくらいはやりましょうよ

F

  • 元ネタは同人ゲームのスグリ
    • 序文だけじゃなくて、日数の上限が1万年なのも元ネタ通り
    • あとMany years laterは続編の曲のタイトルです
  • この問題は去年の夏合宿の時に出そうとしたけど委員長の魔女と雰囲気が似ているということで却下されたので、今回出すことに

G

  • 最初見たときは一瞬k-meansやりたくなった
    • ZOJで解法が似たような問題をやったことがあったのでグリッド分割はすぐ思いついた
    • あとで平面走査でも普通に解けることに気がついた
  • ランダム回転して嘘平面走査が通るので思ったより多くの人が通したっぽい

H

  • ライツアウト系の問題。解法に至るまでに1時間くらいかかった
    • はまると全然解けない問題。本番でも強い人が通してなかったりするし

I

  • 事故から生まれた問題
    • 凸多角形を重心で切ったら面積は必ず半分になりますよねえとか嘘言ってた
    • 5/9以下になることをいる君が証明してくれたのでなんとかなった
    • あと最初はE<90度とかで分かりやすかった
  • 本番30分くらい前にリアクティブのプログラムを公開することに
    • 解法知ってるジャッジですらそれが無いとデバッグできなかったから
    • そして最後の最後でリアクティブのプログラムがバグっていることを指摘されて、またリジャッジになってしまいました。申し訳なかったです。
  • 結局最初から最後まで事故でできた問題だった

J

  • もう一つ問題あったんだけど、いる君が気に入らないとか言って差し替えてこれになった
    • 見たこと無い問題だったけど、切る部分をずらす時に計算量ケチれないかなあと思ったら4,50分で解けた
    • 実はpkuにもあるし有名問題だったらしくてわりと瞬殺されてた

K

  • 問題タイトルは去年のやつから取ってきて1文字増やしてみた
  • 最初は任意のパスについて同じコストになる設定だった
    • この条件をはずしたらどうなるんかなあと思ってはずしたらサイクル基底を使えば解けるなあってなった
    • もっと計算量落とせないかなあとねばってたら、今度は線形代数で普通に出る基底を使えば解けることに気がついた
    • 計算量が落ちたんで、n,m,q,wiの制約を書いてみたら絶望的な数値になった
  • ジェネレータを作るのものすごく苦労した
    • グラフなのでめんどい
    • しかも解法から分かる通り、辺の重みをランダムにすると答えが2^60-1になってしまう
    • 結局、解答2KBに対してジェネレータは18KBとかになった
  • 解法が上のような感じなんで、東大の強い人たちが瞬殺するか解かれないかの2択かなあと思ってた