Regionals 2010 :: Europe - Northwestern
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=397
4944 - Fair Division
問題
金額pをn人で払う。それぞれの人について出せる最大金額a[i]が与えられる。
払う金額の差の最大が最小になるように、n人が払う金額を決める。
ただし、そのような払い方が複数ある場合は、
金額の差の2番目に大きいものが最小になるように、それでも同じなら・・・
それでも同じなら最大金額が大きい人ほど多く払い、それでも同じならリストで先にくる人が多く払う。
制約
1<=p<=1000000
2<=n<=100
1<=a[i]<=1000000
解法
まずIMPOSSIBLEになるのは最大金額の合計金額がpに満たないときのみ。
解の順位付けが難しい感じがするが、実はそんなでもない。
とりあえず入力を、「最大金額が大きい順→リストでの出現位置が小さい順」でソート
現在のリストの中で、最大金額が最小のものだけ皆から徴収することを考える。
徴収する分だけリストの中の人の最大金額を減らす。
最大金額が0になった人はリストから外す。
またpも皆から徴収した分だけ減らす。
これを繰り返すことで題意の解を求めることが出来る。
もし最小のものを皆から徴収するとpがマイナスになってしまうようなときは、リストの前の人から1ずつ徴収していけば良い。
4945 - Free Goodies
問題
n個のgoodiesをPetraとJanで順番に取っていくことを考える。
それぞれのgoodiesについて、Petraにとっての価値P[i]とJanにとっての価値J[i]がわかっている。
Petraは今残っているgoodiesのうち、自分に取って最大価値のものを取る。
最大価値が同じものが複数ある場合はJanにとっての価値が低い方を取る。
Janは（Petraの戦略を知った上で）最終的に自分が得られる価値を最大にするようにgoodiesを取る。
そのようになる選択肢が複数あった場合はPetraにとっての価値が低い方を取る。
全てを取り終わるときPetraとJanは合計でどれだけの価値を得ることが出来るか求めよ。
制約
1<=n<=1000
0 <= P[i], J[i] <= 1000
解法
Petraは単純だが、Janが厄介。
Janが何を取るかはDPで求めるしか無い。
Petraにとっての優先順位に従ってgoodiesをソートする。
するとPetraは左から残っているものをとっていくことになり問題が少し単純になる。
dp[i][j] = Janがi以降からモノを取るときの最大。ただしPetraはj回、番号i以前のgoodiesを取る。
というようなDPを考えた。メモ化再帰で実装した。
dp[i][0] = max(dp[i+1][1], J[i]+dp[i+2][0])
dp[i][j] = max(dp[i+1][j+1], J[i]+dp[i+1][j-1]) (j>=1)
となる。
答えはdp[0][0]
maxの中の1つ目はi番目のgoodiesを取らないときに対応し、2つ目は取るときに対応する。
Janの答えを求めたら、経路復元してPetraの答えも求める。
4946 - High Score
問題
ゲームで自分の名前を入れることを考える。
カーソルは左右に動け、左端から左に行くと右端に行き、逆も成り立つ。
AからBは1ステップでいけ、ZからAやAからZも1ステップで行ける。AからCは2ステップ。
最初は全てAで埋まっており、カーソルは左端にある。
入力するべき名前sが与えられるので、最短ステップ数を求めよ。
制約
1<=|s|<=1000
4947 - Hill Driving
4948 - Rankings
問題
nチームの去年のランキングがt[i]で与えられる。
更に、今年のランキングで去年と順位の関係が入れ替わったペア(a[i],b[i])がm個与えられる。
これを満たすランキングがあるときはそれを出力し、無いときはIMPOSSIBLEを出力せよ。
ただし、そのランクに複数のチームがありうる場合は対応する部分に?を出力する。
制約
2<=n<=500
1<=t[i]<=n
0<=m<=25000
1<=a[i]
解法
実は、?を出力するべきことはない。
n*(n-1)/2の不等式ができるので、それに対応するグラフを作って最短距離を求める問題に帰着すれば解ける。
負の閉路が存在すればIMPOSSIBLE
ただし、この場合の不等式は全てX>=Y+1の形なので、トポロジカルソートでも解ける。
4949 - Risk
問題
グラフと、各ノードにいる味方の兵士の数a[i]が与えられる。
兵隊の数が0のノードは敵の領地である。
味方の領地内で、兵隊を移動させることを考える。
敵の領地と隣接するノード（境界）の兵隊の数の最小の最大値を求めよ。
ただし、兵隊は隣接するノードにしか移動させることは出来ず、各味方領地は最低1人は兵士がいなければいけない。
制約
ノードの数 1<=n<=100
0<=a[i]<=100
グラフは隣接行列で与えられる
解法
ソース、シンク、味方領地を２つに分けたもの（IN(i),OUT(i)）をノードとして適切に辺を張り、最大流を流す。
OUT(i)からシンクへは、境界でなければ1、境界ならばmを容量とした辺を張る。
OUT(i)からシンクへ全ての辺がいっぱいになるまで流すことができたら、境界にm人配置することが出来ることを意味する。
このmで二分探索すればいい。
4950 - Selling Land
問題
n*mのマップが与えられる。
.が芝生、#が沼地を表す。
各芝生について、そこを右下とする芝生だけからなる長方形のうち周りの長さが最大のものを選ぶ。
このとき、ある周りの長さについてその長さが何回出現するかの対応を出力せよ。
制約
1<=n,m<=1000
解法
各行について、蟻本4-4にあるスタックを利用した方法を応用して各区画の解を求める。
注目区画を含み上に続く芝生の数をup[j]とする。
すると各区画における解は、
- 高さup[j]の長方形の周りの長さ
- up[k]
のうち大きな方になる。
4951 - Stock Prices
問題
株価の計算をする。
- ask price とは、株を売りたいと思う値段の最小値
- bid price とは、株を買いたいと思う値段の最小値
- stock price とは、最後に取引されたときの値段
売りと買いの注文が与えられるので、それぞれの注文が処理された後の ask price, bid price, stock price をそれぞれ出力せよ。
ただし、買いの金額が売りの金額以上になっていたときはただちに取引が行われる。
買いの金額が売りの金額以上になっている組み合わせが複数あったときは、より買い値が大きい方、売り値が小さい方から取引が行われる。
制約
注文の数 1<=n<=1000
１つの注文において売買する株の数 1<=x<=1000
希望の値段 1<=y<=1000
解法
英語さえ読めればnが1000なのでいろいろと解き方はあると思う。
売る注文と買う注文を保持するpriority_queueを２つ使う方法を使った。
4952 - Telephone Network
4953 - Wormly
問題
足の数がL、胴体の長さがbである虫が長さnの橋を渡る。
虫が出来る１ステップは
- １つの足を前に動かす（2単位以上動かしてもいい）。ただし、胴体より前に行ってはいけないし、前の足を超えてはいけない
- 胴体を１単位前に動かす。ただし足の位置が胴体より後ろにいってはいけない。
橋は壊れている部分があり、0と1で表される。0は壊れている箇所を表し、1は壊れていない箇所を表す。
最初虫は、胴体が橋の左端に位置し、足も橋の左端に位置する。
虫は、胴体が橋の右端に達し、足も橋の右端に位置するまで進む。
橋の左端L個と、右端L個の部分では橋は壊れていない。
このとき橋を渡る最小ステップ数を求めよ。
ただし渡れないときはIMPOSSIBLEを出力せよ。
制約
1<=L<=b<=n<=1000000
解法
しゃくとり法で解いた。ただ、二分探索を使った O(n log(n)) でも間にあうらしい。
最小ステップは、出来る限り足を前に出し、出来る限り胴体を前に動かすことを繰り返せば達成できる。
足は一番先頭の位置と最後の位置を覚えておけばいい。
しゃくとり法を使って、胴体の範囲内で壊れてない橋の箇所の個数がLとなるような範囲のうち一番前のものを求める。
