hotpepsiの練習帳

SRM 695

19:39

https://competitiveprogramming.info/topcoder/srm/round/16767/div/1

Div1 Easy (300) BearPasswordLexic

問題

• 文字aまたはbだけからなるN文字のパスワードSを作る
• Sの同じ文字が連続する部分(aが連続、またはbが連続)を取り出したものを部分文字列とする
• 異なる位置からはじまる部分文字列は異なるものとする
• 長さがi+1の部分文字列の個数が配列x[i]として与えられる
• 条件を満たす文字列のうち辞書順最小のものを求める

方針

• まず構築できるかどうかについて考える
• 長さXの部分文字列が1つあると、その部分には長さX-1の部分文字列が2つある
• 一番長いものから調べていき、短い部分文字列から、長いものによる個数を減らしていき、ちょうどその長さのものがいくつあるか求める
• 途中で個数が負になったりしたら構築不能
• 長さの合計がNにならなかったら構築不能
• 長さの配列が求まったら、構築していく
• aが連続＋bが連続＋aが連続...という形をしている
• 辞書順最小にするには、最初のaをなるべく長く、次のbをなるべく短く、というように構築する
• 残り個数が0になるまでaとbを交互に追加していく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_695/BearPasswordLexic.cpp

o-- 138.96pt 138th/379 rating 1500 -> 1548 (+48)

300が普通に解けてなかなか良い感じだった。

http://togetter.com/li/1002027