2014-07-06
TCO 2014 Round 2C
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)
文字の位置を覚えたりしたけど、そんなことよりループの計算量削るべきだった。
撃墜回だったのにもったいなかった。