University of Aizu Programming Contest 2010 (解説)

無事に・・・というわけではありませんが、終了しました。多くの方々のご参加、誠にありがとうございました。
簡単ではありますが、解説を公開します。元ネタクイズの解答付きです。

Problem A: Citation Format

問題文の通り書くだけです。Presentation Errorとなっている方が散見されましたが、Outputにも書いてある通り、行末に無駄な空白文字を入れないように気をつけてください。

Statistics

Total Accept/Submit: 94/217 (43.3%)
First Accept: mirac (3 min)

元ネタ

特にありません。

Problem B: Old Bridges

貪欲法です。吊り橋の耐久力が低い島から順番に回っていけば大丈夫です。詳しい証明はきっと原案担当の id:iakasT 君が書いてくれるに違いありません。
状態空間 O(2ⁿ) のDPに走った人が結構な数見受けられましたが、残念ながらそれでは間に合いません。

Statistics

Total Accept/Submit: 94/217 (36.4%)
First Accept: mirac (6 min)

元ネタ

特にありません。原案ではタスクの所要時間と締め切りが与えられる問題だったのですが、これをどれだけアグレッシブに変えられるか試してみたところ、こうなりました。

Problem C: Accelerated Railgun

シミュレーションに走りたくなりますが、実は単純な解法が存在します。実は研究所に超電磁砲が当たるのは、(射程距離を無視すれば)　直接研究所に向って撃つか、あるいはその正反対を向いて撃つ場合に限られます。
証明は以下のようになります。超電磁砲が t 秒間動いて当たったとして、そのときの速度ベクトルを v とします。この超電磁砲の軌道を逆からトレースするには、原点から速度 -v で発射して t 秒間動かせばいいことになります。等速直線運動も跳ね返りも時間について対称なためです。しかし、原点から発射された超電磁砲は、発射方向がどうであれ明らかに直径の上を往復します。よって、直径の上から外れないような2通りの撃ち方のみが命中します。
という証明を考えていたのですが、LayCurseさんの言う (入射角) = (反射角) = 0 の方がシンプルですね。
さて、ここまで分かればあとは高校数学です。現在地から原点へ向かうベクトルと速度ベクトルの内積を取り、2つのベクトルの角度の cos を求めます。1 であれば直接当たる、-1であれば一度跳ね返って当たる、それ以外は百年待っても当たりません。うっかり射程距離を忘れないようにしてください。
シミュレーションに誘導するように問題文を書いたのですが、みんな割とあっさり看破したようで、ちょっと悔しいです。

Statistics

Total Accept/Submit: 25/119 (21.0%)
First Accept: rng_58 (23 min)

元ネタ

みんな大好き超電磁砲。ところで、原作のアクセラレータさんの反射は「速度ベクトル v を -v にする」というものなのですが、これ反射って言っていいのだろうか？
第一段落は頑張り過ぎました。英訳が異常に大変でした。しかも一ヶ所誤記がありまして、申し訳ございません。

Problem D: Distorted Love

特に難しいところはありません。サイズも小さいので、問題文の要求の通りに適当実装してください。私は back 用と forward 用に2本スタックを用意しました。

Statistics

Total Accept/Submit: 55/207 (26.5%)
First Accept: lyrically (29 min)

元ネタ

特にありません。典型的なヤンデレの方にご登場いただきました。空の鍋をかき回したり紅茶に剃刀入れたりさせようかと思いましたが、問題の要求と絡みそうに無いのでやめました。

Problem E: Huge Family

問題文における人を頂点に、家族割引を辺に対応させたグラフを考えれば、clanとは以下のようになります。
1. グラフ G(V, E) の辺の部分集合 E' であり、
2. どんな頂点 u, v についても G(V, E) において u から v へ到達可能ならば G(V, E') でも u から v へ到達可能であり、
3. その上で重みの和が最小
つまり、最小全域木です。厳密に言えば与えられるグラフは連結とは限らないので、MSF (Minimal Spanning Forest: 最小全域森 = 各連結成分ごとにMSTを取ったもの) です。
MSFの個数を求めれば、すなわち各連結成分についてMSTの数を求めて掛け合わせればいいのですが、その前に問題文にわざとらしく書いてある「全ての頂点の次数が2」という情報を思い出しましょう。いくつか図を描いてみれば分かると思いますが、全ての頂点の次数が2である単純なグラフは、1つの単純な閉路になります。よって、最も重い辺を1つ取り除けばMSTが完成します。ここで、最も重い辺が複数あれば、その数だけ自由度があることになります。
まとめると、連結成分に分解して、連結成分ごとに最も重い辺の数を求め、それらを掛け合わせれば答えが求められます。
最大ケースでは、連結成分に分解するときに再帰を使ってDFSするとスタックオーバーフローするので注意しましょう。BFSするか、スタックを自前で作るか、あるいはアドホックに書く必要があります。下手に書くと、ここがちょっと面倒くさいです。
PrimやKruskalなんぞをする必要がないので簡単だと思ってたのですが、Statisticsを見るとみんな苦戦したようです。絶対超電磁砲の方が難しいと思うんだけどなぁ。

Statistics

Total Accept/Submit: 16/38 (42.1%)
First Accept: kinaba (28 min)

元ネタ

だんご大家族 (アニメ「CLANNAD」ED)

何が言いたいかと言いますと、

♪仲良しだんご 手をつなぎ大きな丸い輪になるよ

というのが大きなヒントだったのです。

Problem F: Ben Toh

動的計画法によって解く問題です。ちょっと丁寧に解説してみます。
まずは、小さなケースに対して樹形図を書いて考えましょう。綺麗な図を書くのが面倒だったので、手書き & デジカメにて失礼します。

○のノードは弁当を手に入れたことを、×は入手に失敗したことを、辺の上の数はその状態遷移が起きる確率を表します。
すると各ノードに到達する確率は、ルートからそのノードまでのパス上の確率を全て掛け合わせたものになります。弁当を手に入れた全てのノードについて、そこへの到達確率を求め、足し合わせれば期待値が得られます。これらを上の樹形図に書き込むと、下の図のようになります。ノードの下に書かれている数がそこへの到達確率を、E_day(n) は n 日目に得られる弁当の個数の期待値を、E(n) は n 日間通して得られる弁当の個数の期待値 (= 出力すべき答え) を表します。

樹形図によって小さなケースに対して答えが得られましたが、これでは問題を解くのに不十分です。樹形図の大きさは爆発的に大きくなるためです。そこで、以下の知見を使います。上図の4日目に2つある弁当の入手に失敗した状態は、特に区別する必要がありません。どちらも「4日目」で「過去0日連続で弁当を獲得している」ために、その後起こり得るシチュエーションはまったくもって等しいのです。一般的に、「n日目」で「過去c日連続で弁当を獲得している」状態は全て同一視することができます。従って、prob[n][c] := 「n日目」で「過去c日連続で弁当を獲得している」確率を計算していく動的計画法を考えることができます。prob[n][0]のみが、その日弁当の入手に失敗した状態を表します。
が、やっぱりこれも不十分です。これは O(n²)の計算量ですが、n = 100,000なのでTLEになってしまいます。そこで、もう一つの知見を使います。弁当を入手する確率はどんどん半分になっていくので、長期間に渡って弁当を獲得する可能性は限りなく 0 に近付きます。上の樹形図にもあるとおり、実際4日連続で弁当を入手する確率はわずか 1.56% しかありません。100日連続で獲得する確率など無視できるでしょう。なので、prob[n][c] (c>100) を 0 で近似することができます。これによって、計算量は O(n) になって間に合います。
厳密には、prob[n][c]を勝手に d だけ変化させても求める期待値はたかだか d しか変化せず、かつ sum(prob[n][100..n]) が十分小さいことを示す必要があります。そんなに難しくないので省略します。
誤差に関する制約は不自然に緩いものに見えますが、最大ケースで期待値が 60,000 程度になるので、有効桁数を考えればそれほど緩くもありません。実際、long doubleで計算するかどうかで 10^-5 程度の違いが出るようです。
私は結構頭がこんがらがったのですが、みんなさくさく解いてきました。すごいなぁ。

嘘解法

なんとなく、n 日目に得られる弁当の個数の期待値 E_day(n) はある値に収束していくように見えます。実際に、n = 100 のあたりで E_day(n) = 0.621446217... になっていて、以後動く気配を見せません。よって、O(n²) で計算できる所だけ真面目に計算して、残りは掛け算一発で求めるという手も無きにしもあらずです。まさかの O(1) です。さすがに本当の解法よりは多くの誤差が出ますが、n = 10⁹ ぐらいまでならこれで解けるかもしれません。

Statistics

Total Accept/Submit: 14/57 (24.5%)
First Accept: laycurse (34 min)

元ネタ

「ベン・トー」(著・アサウラ、スーパーダッシュ文庫)

あまり知られてないようですが、私の好きな小説の一つです。これを読むと弁当が3倍ぐらいおいしくいただけますのでマジお勧め。
ちなみに、この問題を思い付いたのはポケモンからです。「まもる」を n ターン使いつづけたときの成功回数の期待値は？という問題だったのですが、ベン・トーを広めたくてこうしてみました。

Problem G: Rolling Dice

cost[x][y][d] = (x, y) にいて、サイコロの状態が d である状態への最短距離を、ダイクストラ法で求めていきます。サイコロの状態は上の面と右の面が決まれば一意に定まりますので、24通りの状態があることになります。つまり 10 * 10 * 24 ノードしかないので、普通に書けばTLEになることはないでしょう。実装問題です。
サイコロの回転と、サイコロから整数値への変換を注意深く実装してください。後者はハッシュ関数を書くか、C++ならばstd::mapを使うと楽でしょう。

Statistics

Total Accept/Submit: 26/91 (28.5%)
First Accept: hs484 (49 min)

元ネタ

言わずと知れたあの国です。偉い人にすっごく怒られそうなので、あまり立ち入ったコメントはしないでおきます。マスゲームとも掛けているのではという考察をいただきましたが、私はそこまで頭は回っていませんでした。うまいこと言うなぁ。
将軍様の高貴な脳みそはスーパーコンピュータZ-80である、とか言いかけましたけど全力で自重しました。

Problem H: Winter Bells

言うまでもなく、全ての可能な最短経路を探索することは不可能です。簡単に爆発します。
ノード c を通る確率を求めるには、定義どおり、(ノード c を通る最短路の数) / (全ての最短路の数) が求まればいいことになり、それはすなわち (スタートからノード c への最短路の数) * (ノード c からゴールへの最短路の数) / (全ての最短路の数) に他なりません。これを求めるには、よく知られている最短経路木を拡張した、最短経路DAG というものを考えます。
最短経路木では、その辺に沿って進めば必ず最短経路になりますが、それが全ての最短経路を含むとは限りません。そこで、「その辺に沿って進めば必ず最短経路になり」「その辺から外れれば必ず最短経路にならない」というようなグラフを考えます。これは明らかに閉路を持たないので、DAG (Directed Acyclic Graph) になります。これを最短経路DAG と呼びましょう。
最短経路DAGは、最短経路木を求めるのと同様に求められます。多分。しかし、ここでは n = 100 なので、より簡単で遅い方法で構築できます。
まず、Warshall-Floydで全点間最短経路をさっくり求めましょう。次に、辺 (u, v) (重み w) が最短経路DAGに含まれるかどうかを判定します。ノード a, b 間の最短経路を sp(a, b) とすると、sp(0, u) + w + sp(v, n-1) = sp(0, n-1) ならばこの辺を使った最短経路が存在するので、辺 (u, v) は最短経路DAGに (u -> vへ方向付けて) 含まれることが分かります。
最短経路DAGが求まれば、後は典型的なDPによってパスの数を数えるだけです。
このアルゴリズムを使っていたにもかかわらず、Wrong Answerのまま終わってしまったように見える人もちらほら見受けられました。引っ掛けどころは、パスの数を数えるところにあります。intで計算するとオーバーフローするのでlong longを使えばいいと見せかけて、実はlong longでもオーバーフローします。BigIntegerを使うという手もありますが、doubleでも問題ありません。
最短経路DAGが見えれば単純なDPなので、Fよりは簡単だろうと思ってたのですが、そうでもなかったようです。もしTopCoderに出してたらオーバーフローで撃墜祭りになってたかも。一発で通したのは rng_58 さんただ一人でした。拍手。

Statistics

Total Accept/Submit: 10/83 (12.0 %)
First Accept: laycurse (26 min)

元ネタ

「Winter Bells♪」(しろくまベルスターズ OP) [youtube]

茶太の声があまりにも可愛かったので、問題になってしまいました。Problem Cとで茶太がかぶってしまったけどまぁいいや。茶太の曲の中ではこれとsee-saw!!が一番好きです。
原作に準じて、英語版ではサンタの代名詞が she, トナカイの代名詞が he になってるのも地味にポイントです。

Problem I: Mysterious Onslaught

まず初めに、いくつかの基本的な事柄を確認しておきましょう。

同じ範囲に向けて 2回以上みょんを放つ必要はない
複数回みょんを放つとき、どんな順番で放っても結果は変わらない

自明ですよね。

探索

状態空間 2²⁵ を探索するのが良さそうに見えますが、もちろんこれはメモリに載りません。全部探索していては TLE です。単純な枝刈りとして左右反転・回転を同一視すると言うものが考えられますが、それでもまだ不十分です。
審判が考えた枝刈りとして、4 * 5 のパターンについて最初に答えを求め、メモしておくというものがあります。これは 2²⁰ の状態空間になりますので、メモリに載せることができます。これがあれば n <= 4 のケースは直ちに求められますし、n = 5 についても 2 - 5 行目のみを範囲としたみょんを考えなくてもよくなります。前処理に若干の時間がかかりますが、その後は十分速く計算できます。
また、ビット演算を活用しても高速化が見込まれます。

DP

実はDPによる解法も存在します。
ポイントは、1列ごとに考えることです。以下、n = 5を例に挙げて説明しましょう。
ある列に対して1回だけみょんを掛けるとき、その掛け方は 5 + 4 + 3 + 2 + 1 = 15 通りです。ということは、ある列に対する任意のみょんの掛け方は 2¹⁵ = 32,768通りに限られます。よって、dp[i][s] := 「i 列目までの全ての敵を戦闘不能にして、i 列目に使ったみょんの集合が s であるときの、最小のみょんの回数」を管理していくDPによって解くことができます。
全ての s について dp[i][s] が求まったときに次の列 dp[i+1][t] を求めるには、基本的には任意の s について min(dp[i][s] + |t|) を求めればいいのです。しかし、i 列目と i+1 列目で同じみょんを使った場合、それらはつなげて一つのみょんにすることができます。つまり min(dp[i][s] + |t| - |s and t|) です。これを全ての t に対して求めれば、i+1 列目のテーブルも埋めることができます。
これによってテーブルは埋まることは埋まりますが、しかしながらTLEです。先ほど言ったように s, t はそれぞれ 2¹⁵ 通りあるので、一列ごとに 2³⁰ 掛かってしまうためです。ここで、問題文の重要な制約を思い出します。i 列目に対するみょんの集合はどんなものを使ってもよいわけではなく、i 列目の全ての敵を戦闘不能にするような組み合わせでなければならないのです。
そこで、2¹⁵通りのみょんの組み合わせを、どの敵の組み合わせを殲滅できるかによって分類します。ある1列の敵の組み合わせは 2⁵ 通りなので、均等に分布すると仮定すれば、どの敵の組み合わせを殲滅するみょんも 2¹⁰ 通りになることが期待されます。実際に計算してみると、実は綺麗にその通りになっています。従って、各列を殲滅できるようなみょんだけを考えれば、各列ごとに掛かる計算量は 2²⁰ ぐらいになって間に合うことが分かります。
あとはビットDPをちまちま実装するのみです。
赤い人たちはあっさりさっくりDPで解いてくると思っていたのですが、みんな揃って探索に走ったようです。長い時間制限と、FとGがDPだったことから探索だと踏んだのでしょうか。審判としてもDPばかりの問題セットは避けたかったのですが、そもそもDP解法に気付いたのがコンテスト直前だったので妥協しました。

Statistics

Total Accept/Submit: 4/68 (5.8%)
First Accept: laycurse (182 min)

元ネタ

最強最速アルゴリズマー養成講座 (ITmedia)

最強最速アルゴリズマー養成講座の著者にしてぼくらのアイドル chokudai 先生の口癖をお借りしました。
この問題が出来たとき、審判団は早々とDPに見切りを付け、こぞって探索解法を探しました。その末に出来たのが上の部分メモ化解法です。
しかしその後、アルゴリズマーの記事 (SRM383 Div1 Medium)を読んだところ、「もしかしたらこれってDPでいけるんじゃね？」と思い始めたのでした。そしてDP解法が発見されたのです。
そんなわけで、chokudai 先生への感謝を込めて、みょんをテーマに問題文を作ってみました。地味に問題名も MYsterious ONslaught になっています。myで始まる単語は割とあっさり思い付きましたが、onで始まる単語は辞書を引いてもなかなか見つからなくて焦りました。
そもそも「みょん」の元ネタは東方妖々夢 (に登場する、「妙な」と「ひょんな」が合わさった造語) と思われるので、これらの単語も問題文に入れておきました。

Problem J: No Story

L <= <10¹² という入力サイズからすぐに O(sqrt(L)) が見え、素因数分解とか約数列挙のような匂いが漂ってきますがその通りです。
i 番目に小さな素数を p_i と書きましょう。a の素因数分解を、(a₁, a₂, ...) を使って
$a = \prod_{i=1}^{\infty}p_i^{a_i}$
と書くことにすると、a, b の最小公倍数は以下のように表すことが出来ます。
$LCM(a, b) = \prod_{i=1}^{\infty}p_i^{max(a_i, b_i)}$
つまり、Lを素因数分解しておけば、(a₁, a₂, ...) を決め打ったときに対応する (b₁, b₂, ...) が何通りあるかは簡単に計算できます。
しかし、このままでは a <= b でないものも数えてしまうので、あとで帳尻を合わせる必要があります。2で割れば良さそうに見えますが、それでは一度しか数えられない a = b のケースを減らしすぎてしまいます。が、よく考えれば自明に LCM(a, a) = a なので、要するに 1 を足して 2 で割ればよろしいのです。
a を決め打たなくても、L の素因数分解が (すなわち、(L₁, L₂, ...) が) 分かれば計算で求まりそうな気もします。数学が得意な人、誰かお願いします。

遅い解法

L に比べて L の約数の数はそんなに多くないことを使って、 L の約数を全列挙し、そこから2つ選ぶ全ての組み合わせに対してLCMが L になるかどうか調べる、という解法も考えられます。さすがにこれは単純過ぎるので、この解法が Accept にならないようにジャッジデータを調整しました。ここにいくつかの高速化を加えれば Accept 出来なくもありませんが、おそらくそれは普通の解法より面倒くさいことになると思います。

Statistics

Total Accept/Submit: 19/83 (22.8%)
First Accept: laycurse (10 min)

元ネタ

特にありません。「私は長い問題文を書くのに疲れたので」という下りは、割と本気な私の心の叫びです。
JAGの問題にも妙に短いのがあったなぁ、ともちょっと思ってましたが。

Problem K: Seventh Color

審判の解法にミスがあったために、この問題は無かったことになりました。大変申し訳ございません。なお、コンテスト中に使われたジャッジデータには間違いがないことが確認されています。
問題はAOJ1061にアップロードされましたが、これは解答が作られたときに利用可能になります。

元ネタ

Princess Drawing!

ぐりぐり描ける新感覚シューティングゲーム。チームメイトの @romanchu 君がプログラムを書いているということで、今回ネタとして拝借させていただきました。無許可で。
時代はやっぱり男の娘なんでしょうかね。コピック君かわいい。

Final Standing

こちらで見ることが出来ます。
優勝は10問を解いた rng_58 さんでした。おめでとうございます。同じく事実上の全問正解を果たした lyrically さん、laycurse さん、tanakh さんがそれに続きました。

Comments

みんな解く速さがおかしすぎると思いました。
解く順番もおかしすぎると思いました。
全完されるのは覚悟してましたが、30分でほとんどの問題が通されるのはさすがに予想外です。
- 審判団涙目です。
なお、私は A, C, E, F, H, I, J (, K) の原案と全ての問題の日本語文、B, C, E, F, G, H, I, J の英訳を担当しました。
- これは頑張りすぎだろ作業量的に考えて...とかつぶやきながらがりがり作業してました。
  - Twitter上で励ましの言葉をくださった皆様、ありがとうございました。
問題文では好き勝手させていただきました。
- 面白かったよーという反響をいただいております。誠にありがとうございます。

参加された皆さん、お疲れさまでした。ありがとうございました。
疑問質問御意見御感想などありましたら、コメント欄にお寄せください。