Maximum Winter Contest 2006

プログラミング

埼玉大のサークルMaximumが主催する、ICPCとほとんど同じ形式のコンテスト。ただ大きく違う点は、

  • 参加資格に制限がない(OB/OGでも参加できる)
  • 個人戦

ということ。普段のコンテストとは一味違ってまた面白い。

実際の問題セットとジャッジの入出力はこちらで公開されている。

以下、実際のコンテスト中の記録。


今回の制限時間は12:30から4時間半で、問題数が8問。

Problem A "Profit Maximization in Casino"

スタートしてすぐに、とりあえず問題を印刷。最初に出てきた問題Aを読む。
が、いきなりわけが分からない… 何度も読んで、Sample Input/Outputを見てみたところで、もしかしてただの足し算？ と思い当たって、そんなに簡単でいいのかとまたさらに悩まされる。
とりあえず負の数は入れてはいけないよね、ということで正の数だけ和をとるようにしてsubmit。WA。この瞬間、通称陰険株式会社の黄さんが笑っている様子がテレパシーか何かのように思い浮かんだ。くそう。
で、全てが負の数のケースでもひとつはとらなくてはいけないことに気づいて再submit。AC。

Problem B "Saitama Destiny Land"

Sample Input/Outputがアレゲで笑った。
最適化問題。最初、ナップサック問題が思い浮かんだけど、容量が2^31までとなっているので不可。その直後にアイテム数が最大20ということに気づいたのでgenerate&testをやることに。
最初にアトラクションの名前でソートしておいて、なるべく最初の項目を取るようにしてDFS。submit。WA。同じ満足度のとき、アトラクション数が少ない方を取るという条件を勘違いして、逆に多い方にしていた。不等号の向きを変えてsubmit。AC。

interlude

Problem Cを読んだけど、A,Bと違ってぱっと解法が思いつかなかったのであとまわしにして、とりあえず問題を全部読むことに。

Problem F "The Adventure of Dai"

ルーうって一体どういうネーミングですか。
グラフの問題。実はただのMSTということがすぐ分かったので、ぱぱっとKruskalを書いてsubmit。WA。あー、非連結な場合を考えてなかった。そこを修正してsubmit。AC。

Problem E "Destroy the Castle Wall"

幾何。点の数が多いから、いちいち交差判定をするようなアルゴリズムでは絶対に間に合わない。原点からの仰角を求めてあとは範囲計算かな、と思ったけど、最初、点が第一象限にしかないことに気づかなくて、-piと+piの間をつなげる処理とかが酷く大変そうだと思って敬遠していた。第一象限の制限に気づいたところでコーディング開始。角度区間に落としたあとは、終点順にソートして、もっとも小さい角度の終点から順にそこを撃っていく貪欲法で射撃数を求める。これは一発でAC。

Problem C "Finding the Padekia Root"

幾何。任意の二つの円について交点をとって、その交点が全ての円に含まれているかどうかをチェックすればとりあえずは良い(最終的に全ての円の積として残る部分はかならずどれか二円の交点をその境界上に持つから)のだけど、円の数が1024なのでO(n^3)のアルゴリズムは普段ならちょっとありえない。でも、まわりの状況を見てみるとみんな(特に埼玉大の人)が続々とこの問題を解いていたので、実はそんなに悩まなくてももしかして何とかなっちゃう？ と思うことにして実装開始。
もともと重いアルゴリズムなので、できるだけ速度が速くなるように書こうと思って書いていたら、すさまじくスパゲッティコードになった。とりあえずできたと思ってsubmitするもWA。とりあえずTLEが出なかったことに希望を持って、許容誤差が大きすぎたかな？ と思って誤差の値を小さくして再submit、WA。
結局間違えていたのは、

  • 任意の二点を持ってくるときに(i,j)と(j,i)のペアを両方とも拾ってしまっていた(R(i)>=R(j)を仮定していたコードなので致命的)
  • 円が他の円を包含するときの処理をし忘れていた
  • 包含するときの判定を入れたあとも、そこがエンバグしていた

という具合で、結局ACするまでに12submit。もうここまできたらきっと時間では他の人に負けてしまうに違いないので、ここからはsubmitデバッグをためらわずにやることにした。

Problem H "Design of the Museum"

グラフ。最初は完全に知識問題だと思って捨てたけど、それにしては解いている人が結構多かったので考えてみることに。
ちょっと考えてみると、実は次数最大の頂点を取って、それを次数のなるべく大きい頂点に貪欲的につなげていけばいいのね。ある頂点の辺を全て他の頂点に繋げようとしたときに実行できないことがあるとしたら、それは辺を繋げられる頂点が足りないときだけ。ということは、辺をつなげる時には他の頂点の次数をなるべく下げるようにすればいい。
…といってもあまり自信はなかったので、submitしてACをもらったときは儲け物だと思った。

Problem G "TOKOSHI's Trip"

明らかにダイナミック計画法(TM)。しかし、問題の条件を漸化式に落とすのが非常に面倒で分かりづらい。ぼくはこういう複雑なDPの場合はメモ付き探索の方が感覚的に書けて良いと思っているので、そちらで書いた。が、どうやらオーバーヘッドがシビアらしくTLEが抜けず、そのままコンテスト終了。

懇親会

19:00から、東京駅近くに参加者が集まって懇親会。
順位的にはこうなって、3位。上位のk.inabaさんとid:tanakhさんはオープン参加だったので、公式には繰上げ1位、らしい。
懇親会ではk.inabaさんはやっぱり凄いなぁということで参加者の意見が一致。7問を颯爽と解いて(ぼくより1問多く解いているのに既に時間で負けているし)、ほとんどの人が手をつけなかったProblem Dに対して7submit。流石です。

その後、二次会に行こうかという話もあったけど、時間の都合上見送ることに。色々と楽しそうだっただけに残念。また今度の機会があれば行きましょう。

ところで

繰上げ1位というわけで、賞品を頂きました。で、その賞品があまりにもアレゲなのでここにネタとして載せようかと思ったんですが… よく考えてみると、あれって結構やばいのでは？(笑
というわけで、掲載はやめておきます...