Binary-Search Game

確率を考える際に取りうる方法は主に $2$ つ考えられると思います。 すなわち、上手く漸化式を立ててDPをするか、条件を満たす状態を数え上げて全体で割るか、です。 しかし、本問題ではどちらの方針も難しいと思います。まずは、「勝率の最大化」という条件を上手く言い換えることを考えましょう。

これ以上質問ができなくなった（あるいは、偽物を特定できておりする必要がなくなった）状態を考えます。 一般に、この状態で偽物の可能性のあるコインの枚数を $k$ 枚とすると、

• 一連の質問の結果この状態が生じる確率が $k/N$ （ $N$ 枚のコインは、それぞれ $1/N$ の確率で偽物であるため）
• この状態から宣言をした場合、偽物を的中させられる確率が $1/k$

であることから、「このような状態が生じ、その上で勝利できる確率」は $k$ によらず $1/N$ です。 したがって、最適な質問順とは、偽物のコインが含まれている可能性のある区間をできるだけ多くの区間に識別しうる質問順であり、質問の結果最終的に $s$ 個の区間に識別できる場合のあなたの勝率は単に $s/N$ と求まります。 （問題文中のサンプル $1$ で言えば、質問によりコイン $1,2$ のペアと $3$ 単体のどちらに偽物が含まれるか識別しているため、 $2$ 区間に識別できていることになり、勝率は $2/3$ となります。）

この考察に基づくと、区間と、その区間内で識別可能な区間数を持って、その必要コストを求める区間DPを組むことが可能ですが、この解法の計算量は $O(N^5)$ であり、残念ながらまだ不十分です。 （定数倍が軽いため、C++であれば $N\leq 100$ 程度までなら大丈夫なようですが。）そこで、最適な区間の識別がどのようなものであるかをさらに考えます。

最適な質問順によって、偽物が含まれる区間を $s$ 個区別することができると仮定します。 この時、「①：コイン $1$ から $s$ の中に $1$ 枚偽物が含まれています。問題と同様の条件で、確実に偽物を特定できますか。」という問いの答えは必ずYesになります。 なぜなら、当初考えた最適な質問順で $s$ 個の区間に分割したときに、「仕切り」は $s-1$ 個あるはずですが、そのすべての仕切りは①の特定を実現するための「仕切り」 $s-1$ 個よりも質問コストが低くはならないからです。

【参考図】

したがって、最適な質問順を取った場合、最終的に偽物が含まれる区間は $1,2,3,...,s-1,s$～$N$ という $s$ 個の区間に識別されると固定してよいです。 すると、先ほどの問題①の答えがYesであるような $s$ の上限に対して $s/N$ が本問題の答えです。

問題①については、コイン $i$～$j$ の中に偽物があるとしたとき、偽物を特定するために最低限必要なコストを $dp[i][j]$ とする区間DPにより、区間の分割を全通り試して

• $dp[i][j] = min(max(dp[i][k],dp[k+1][j])+k)$ $(k=i,i+1,...,j-1)$

とすることで解くことが可能です。 （区間を分割したとき、分割した $2$ つの区間でコストが大きい方の必要コストと、その分割をするための質問コストの和が、もとの区間から偽物を特定するコストになります。）

この区間DPを全区間に対して行うと計算量は $O(N^3)$ であり、最後に $dp[1][s]$ を $s=N$ から $s=1$ まで降順に確認し、コストが初めて $M$ 以下になるような $s$ を特定すると答えが求まります。