hotpepsiの練習帳

TCO 2014 Round 1A

greedy | 00:42

Easy (250) EllysSortingTrimmer

問題

• 文字列を変更する装置がある
• 先頭のN文字をそのまま、途中のL文字をソートして、末尾を削除できる
• 何回でも適用できる
• 適用結果のうちの辞書順最小のものを求める

方針

• 末尾に若い文字が入っている場合、それを先頭にもっていきたい
• なのでまず末尾のL文字をソートする
• 次にひとつ前の位置をソートして末尾を削除
• あとは長さがLになるまで繰り返す
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2014/EllysSortingTrimmer.cpp

Medium (500) EllysScrabble

問題

• 文字列と、移動可能な距離Dが与えられる
• 各文字は、左右どちらか距離Dまで移動可能
• 移動結果のうち辞書順最小を求める

方針

• 先頭から1文字ずつ確定させていく
• 置ける候補のうち辞書順最小のものを見つける
• ただし、D個前の位置にあるものを使っていない場合、それを置く
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/tco_2014/EllysScrabble.cpp

Hard (1000) EllysLamps

問題

• N個のランプとボタンがある
• 各ボタンはトグル動作し、押すとランプがON/OFFする
• ただし、両隣の片方または両方のランプも同時にON/OFFするようなボタンが存在する可能性がある
• ボタンの挙動がワーストケースの場合に、OFFにできないランプの最小値を求める

方針

• YNまたはNYの数を数える
• とサンプル4が合わない
• スイッチがN個連動するという前提でDP書いてみたりとか
• (終了後)
• YYYと並んでいるとき、一つ目と二つ目が連動していて、二つ目と三つ目が連動しているとき、NNNにできないので、+1カウントする、ということらしい
• https://github.com/firewood/topcoder/blob/master/tco_2014/EllysLamps.cpp

結果

oo- 238.44 + 386.42 = 624.86pts 331st/2205 rating 1513 -> 1578 (+65)

毎年の祭りその2到来。

比較的早く解けた。highest更新。

http://togetter.com/li/651699