hotpepsiの練習帳

SRM 648

21:41

Div1 Easy (250) AB

問題

• 'A'か'B'だけからなる長さNの文字列Sについて考える
• i<jで位置iが'A'、位置jが'B'の個数がK個のものを求める</li>

方針

• Aより右にあるBの個数がスコア
• Aの個数をa個、Bの個数をb個として、a×bが最大値
• aとbを全て試す
• a×bがK以上になるとき、a-1個のAは全てのBの前で、残りひとつのAの位置でスコアが調整できる
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_648/AB.cpp

結果

o-- 127.75pts 379th/528 rating 1460 -> 1424 (-36)

堅実にratingが削れた。

http://togetter.com/li/777753