Regionals 2010 :: Asia - Kuala Lumpur
会津の練習会
http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=593
4994 - Overlapping Scenes
問題
文字列がn個与えられる。
n個の文字列を並べ替えて連結する。
このとき、重複している部分があれば、重ねて連結することが出来る。
このとき出来上がる文字列の長さの最小値を求めよ。
制約
n<=6
文字列の長さ<=10
解法
n!全部試して連結するだけ。
完全に包含しているのを中に入れることはできないことに注意。
例えば、{ABA,B}は4。
4995 - Language Detection
超やるだけ
4996 - Scientific Experiment
卵をビルの色々な階から落として、どこで始めて割れるかを調べる。
- ビルはn+1階建てであり、0階（１階）から落とした場合は割れず、n階(n+1階)から落とした場合は必ず割れる
- 好きな階から卵を落とすことが出来る
- 卵は１度に１個しか持てない
- 卵が落とした後は必ずビルを出て確認する
- 卵が割れた場合は回収しないが、割れなかった場合は必ず回収して使い回す
- 卵を持っていないときビルに入るのはyセントかかり、卵を持っているときビルに入るのはzセントかかる
- 卵が割れた場合、まだ実験したければビルの中で卵を買う。このとxセントかかる
- 最後に卵が残っていた場合、x/2セントで売ることができる
最善の手順で実験を行った場合、最悪の場合かかる費用の最小値を求めよ。
制約
n<=1000
解法
dp[i][j][k] = いまビルの外にいて、k=1なら卵を持っていて、i階からj階に答えがあるときの、最悪の費用の最小値(j階では必ず割れる)
というDPをすれば解けそう。
しかしこれだとO(n^3)で間に合わない。
ここで、階の幅が重要であり、例えばdp[i][j][k]=dp[i+1][j+1][k]は答えが一緒ということに注目する。
すると、
dp[i][k] = いまビルの外にいて、k=1なら卵を持っていて、1階からi階に答えがある時の、最悪の費用の最小値（i階では必ず割れる）
を考えることにより、O(n^2)となる。
4997 - ABCD Tiles
問題
N×Nの壁があり、はじめタイルAで覆われていたが、今いくつかのタイルが剥がれている。
剥がれている箇所に新しいタイルを貼りたい。
今使えるタイルは、タイルB、タイルC、タイルDの３種類で、全て以下のような形をしている。
×○×
○○○
×○×
このとき、うまくタイルを取り付けることが出来るかを調べよ。
取り付けることが出来る場合は、その具体例の辞書順最小を示せ。
ただし、タイルB,C,Dを貼るとき、同じ種類のタイルが辺や頂点を共有してはならない。
制約
N<=15
解法
枝刈り探索。
左上からB,C,Dの順でタイルを張っていく。
4998 - Simple Encryption
4999 - Electricity Connection
5000 - Underwater Snipers
問題
y>kの領域に敵がN人いる。
y
制約
- 10^8≤k≤10^8
1≤N≤10000
1≤S≤10000
1≤D≤10^9
解法
二分探索+貪欲。
スナイパーを異なるy座標に位置させることは意味がないので、全てのスナイパーのy座標はyとして考える。
このとき、貪欲で必要最低限のスナイパーの数（無理ならINF）を求め、Sより大きいかで二分探索における分岐を行う。
貪欲のやり方は、[id:sune2:20120710:134192860241]の「POJ 1328 - Radar Installation」参照。
ただしフラグを立てるループをupper_boundで範囲限定してO(n^2)にならないようにする。
5001 - Making Quadrilaterals
問題
n本の棒から、どのような４本を取り出しても四角形を構成できないとき、n本の棒の長さの最大値の最小値を求めよ。
棒の長さは1以上の整数とする。
制約
n<=60
解法
n=4のとき{1,1,1,3}
n=6のとき{1,1,1,3,5,9}
四角形を構成できないのは、
一番大きな辺>=残りの辺の和
のときである。
今の棒集合に1本加えても四角形を作れないようにするためには、今の棒集合のうち最長の棒3本を足した長さの棒を加えれば良いことが分かる。
f[n]を答えとすると、
f[n] = f[n-1]+f[n-2]+f[n-3]
これはトリボナッチ数である。
5002 - The Queue
問題
要素数nの根付き木が与えられる。
各ノードをキューに入れるが、各ノードは親より先にキューに入ることはできない。
このときキューの中身として考えられるものの総数をmod 10^9+7で求めよ。
制約
n<=1000
解法
i以下のノードの個数をnum[i]、i以下のノードの並べ方をf[i]とすると、
となる。
