hotpepsiの練習帳

SRM 650

22:00

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

Div1 Easy (250)

問題

• 文字AかBだけからなる文字列がある
• 確定している文字の種類と場所が与えられる(与えられなかった場所の文字は未確定である)
• 隣り合う文字が同じである個数の総数を最小にするとき、可能な場合の数を求める

方針

• 確定している文字について、位置でソートする
• 端から確定した文字については、一意に定まる
• 確定した文字と確定した文字との間については、文字の違いと、距離d(隣なら1)で場合分け
• 同じ文字の間に、奇数個はさまっていたとき(dが偶数)は一意で、偶数個のときはd通りある
• 異なる文字の間に、偶数個はさまっていたとき(dが奇数)は一意で、奇数個のときはd通りある
• 一意でない場合、連続するところを一カ所だけ作るのが最小で、それがd通りになる
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_650/TaroFillingAStringDiv1.cpp

結果

o-- 107.77pts 257th/357 rating 1443 -> 1410 (-33)

agwさんと同室。4回目?

何通りなのかよくわからず時間がかかった。

http://togetter.com/li/784723