AOJ-ICPC 2016.10.14
アジア地区の前日（だった）。
問題
問題概要
省略
解法
DP。
それぞれの種目別に、何回アピールを行うかを分けて考える。
ある種目について、アピールを行う回数を決めておくと、各アイドルに勝てる確率を求めることができる。
これを使うと、1位から3位になる確率をDPで求められる。最下位になる確率は全員に負ける確率である。
種目で
回アピールしたときの期待値が求められたので、各種目についてアピールする回数を全探索すればよい。
問題
問題概要
省略
解法
DP。
各カードを桁別に分けて考える。
桁のカードの右に
桁並べるような場合の数 を求める。
右に置くカードが枚のとき、左に置くことができるカードは
枚である。
この時の場合の数は となる。
この場合の数が求まれば、各カードの各数字が桁目にある時の場合の数が求まるので、これを全て足せばよい。
この時、リーディングゼロとなるようなものも含まれているので、そういったものの合計を求め、引く必要がある。
これは、1桁のカードを1枚減らした後（つまり、最初に置く0のカードを取り除いておく）、上と同じことをやればよい。
