World Finals 問題解説

ICPC

上の文章が良く分からん感じになってしまったので、
問題についての説明だけこっちにも書いておきます。

http://icpc.baylor.edu/icpc/Finals/2005FinalsProblemSet.pdf

問題はここから参照できます。

  • 問題A

一方の図が他方の図の一部になっているかを判定する問題。
難問。はっきりと捨て問題でしょう。

  • 問題B

いくつか無線のアクセスポイントがあって、
その最も近いところと通信を行いながら町を移動する。
ある町からある町へ移動するときに、最も少ない切り替え回数を求めよ、という問題。
グラフを作ってダイクストラ。
グラフを作るのは…がんばれ。

  • 問題C

無限に相乗りできるタクシーを使って複数の人が一箇所に集結したいとき、
最もコストを小さくせよ、という問題。
最小全域木の部分木を求める。

  • 問題D

ある人がカードを何回か(10回以下)シャッフル(パーフェクトシャッフル)する。
シャッフルが成功すると前半と後半が完全に一枚ずつ交互に並ぶ。
シャッフルは失敗するかもしれない。失敗すると本来あるべき位置が
どこか一箇所入れ替わってしまう。
シャッフル済みカードの列が与えられたとき、何回シャッフルしたか、
何回目にどこを失敗したか、を求める問題。
深さ優先探索+枝刈りで解けてしまいます。

  • 問題E

いくつかアパートが与えられ、指定された部屋に対して
日光が当たる時間を求めよ。という問題。
簡単な問題。特に書くことはなし。

  • 問題F

家から大学までなるべく道を横切らずに行きたい。
最低何回横切らなければならないか?
解き方は…まだ考えていない。
これもグラフ生成+ダイクストラかな?

  • 問題G

与えられた図形が無限に敷き詰め可能な図形か判定せよ。
本文中にヒントがあるらしいが、それでも難問。
これも捨て確定。

  • 問題H

万里の長城ゲームという、n*nの盤面に適当にn個の石が配置された状態から
石を動かして一直線に並べるというゲームを考える。
石を一ます動かすのを一手とするとき、最短手数を求めよ、という問題。
手数は各石の出発地点から到達地点へのマンハッタン距離の合計に等しくなる(多分)
ので、各石がどこに行くのかを求める二部グラフのマッチング問題となる。
マッチング自体はハンガリー法というのを使えば解けるらしい。
(私は知らないけど…)

  • 問題I

いくつかのイベントが開かれ、いくつか部屋が用意される。
部屋には入れる人数と使える時間が決められていて、
イベントの参加人数と時間が部屋の条件に収まっていればその部屋が使える。
なるべく多くのイベントが部屋に入るように、
イベント数が同じなら参加人数が一番多くなるようにするにはどうすればいいのか。
…おそらくこれもマッチング。

  • 問題J

アンテナを立てる場所がいくつか(<20)あって、それぞれカバーできる人口がちがう。
複数のアンテナにカバーされる領域もある。
アンテナを立てる本数が与えられるので、カバーできる人口を最も多くせよ。
20C10が非常に小さい数なので、全探索すれば終了。


…ちなみにうちのチームが本番で解いたのはBDEJ、です。