hotpepsiの練習帳

SRM 586

20:18

Div2 Easy (250) TeamsSelection

問題

• メンバーを2チームにふりわける
• それぞれのキャプテンがメンバーの番号の優先順位を持っている
• 1人ずつ割り当てたときのチーム割りを求める

方針

• 貪欲に割り当て
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_586/TeamsSelection.cpp

Div2 Medium (500) PiecewiseLinearFunctionDiv2

問題

• 直線からなる関数が与えられる
• 座標に対する解の個数を求める

方針

• 連続して同じ座標のものは無限に解があるので覚えておく
• 座標が等しいものだけカウントして、開区間だけカウントする
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_586/PiecewiseLinearFunctionDiv2.cpp

Div2 Hard (1000) StringWeightDiv2

問題

• 26文字のどれかからなる文字列Sがある
• ある文字についてのスコアは、最も右のものと最も左のものの出現位置の差の絶対値である
• 文字列Sのスコアは、文字のスコアの合計である
• 文字列Sの長さLが与えられる
• その長さにおいて最小のスコアの文字列が何通りあるかを求める

方針

• 異なる文字を使ったほうがスコアが小さい
• それぞれの文字は連続していること
• 長さが26以下のときは、1文字ずつ使う場合が最小
• 長さ1のとき26通り、長さ2のとき26×25通り...長さLのとき26_P_L = (26!)÷((26-L)!)
• 長さが27以上のとき、26種類全て使う
• 26を超えたぶんをどこかに分配する
• 26箇所に0個以上分配する重複組み合わせ
• 26_H_(L-26) = (26+L-26-1)_C_(26-1) = (L-1)_C_25
• それぞれの文字種の並べ方は26!
• つまり26!×(L-1)_C_25
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_586/StringWeightDiv2.cpp

結果

ooo 196.67 + 421.80 + 568.00 = 1186.47pt 23rd/1005 rating 1191 -> 1280 (+89)

easyの優先度の見方が間違っていて時間がかかった。

hardも通って良かった。最高順位。