hotpepsiの練習帳

TCO 2014 Round 2C

16:52

Easy (300)

問題

• 文字列Sが与えられる
• 位置iからjまでを逆転させる
• 辞書順最小になるiとjを求める

方針

• SをソートしたものをXとすると、S==Xなら何もしなくていい
• 先頭に近いほど辞書順に影響する
• 1文字ずつソートしたものと見比べていって、最初に異なるところが反転開始位置i
• jは全て試せばよい
• Failed System Test
• break忘れてた
• 気づいていたけど手元で1秒くらいだったので再提出しなかったが、ワーストケースではもっとかかっていた
• https://github.com/firewood/topcoder/blob/master/tco_2014/SubstringReversal.cpp

結果

x-- 0pts 1539 -> 1477 (-62)

文字の位置を覚えたりしたけど、そんなことよりループの計算量削るべきだった。

撃墜回だったのにもったいなかった。

http://togetter.com/li/689068