hotpepsiの練習帳

SRM 686

23:12

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

Div1 Easy (300) BracketSequenceDiv1

問題

• ()と[]だけからなる文字列がある
• 0文字以上削除して、1文字以上にする
• きちんと括弧が閉じるのは何通りか求める

方針

• 半分全列挙
• まず左半分と右半分にわける
• 左半分について、残す・削除するをビットで表す
• 残った部分について、1つずつ処理していく
• 括弧の対応関係がおかしければそこで終了
• 一つ前のものに対応していたらひとつ消す
• 消えない場合は、括弧の種類を2ビットで表して(ビットシフトして)蓄積させていく
• 最終的に残った対応関係を記憶する
• 右半分は、文字列と文字を反転させて、左半分と同じ処理をする
• 同じ値同士のものが結合でき、かけたものが組み合わせの数になる
• 合計が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_686/BracketSequenceDiv1.cpp

結果

o-- 136.81pt 119th/283 rating 1488 -> 1533 (+45)

一年ぶりに黄色。

半分全列挙なら解けそうだったので愚直に書いた。この方針だとやるだけといえばやるだけだけど、正しく書けたのは良かった。

http://togetter.com/li/955714