hotpepsiの練習帳

SRM 597

greedy | 19:57

Div1 Easy (250) LittleElephantAndString

問題

• 同じ長さの文字列AとBがある
• Aの任意の文字を先頭に移動できる
• AとBを等しくするための手数を求める(不可能なら-1)

方針

• ソートして一致しない場合は不可能
• 例としてA=edcba,B=abcdeで考える
• 先頭への移動しかできないので、末尾の文字eより後ろの文字は全て移動する必要がある
• dについて考えると、e以外の文字は全て移動する必要がある
• と考えていくと、末尾から、移動不要なものをe->d->cと一つずつ見つけ、それ以外のものは全て移動すればよい
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_597/LittleElephantAndString.cpp

Div2 Easy (250) LittleElephantAndDouble

問題

• 数値の配列が与えられる
• どれかの要素を2倍にできる
• 全ての要素を等しくできるかどうかを答える

方針

• 任意の2要素が2の累乗倍になっているかどうかを調べる
• 先頭の要素と、それ以外の全ての要素について確認できればよい
• 小さいほうを2倍して一致するかどうか見る
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_597/LittleElephantAndDouble.cpp

結果

o-- +1 198.95 + 50 = 248.95pt 69th/740 rating 1236 -> 1400 (+164)

初の二桁順位。