RUPC2015 Day1 運営記

(この記事には問題のネタバレを多分に含みます。)

立命合宿2015の運営でした。 ( ATND, AOJ ) コンテストの講評と解説はここにあります。

Day1の問題セットの準備に関することを書きます。

全体を通して

僕は事前準備は作問しかしていなく、当日も Clar に張り付いていたので、風船運びやプリント対応は完全に他の人に任せていました。すみません。 JAG の方も仰ってますが、こういうコンテスト中の仕事や会場, Wifi 等の事前準備も大切です。 コンテストは作問だけではありません。

問題のジャンルはまんべんなく散ったと思います。難易度に関しては許してください。

原案は色んな方に出してもらいましたが、問題文は全て僕が書きました。 必要十分で簡潔な問題文を書くのは大変難しいということが分かりました。 (その点でもりんごさんコンテストは素晴らしいですね… (ex.1, ex.2) 内容も去ることながら。)

テストと問題文校閲は後輩から OB まで色んな方に手伝っていただきました。感謝です。 特に、D問題の想定解はもともと僕が寝ぼけて書いた $O(N L^2)$ だったのですが、 1年生の後輩に指摘されて $O(NL)$ に落ちたという経緯があります。プロです。 問題文に関しても、他人のチェックが無ければ Clar の嵐だったと思われます。とにかく他人に見てもらうことが大事です。

手順はだいたい 2Dさんの記事 を参考にしました。 コードの共有は GitHub で、問題文の校閲は Google Docs で行いました。 Rime と testlib はプロコン以外でも使える場面があるのでは思いました。

2D さんの以外のググって出てきた記事 (author : yukicoders, cos さん, japlj さん, evima さん, hama_du さん, komiyam さん, nodchip さんなど) も全て読ませていただきました。 こういう記事本当に有益です。参加記だけでなく準備側の手記もばんばん残してほしいです。

A : サッカー

原案は @Rp7rf くんです。僕はよくわかっていないのですが、 彼は TopCoder MM のようなノリでサッカーなどの AI を作って戦わせる団体に入っています。 そこの競技から来た問題のようです。

問題としては書かれているとおりに実装するだけです。あまり言うことは無いです。 しかし、出力の桁が足りなかったり INF が小さすぎたり誤読していたりで AC 率は 45% ほどでした。 意外と低かった。

B : RUPC

原案は @ik11235 さんです。 もとは最終防衛線というタイトルで、最後の1問の難易度をちょうど良く設定するというストーリーでした。 しかし、この問題名は既出だったのと、 RUPC というタイトルの問題がまだ１つも無いということからこうなりました。

想定解は累積和です。和の持ち方を工夫すると二分探索は不要になります。 二分探索が必要な持ち方の場合はちょっとした罠に気をつけないといけなくなります。

C : 買い物

原案は @ik11235 さんです。 もとは「言い換え」というタイトルで、正月に親戚が集まった際に、 艦これ等のオタク的なものを適切に言葉を選んで説明するというものでした。 それを口伝えで聞いた後、自然な設定の問題文にできなかったため仮に現在の形で書いていたのですが、 それがそのまま残ってしまいました。 その結果 2D さんのコメント : https://twitter.com/Respect2D/status/576642709479260160

想定解は UnionFind または DFS です。実装量はあまり変わりませんが UnionFind の方が頭は楽です。 提出も UnionsFind の方が多かったように思います。

実はコンテスト 1 週間前までグラフの有向/無向が定まっていなかったのですが、 最終的に全体のバランスを見て無向グラフに決め、C問題となりました。 有向だと SCC してトポソして DP でしょうか。

D : こころぴょんぴょん

原案は @Rp7rf くんと私です。もとは御城プロジェクトというDMMのゲームが原案だったのですが、 彼が作問の時期に日本にいなく、あまり関われなかったので、幾多の変遷を経てごちうさとなりました。 ところで “Hoppoing Hearts” という英語訳は適切だったでしょうか。かなり慎重に選んだつもりだったのですが…

想定解は $O(NL)$ の DP です。 " $dp[i][j] := i $ 番目のうさぎが $x=j$ にいて、 $i-1$ までのうさぎが $j-1$ までにいるときの状態数” とおきます。 遷移に工夫が必要で、僕のように雑にやると $O(NL^2)$ でTLEします。 ここから BIT を使って $O(NL \log L)$ にして通している人もいました。

ほぼ全員が $a_i=0$ という罠に嵌っていました。テスターも全員嵌まりました。 僕は性格が悪いので、これで RE を出している解答を見るたびにこころぴょんぴょんしていました。 また、 long long dp[5000][5000] がMLE するというのは想定外でした。申し訳ありません。 ジャッジ解は全て int で取っていたため気が付きませんでした。 ML が 128MB というのも中途半端でミスを誘ったかもしれませんね。 AOJ 収録時には 256MB になる予定です。

E : 時のオカリナ

原案は @LazyMii くんと私です。なんか典型幅優先の問題が欲しいよねと持ちかけたところ、発案してくれました。 僕はゼルダシリーズをプレイしたことはほとんど無いので分からないのですが、 タイトルはムジュラの仮面のほうが適切だったようです。

想定解は $O(N^2R2^E)$ の幅優先探索だったのですが、 $\max(N^2R2^E)=2.56$ 億ですよね…。想定解にしては大きすぎますね。申し訳ありませんでした。 一応、始点・終点・イベントが起こる街だけのグラフに潰せば $O(E^2 2^E R)$ か少し手を抜いても $O(E! E R)$ になるので OK と言えば OK です。でも想定解ではなかったので AOJ 収録前に $E \leq 4$ くらいに減ると思われます。

F : 木

まず謝罪ですが、 UVa1674 とほぼ同じ内容でした。頂点への加算しているだけの差です。 事前に結構ググったのですが…

原案は私です。 コンテスト唯一の algorithm-driven の問題です。 うまいストーリーが生えなかったのでそのままの形での出題となりました。

発想は蟻本 295 ページの例題 (POJ2763) から得ました。というかほぼパクリです。 例題で使っているのはBITですが、これを区間 add のセグ木にしたらどうなるかと考え出したのがきっかけです。 私の貧弱な頭だと、問題の設定と解法を詰めるまでに 10 日くらいかかりました。 それを時間内に通すプロの方々は本当に尊敬します。

想定解は蟻本のように Eular-Tour で辺を列にした後、 segtree 等の range-add, range-sum が可能なデータ構造でやる方法です。 が、多くのプロには Heavy-Light Decomposition, Separator Decomposition, Link-Cut Tree 等の未知の手法で解かれてしまいました。 しかし後でググってみると、なんと全て iwi 先生のブログで紹介されていました。 僕の精進が足りないだけで典型だったのかも…

int でオーバーフロー、 DFS で RE という罠があります。 前者については、根に足しまくった後に葉同士の距離クエリが来るときなどに最大の $NQ \max(w)$ となります。 後者については、木の高さ $N-1$ のケース等です。人によってはライブラリの書き換えが必要になると思いますが、 そこまで時間がかかることでもなかったので含めました。 ジャッジはしっかりこれら両方に引っかかりました。 AOJ のスタックメモリは意外に小さいという知見を得ました。

一部想定の $O(Q \log N)$ で TLE し、つらい定数倍高速化をしていた人が見受けられました。申し訳ありません。 AOJ 収録時には $N,Q \leq 10^5 $ 程度になっていると思われます。

G : 爆弾

原案は @LazyMii と僕です。強実装枠ですがそこまででもないと思います。 最初期は空間幾何だったのですが、私が嫌なので2Dとなりました。

問題文で正確に条件を表現するのに苦労しました。

誤差については、僕の頭悪い実装で boost/multiprecision の mpfr を使った時の出力を想定解にしたときに、 long double でやっている解答が通る下限 × 10 を制約にしました。 出力が正しいことは、これに加えて目視でも一つ一つ確認しました。 しかし、それでも自信は無いので AOJ でどうしても通らないということがあれば Twitter でぼやいてくれれば調査します。 残念ながら、制約的に「乙」を含めることは出来ませんでした。

あと、コンテスト直後にみさわさんにもっと頭のいい方法を聞きました。 答えの領域の境界となりうるのは、辺の延長・共通内接線・街の境界しか無いので、 それらに囲まれてできる多角形を全部調べるというものです。 各多角形を調べるときには、その内部から代表する 1 点を代表して使えば OK です。 誰か実装してください。(僕も余裕ができたら実装します。) ところで、このように領域の境界になりうる直線のことを “エクストリームな直線” と言うのですね。

おわりに

気づいたらかなり長くなってしまっていました。読んでいただいた方はありがとうございます。 来年も体力があれば開催したいと思いますので是非ご参加ください。