水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

Summer Festival Contest 2018 (Division 2):B - 太鼓の名人 (Taiko Expert)

問題

B - 太鼓の名人 (Taiko Expert)

何回か D が続き,その後 K が何回か続く長さ N の文字列がある.この文字列が壊れてしまい,一部は ? となってしまっている.このとき,何通り元の文字列は考えられるか,という問題.

解法

一番右にある D と一番左にある K の位置が D < K となっていなければ0通り.

D も K も現れていたら K - D 通り(D と K の境目が,D と K の間にある ? の個数だけ考えられるから).もし,片方が現れていなければ,K + 1 通りや N - D 通りとなる.もし,両方とも現れていない,すなわち,全部 ? であれば N + 1 通りとなる.

場合分けが少し多い.

解答

Submission #3069764 - Summer Festival Contest 2018 (Division 2)

怒涛の 11 WA をしました.

f:id:babcs2035:20180825165311p:plain

gist.github.com