概要

グラフ上の始点 \(S\) から終点 \(T\) への全ての単純パス（同じ頂点を2回通らないパス）について、訪問スポットの満足度の合計（スコア）の平均値を求める問題です。ビットマスクDPを用いて、全パスのスコア総和とパス数を効率的に計算します。

考察

素朴なアプローチとその問題点

最も直感的な方法は、\(S\) から \(T\) への単純パスを全列挙し、各パスのスコアを計算して平均を取ることです。しかし、\(N\) 頂点の完全グラフの場合、単純パスの数は最悪で \((N-2)!\) 程度になり、\(N = 18\) では \(16! \approx 2 \times 10^{13}\) にもなるため、全列挙は到底間に合いません。

重要な気づき：状態の圧縮

単純パスにおいて重要なのは「今どの頂点にいるか」と「どの頂点をすでに訪問したか」です。訪問済みの頂点集合をビットマスク（\(N\) ビットの整数）で表せば、状態数は高々 \(2^N \times N\) です。\(N = 18\) の場合でも \(2^{18} \times 18 \approx 470\) 万程度であり、十分扱えます。

スコアの総和を直接管理する工夫

パスの「本数」だけでなく「スコアの総和」も同時にDPで管理します。ある状態 \((mask, cur)\) に到達するパスが \(cnt\) 本あり、それらのスコアの合計が \(scr\) であるとき、次の頂点 \(v\) に移動すると：

• 新しいパス数：\(cnt\) 本がそのまま引き継がれる
• 新しいスコア総和：\(scr + cnt \times cost[v]\)（\(cnt\) 本の各パスにスポット \(v\) の満足度が加算される）

アルゴリズム

1. 状態定義: \(dp\_count[(mask, cur)]\) = 訪問済み集合が \(mask\)、現在地が \(cur\) であるようなパスの本数。\(dp\_score[(mask, cur)]\) = そのようなパス全てのスコア（途中までの累積満足度）の総和。

2. 初期状態: \(mask = \{S\}\)（\(S\) のビットだけ立てた集合）、\(cur = S\) のとき、\(dp\_count = 1\)、\(dp\_score = c_S\)。

3. 遷移: \(mask\) を小さい方から順に処理する。状態 \((mask, cur)\) から、\(cur\) の隣接頂点 \(v\) のうち \(mask\) に含まれないものへ遷移する。

   • \(new\_mask = mask \cup \{v\}\)
   • \(dp\_count[(new\_mask, v)]\) += \(cnt\)
   • \(dp\_score[(new\_mask, v)]\) += \(scr + cnt \times cost[v]\)

4. 終了条件: \(cur = T\) に到達した状態はパスの完成を意味するので、そこからさらに遷移しない。到達時のパス数とスコア総和を集計する。

5. 答え: 集計した全パスのスコア総和 ÷ 全パスの本数。

具体例

\(S=1, T=3\) で \(1 - 2 - 3\) と \(1 - 3\) の2本のパスがある場合： - パス \(1 \to 3\): スコア = \(c_1 + c_3\) - パス \(1 \to 2 \to 3\): スコア = \(c_1 + c_2 + c_3\) - 平均 = \(\frac{(c_1 + c_3) + (c_1 + c_2 + c_3)}{2}\)

計算量

• 時間計算量: \(O(2^N \times N^2)\)（各状態 \(2^N \times N\) に対し、隣接頂点の探索が最大 \(O(N)\)）
• 空間計算量: \(O(2^N \times N)\)（到達可能な状態のみ辞書で保持）

実装のポイント

• ビット演算で隣接頂点を高速列挙: adj[cur] & ~mask で未訪問の隣接頂点のビットマスクを取得し、最下位ビットから順に取り出す v = (neighbors & -neighbors).bit_length() - 1 テクニックを使う。

• \(cur = T\) で遷移を打ち切る: 終点に到達したパスをさらに延長しないことで、\(S\) から \(T\) への単純パスのみを正しく数え上げる。

• 辞書による疎な状態管理: 到達不可能な状態が多い場合にメモリと時間を節約できる。

• 0-indexed への変換: 内部ではビットマスク操作の都合上、頂点番号を \(0, 1, \ldots, N-1\) に変換して処理する。

  ソースコード

import sys
from functools import lru_cache

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    c = [0] * (N + 1)
    for i in range(1, N + 1):
        c[i] = int(input_data[idx]); idx += 1
    
    # Adjacency as bitmask (0-indexed internally)
    adj = [0] * N
    for j in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u - 1] |= (1 << (v - 1))
        adj[v - 1] |= (1 << (u - 1))
    
    # Convert S, T to 0-indexed
    S -= 1
    T -= 1
    
    # dp[visited_mask][current_node] = (count_of_paths, sum_of_scores)
    # We use memoization with bitmask DP
    # visited_mask includes all visited nodes including current
    
    # We'll do iterative DP or recursive with lru_cache
    # State: (mask, cur) where mask is the set of visited nodes, cur is current position
    # Transition: move to neighbor not in mask
    
    # If cur == T, we have a complete path (don't extend further)
    
    cost = [0] * N
    for i in range(N):
        cost[i] = c[i + 1]
    
    # dp[mask][cur] = (number_of_paths_from_cur_to_T, total_score_sum_of_remaining_path_including_cur)
    # Actually, let's think forward:
    # Let's accumulate from S.
    # State: (mask, cur) - mask is visited set, cur is where we are
    # For each state, count = number of simple paths from cur to T using only unvisited nodes
    # score_sum = sum of scores of all such paths (where score includes all nodes from S to T)
    
    # Better approach: enumerate paths from S to T
    # dp[mask][cur]: number of paths that visited exactly 'mask' nodes and ended at 'cur'
    #                and the total accumulated score sum across all such paths
    
    # Initialize: mask = {S}, cur = S, count=1, score_sum = cost[S]
    # Transition: from (mask, cur), go to neighbor v not in mask
    #   new_mask = mask | (1 << v)
    #   new_count += count
    #   new_score_sum += score_sum + count * cost[v]  (each of the 'count' paths gains cost[v])
    
    # Answer: sum over all masks where T is in mask, of dp[mask][T].score_sum / dp[mask][T].count total
    # Actually: total_score = sum of score_sum for all (mask, T), total_count = sum of count for all (mask, T)
    # answer = total_score / total_count
    
    # Use dictionary or array. With N<=18, mask up to 2^18 = 262144, nodes up to 18
    # Total states: 2^18 * 18 ~ 4.7M, manageable
    
    size = 1 << N
    # Use arrays: dp_count[mask][cur], dp_score[mask][cur]
    # Too much memory for full array? 262144 * 18 = ~4.7M entries, fine with dicts or arrays
    
    # Let's use dictionaries keyed by (mask, cur) for efficiency since many states are unreachable
    
    dp_count = {}
    dp_score = {}
    
    init_mask = 1 << S
    dp_count[(init_mask, S)] = 1
    dp_score[(init_mask, S)] = cost[S]
    
    total_count = 0
    total_score = 0
    
    # BFS/iteration in order of popcount of mask
    from collections import deque
    queue = deque()
    queue.append((init_mask, S))
    
    # We need to process each state once. Use a set or process by mask order.
    # Better: iterate over masks in order (increasing), then nodes.
    
    # Rebuild with iteration over masks
    for mask in range(size):
        for cur in range(N):
            if (mask, cur) not in dp_count:
                continue
            cnt = dp_count[(mask, cur)]
            scr = dp_score[(mask, cur)]
            
            if cur == T:
                total_count += cnt
                total_score += scr
                continue  # Don't extend past T
            
            neighbors = adj[cur] & ~mask
            while neighbors:
                v = (neighbors & -neighbors).bit_length() - 1
                neighbors &= neighbors - 1
                new_mask = mask | (1 << v)
                key = (new_mask, v)
                if key in dp_count:
                    dp_count[key] += cnt
                    dp_score[key] += scr + cnt * cost[v]
                else:
                    dp_count[key] = cnt
                    dp_score[key] = scr + cnt * cost[v]
    
    print(f"{total_score / total_count:.10f}")

main()

---

この解説は claude4.6opus-thinking によって生成されました。