Regionals 2010 :: North America - Rocky Mountain
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=408
4883 - Ropes
問題
休憩所があるような崖を登って降りる。休憩所の高さの間隔が与えられる。
登るときは、各休憩所ごとに、先頭の人はロープを持ってのぼり、後の人は前の人が登りきったら自分にロープを装着し登る。
降りるときは、一気に降りる。このときロープの真ん中を崖の上に付け、それを使って降りるので、崖の高さの２倍のロープが必要である。
50, 60, 70mのロープを使うとき、それぞれ最大で何人登って降りることが出来るか求めよ。
解法
ロープの長さをxとする。
登ることが出来る人数は、 floor(max(休憩所の間隔)/x)+1
降りるのは人数に関係なく、 x>=sum(休憩所の間隔)*2 なら降りることが出来、そうでなければ降りることができない。
降りることができないなら答えは0となり、降りることが出来るなら登ることが出来る人数がそのまま答えとなる。
4884 - Chain Code
問題
必ず最初に戻ってくるチェーンコードが与えられるので、そのチェーンコードが囲む格子点の個数（境界上も含む）を求めよ。
解法
ピックの定理。
4885 - Task
問題
タスクの時間関係が与えられるので、それを満たすようなものがあるときはその解の一つ、ないときはImpossible.を表示せよ。ただし全てのタスクを行う時間は１以上である。
解法
条件は２変数間の1次不等式になる。このとき蟻本にもあるように最短路問題に帰着することが出来る。sinkを作り、全てのノードにコスト0のエッジを張る。
負の閉路があるとき、その時に限り解がない。
4886 - Page Count
問題
ページ数と、10-15,25-28のように印刷するページが指定されるので、印刷されるページの総数を求めよ。
解法
ページ数とページ指定が少ないのでテーブルを作って計算する。
4887 - Soccer
問題
nチームが計m回試合をする。そのうち最大12回の試合はまだ勝負が決まってない。
試合結果の情報が入力で与えられるので、それぞれのチームについて、最大何位で最低何位になるかを求めよ。た
だし、試合に勝ったら勝ち点3、引き分けなら勝ち点1、負けなら勝ち点0得られる。
解法
勝ち負けが決まっていないAとBとの試合について、Aが勝つ場合、Bが勝つ場合、引き分けの場合をDFSで全て試す。(3^12)
それぞれでランキングを作って最高順位と最低順位を更新していく。(3^12*20*log(20))
4888 - Railroad
問題
２つの数列A,Bと、A,Bの長さを足したものと等しい長さの数列Cが与えられるので、A,Bそれぞれの各要素の順番を変えずにマージするとき、Cを作れるかどうかを判定せよ。
解法
DP[i][j] = Aをi番目まで、Bをj番目まで使うときCの(i+j)番目までを作れるかどうか
4889 - Post Office
問題
３つの数字が与えられる。
それを大きい順にlength, height, thicknessとする。これをletter, packet, parcelに分類する。
全ては、length>=125, height>=90, thickness>=0.25を満たす。
letterはlength<=290, height<=155, thickness<=7
packetはlength<=380, height<=300, thickness<=50
parcelはlength+2*(height+thickness)<=2100
を満たす。
３つの数字が与えられたとき上のどれになるか判定せよ。
どれにもあてはまらないなら、"not mailable"
解法
英語読解
