Problem E : Marathon †問題概要 †駅伝大会が行われる。ルールは以下の通り。（とりあえず原文のままで） l Each team consists of exactly N runners. l The winner is the team that runs the longest distance for D days. l For each day, exactly one runner from each team should run. l If a team member runs on a particular day, that team member should run for the entire day. That is, runner exchanges are only possible at the beginning of each day. l Each of the N runners on a team should run for at least one day, but at most three days. l If a runner participates in running for a day or for a sequence of days, and then, is switched with another runner, he/she cannot participate in the marathon again. チームメンバーそれぞれについて a : 一日で走れる距離 b : 二日で走れる距離（合計） c : 三日で走れる距離（合計） が与えられます。このチームがこの駅伝で走れる最長距離を出力せよ。という問題です。 与えられる値はすべて整数。0 < N <= 50,0 < D <=150,a <= b <= c。入力が不正、またはルール上大会に出場できないならば-1を出力します。 難易度 †普通。 解法 †（ｎ日目に走れる距離をLnとします） 参加者をmax{L2,(L2+L3)/2} をキーとして大きい順にソートし、順に余計に走らせるようにすればO.K.。L2 > (L2 + L3)/2 ならばとりあえず二日間だけ。L2 < (L2 + L3)/2 なら三日間。 とりあえず二日間走ることが決まった人については、L3をキーにして参加者のソートされた列に再度挿入し、再度選択されたら３日間走ることにします。 （このやり方の場合、）最後の一日は別処理が必要。 議論・その他 †もしある人が二日以上走った場合 一日目に走れる距離 > 二日目に走れる距離 > 三日目に走れる距離 を仮定できると、問題が簡単になりますが、問題文を読む限りそうでは無いようです。 ファイルを添付する † |
