Hatena::Grouptopcoder

hotpepsiの練習帳

2014-07-06

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

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20140706