問題一覧 > 通常問題

No.3615 Ge Gusser

レベル : / AI推定難易度 : 1350 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 30
作問者 : kazuppa / テスター : Unbakedbread Tamiji153
お気に入りにしたユーザー ProblemId : 13626 / 自分の提出
問題文最終更新日: 2026-08-06 13:56:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Paken新入生コンday1 (順位表) の他の問題:

Problem Statement

Kazuppa is playing a certain game. The game proceeds as follows.

  • The game has $M$ maps implemented, and $1$ of them is chosen as the answer.

  • In each game, there are $N$ areas that can be visited. The information of area $i$ is represented by a string $S_i$ of length $M$ consisting of o and x. If $S_{i,j}=$ o, the information of area $i$ tells that "the answer may be map $j$", and if $S_{i,j}=$ x, the information of area $i$ tells that "the answer cannot be map $j$". Here, it is guaranteed that the answer is uniquely determined once all $N$ areas have been visited. Also, the player cannot know the information $S_i$ until visiting area $i$.
  • The player starts from any location, moves by choosing various areas, and can answer which map is the answer exactly once. The player becomes happy if the answer is correct, and unhappy if it is wrong.

Kazuppa has decided to play this game with the following strategy.

  • He absolutely does not want to be unhappy, so he does not answer until the answer is uniquely determined. Also, since he is impatient, he answers as soon as the answer is uniquely determined.
  • He does not understand the optimal play of this game, so he starts by choosing $1$ random area, and each time he moves, he randomly chooses $1$ area he has not visited yet and moves there.

Define the score of this game as the number of areas visited (including the starting area). Find the expected value of the score when Kazuppa plays with his strategy.

Constraints

  • $1\leq N\leq 22$
  • $2\leq M\leq 50$
  • $S_i$ is a string of length $M$ consisting of o and x
  • There exists exactly one $j$ such that "$S_{i,j}=$o for every $i$"
  • $N,M$ are integers

Subtasks

This problem has partial scores set by subtasks.

Subtask NamePointsConstraints
Subtask 1100 points$N\leq 6$
Subtask 2100 points$N\leq 18$
Subtask 350 pointsNo additional constraints

Input

$N\ M$
$S_1$
$S_2$
$\vdots$
$S_N$

Output

Print the answer on one line.

Your answer is judged as correct if the absolute or relative error from the true value is at most $10^{-6}$.

Sample

Sample 1
Input
2 2
oo
ox
Output
1.5

If he starts from map $1$, the answer is not unique at that point, so he moves to map $2$. Here the answer is uniquely determined, so the score is $2$.

If he starts from map $2$, the answer is uniquely determined at this point, so the score is $1$.

Therefore, the answer is $\frac{1+2}{2}=1.5$.

Sample 2
Input
3 3
xox
xox
xox
Output
1

Sample 3
Input
5 5
ooxoo
xoooo
oxooo
oooox
ooooo
Output
4.8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。