hotpepsiの練習帳

SRM 518 Div2

01:03

Easy (250) TwiceString

• 同じ文字列が2回出てくる最短のものを求める。
• 普通に全試行。
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_518/TwiceString.cpp

Medium (500) LargestSubsequence

• 部分文字列のうち辞書順最大のものを求める。
• 前から見て全試行したが、後ろから見るとO(n)だったらしい。
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_518/LargestSubsequence.cpp

Hard (1000)

• N枚のコインがあり全て表になっている。
• Kターン後に表になっている枚数の期待値を求める。
• 最初から1ターンずつ計算したらサンプルと合ったので提出
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_518/CoinReversing.cpp

結果

ooo 241.27+305.88+493.62=1040.77 rating 1100 -> 1154

Easyは全く悩む所がなかったが、テストケースを手で書いていたため5分かかった。

Mediumをきれいに書き直してたら20分くらいかかってしまったが、変なバグを埋め込むよりはよかった。

初めてHard通った。しかし簡単な回かつ遅かったためrate上昇はそこそこ。