結果

問題 No.3615 Ge Gusser
コンテスト
ユーザー kidodesu
提出日時 2026-08-06 16:39:45
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 180 ms / 3,000 ms
+ 479µs
コード長 936 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,367 ms
コンパイル使用メモリ 95,720 KB
実行使用メモリ 148,864 KB
最終ジャッジ日時 2026-08-06 16:39:54
合計ジャッジ時間 5,451 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 3
小課題1 40 % AC * 8
小課題2 40 % AC * 15
小課題3 20 % AC * 27
合計 2.5 * 100% = 250 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    h, w = list(map(int, input().split()))
    S = [input() for _ in range(h)]
    for x in range(w):
        for y in range(h):
            if S[y][x] == "x":
                break
        else:
            mx = x
    A = [0] * h
    for y in range(h):
        for x in range(w):
            nx = x
            if x == mx:
                continue
            elif mx < x:
                nx -= 1
            if S[y][x] == "x":
                A[y] |= 1<<nx
    dp = [0] * (1<<h)
    ep = [0] * (1<<h)
    for y in range(h):
        dp[1<<y] = A[y]
    X = [0] * (h+1)
    X[0] = 1
    for y in range(1, h+1):
        X[y] = X[y-1]*(h+1-y)//y
    o = 1<<60
    ans = o
    mask = (1<<w-1)-1
    for bit in range(1, 1<<h):
        mbit = bit & (bit-1)
        dp[bit] = dp[mbit] | dp[mbit^bit]
        ep[bit] = ep[bit>>1] + (bit&1)
        if dp[bit] < mask:
            ans += o//X[ep[bit]]
    return ans/o

print(main())
0