Space Elevator (UVa Live Archive Asia - 2008 Taipei(Taiwan))
問題
右方向にr個、左方向にq個止まる候補の箇所がある。各箇所はxiの場所にあり時間t1ｎそこに行くとmax(0, pi-t)の利益を1度だけ得る。利益の最大値を求めよ。
解法
dp[lr][left][right][t]でDPする。lrは左端、右端のどちらにいるか、leftは左側をどこまで行ったか、rightは右端、tは現在の時間を表す。これでDPするとメモリが足りないのでleftを使い回せば解ける。
Friend Numbers (UVa Live Archive Latin America - Mexico and Central America 2007)
問題
Nに含まれる桁の数値を全て含む数値をFriend Numbersと呼ぶ。範囲[A,B]の中でK番目のFriend Numbersを求めよ。
1
解法
dp[上界が存在する][下界が存在する][使った数値][何桁目]を状態にしたO(2*2*2^10*100*10)のdp。Aの桁数がBの桁数よりも小さい場合はleading 0にする。Nに0が含まれるとか、leading 0の際に0を使ったとみなさない事とかに注意。
The Game (UVa Live Archive Europe Southwestern 2008)
問題
シンプルなゲームをするので自分が何点差で勝つか求めよ。
1<=mugの数<5
石の数の合計<=15
解法
αβ法でやるだけ。
注意点とか細かいルールは以下のとおり。
- swapのターゲットは最後に石を入れたmugのみ
- 4ターン分のswapのカウンタはそのmugについて発生し自分と相手で共通
- swapをやるやらないは選択できるが、add turnとbowlへの石の投入は強制的に発生する
- swapとbowlへの石の投入で使うmugの対応が違う
- (bowlへの石の投入の条件である)「before distribution」とはmugから石を取り出す前のこと
- add turnや相手がいきなりパスした場合はswapのカウンタは減らない
- 相手が先手
First Knight (UVa Live Archive Europe Southwestern 2008)
問題
m*nのグリッドがある。各マスで上下左右に移動する確率を与えるので、(1,1)から(m,n)まで行くのに掛かる時間の期待値を求めよ。
2<=m,n<=40
答えは1000000以下
Wizards (UVa Live Archive Europe Southwestern 2008)
解法
重解を持つ条件はf(x)=0かつf'(x)=0となるxが存在することである。なので、gcd(f(x),f'(x))の次数が2以上になるかどうかを調べれば良い。計算をdoubleでやったら誤差死したっぽいので、mod 1e+9+7で計算した。
The Merchant Guild (UVa Live Archive Europe Southwestern 2008)
問題
長さnのハッシュにn個の値を線形探索で値を入れていく。もしもN-1まで開いてない場合は失敗となる。m個分はどのタイミングでどの箇所に挿入するか分かっている。全ての値を挿入できる、値の挿入の仕方は何通りか？
1<=m<=n<=300
解法
m個分の挿入タイミングは関係ないので、どこに挿入するかだけカウントしておく。次にcalc(depth, rest)を後ろから計算していく。depthは現在の位置で、restは現在までに何個の空きがあったかを表していて、前もって挿入された分はそこに来たタイミングでrestから引いておく。途中でrestが負になったら失敗とみなす。コンビネーションの計算を前処理しておけば、このcalcはメモ化再帰でO(n^3)で計算可能。
Top Secret (UVa Live Archive Europe Southwestern 2008)
問題
円環の中に長さNの数列がある。この数列の各数値に対して自分自身と左側のL倍と右側のR倍を足した数値を新しい数値にするという操作をS回繰り返す。下X桁だけ取り出した最終的な数列を答えよ。
2<=N<=1,000
0<=S<=2^30
0
解法
行列を作ってS乗する。この時、行列は巡回行列になっているので、掛け算をする時に1行目だけ求めて、残りは1行目をずらした物を入れるとO(N^2logS)で計算できる。
