hotpepsiの練習帳

SRM 573

01:22

Div1 Easy (250) TeamContest

問題

• 3人単位でプログラミングコンテストに参加する
• 各人のスキルが与えられる
• チームの強さは、スキルの最低値と最高値の和である
• ありうる最大の順位を求める

方針

• どういう割り当てをしても、何位以上になるかというのを答える
• 3人ずつ割り当てていく
• 最高の一人と、最低の二人の組み合わせが、自分よりランクが高い場合、答えに+1
• そうでない場合、最低の三人をグループにする
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_573/TeamContest.cpp

Div1 Medium (450) SkiResorts

問題

• スキーリゾートに場所0から場所N-1までのN個の場所がある
• 同じ高さか、より低い場所へのみ移動できる
• 任意の場所を工事して高さを変更できる
• 場所0からスタートして場所N-1に行けるようにするための最小のコストを求める

方針

• Dijkstraらしい
• 最小のコストで工事した場合、既存の高さのどれかに揃えることになる
• どこの場所をどの高さに揃えるか決めて、最小コストの場所からpriority queueで取り出して処理していく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_573/SkiResorts.cpp

結果

o-- 144.66pt 379th/580 rating 1330 -> 1343 (+13)

どうもeasyの「maximum」というのは最高ではなく最低の意味っぽい。わかりづらい。

mediumは典型問題らしいが、高さを削ることだけ考えてしまいだいぶ時間がかかった。