hotpepsiの練習帳

SRM 671

00:44

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

Div1 Easy (300) BearCries

問題

• 1個以上の泣きの顔文字;_;をネットワーク上に送信する
• アンダースコアは1つ以上なら何個でもよい
• 複数の顔文字が混ざって1つの文字列として送信される
• 1つの顔文字内の文字の順番は入れ替わらない
• 最終的に送信されるmessageが何通りに復元できるかを求める

方針

• (終了後)
• kojingharangさんのを写経
• dp[N文字目][開始;の個数][;_の個数]
• 1文字ずつ見ていき、;だったら開始;にするか;_を閉じる。閉じる場合、;_の個数だけ開始位置が存在する
• _だったら既存の;_につなげるか、開始;を;_にする。つなげる場合、どこにつなげるか個数分存在する。開始する場合も、どの;から開始するか個数分存在する。
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_671/BearCries.cpp

結果

--- 0pt 300th/556 rating 1295 -> 1274 (-21)

面白い問題。半年後には解き方忘れてそう。

http://togetter.com/li/886966