nu practice 12/05/31 - 競技プログラミング+αなブログ

ishikadoさんのチームの練習会がVirtual Arenaで開かれていたので勝手に参加させていただいた

UVA 10803 Thunder Mountain

問題

整数座標がn点ある。
各点対に関して、距離が10以下なら直接移動することができる。
ある点からある点に移動する中で最も遠いものの距離を求めよ。
もし移動できない点対があれば、"Send Kurdy"と出力せよ。

制約

解法

各点をノードとするグラフを考える。
全点対に関して距離を計算し10以下ならその距離に応じた重みのついたエッジを張る。
全点対間距離を求め、すべての点対を全探索して最大の距離を求める。
たどり着けないものがあったらSend Kurdy

UVA 10849 Move the bishop

問題

N*Nのチェス盤を考える。
現在のビショップの位置と目標の位置が与えられるので、何ステップの移動で目標の位置までたどり着けるか出力せよ。
たどり着けない場合は"no move"と出力せよ。
ただし、ビショップは４つ斜め方向にいくらでも移動することができる。

制約

1<= クエリの数 <= 100
1<= N <= 10^9
1<= 座標値 <= N

解法

現在の位置を(x1,y1),目標位置を(x2,y2)とする。
x1+y1 != x2+y2 (mod 2)
ならたどり着けない。
(x1,y1) = (x2,y2)
なら0回。
abs(x1-x2) = abs(y1-y2)
なら1回。
そうでなければ2回。
最初0回を見落としていた。

UVA 10816 Travel in Desert

問題

ノード数N、エッジ数Eのグラフが与えられる。
各エッジは距離Dと最高温度Rを持つ。
たどるエッジの最高温度ができるだけ小さくなるように、ノードSからノードTまで行きたい。
もし最高温度が同じになるような経路が複数ある場合、最も距離が短いものを選ぶ。
そのような経路の辿るノード番号の列、その経路の距離、最高温度を出力せよ。

制約

1<=N<=100
1<=E<=10000
20<=R<=50
0

解法

拡張ダイクストラかと思って書いてみたら当然のようにTLE。
各ノードに関して、Sからたどった時の最低最高温度、Tからたどった時の最低最高温度をダイクストラで求める。
これをtemp1[i],temp2[i]とすれば、ノードiまではmax(temp1[i],temp2[i])以下の最高温度でたどり着けばよいことになる。
今度は、距離でダイクストラをするのだが、現在の最高温度を保持しておき、次にたどるノードの許容最高温度が、その最高温度以上のときのみ遷移するようにする。
以上で答えを求められる。
ACR#003のCがほぼ同じ問題だったらしいが出てないので知らない。

UVA 10894 Save Hridoy

問題

"SAVE HRIDOY"という文字列を大きさや向きを変えながら出力する問題。
各文字は最小で5*5文字の'.'と'*'を使って表現する。
与えられるNが正のとき、N倍した文字を横に並べる。
負のとき、-N倍した文字を縦に並べる。
文字と文字の間は'.'を並べるのに注意。
サンプルを見るのが早い。

制約

解法

やるだけだがそこそこ面倒。
最小単位のものを埋め込んでNに応じてうまく出力を変える。

UVA 10898 Combo Deal

問題

I個の商品があり値段が与えられる。
Cタイプのセット販売があり、どの商品を何個含むかと値段が与えられる。
Q個のクエリを処理する。
各クエリは各商品がどれだけ欲しいか与えられるので、それらの商品をちょうど買えるような買い方の最小値段を求めよ。

制約

I<=6
C<=8
Q<=10
クエリで要求される各商品の個数は9以下

解法

I<=6で、クエリで要求される各商品の個数が9以下なので、クエリの種類は10^6個。
メモ化再帰か何かで求めてやれば良い。
計算量はO(10^I*I*C)