水色プログラミング

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

SoundHound Inc. Programming Contest 2018 -Masters Tournament- : C - Ordinary Beauty

 

問題

C - Ordinary Beauty

数列の美しさを隣り合う2数の差が d である組の数と定義したとき、1 ~ N までの数で長さ M のすべての数列の美しさの平均を求める問題。

 

解法

解説 PDF からどうやら隣り合う2数という小さいところから考えていくらしいとヒントを得た。考えてみると、隣り合う2数が「美しい」となるのは d が 0 か 1 かで場合分けをすると単純な式でその確率が求められる。この2数の組が長さ m の数列中には当然 m - 1 個ありうるので、その数列がどれだけの「美しさ」であるのかという期待値的なものが出てくるのでそれをそのまま答えにしていい(n^m 個倍にしても平均をとるときに n^m で割るだけなので)。

 

解答

Submission #2833546 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

凄いシンプルになった。

f:id:babcs2035:20180713160040p:plain