思路

这道题的目标是计算多个查询结果的平均平均精度（MAP@k）。整个计算过程可以分解为两个主要步骤：

1. 为每个查询计算其平均精度（AP@k）。
2. 将所有查询的 AP@k 值取算术平均，得到最终的 MAP@k。

下面我们详细拆解每一步的计算逻辑。

1. 计算单个查询的 AP@k (Average Precision @ k)

对于给定的一个查询，我们需要根据其返回的文档列表（由 scores 和 labels 表示）来计算 AP@k。

a. 数据预处理：排序

题目定义中提到“已按系统得分从高到低返回文档序列”。然而，输入数据中的 scores 和 labels 列表不一定是排好序的。因此，第一步必须根据 scores 对文档进行降序排序。在排序 scores 的同时，必须保持 labels 与之对应。

例如，如果一个查询的 scores 是 [0.8, 0.9, 0.7]，labels 是 [1, 0, 1]，排序后应该是：

• scores: [0.9, 0.8, 0.7]
• labels: [0, 1, 1]

b. 确定计算参数

• $k$：题目给定的截断位置。
• $R$：该查询的真实相关文档总数。可以通过对排序后的 labels 列表求和得到。
• 截断长度：实际计算时，我们只关心到位置 $k$ 为止的结果。但如果返回的文档总数小于 $k$，则只计算到实际的文档数量。这个有效的截断长度可以表示为 min(k, len(sorted_labels))。

c. 计算 AP@k

AP@k 的计算公式为：

这里有几个关键点：

• $\text{rel}_r$ 是排序后第 $r$ 个文档的相关性标签（0 或 1）。
• $\operatorname{Prec}(r)$ 是到位置 $r$ 为止的精度（Precision），计算公式为：$\operatorname{Prec}(r)$=$\frac{\text{到位置 r 为止相关文档的数量}}{r}$。
• 求和项 $\sum_{r=1}^{k}$($\operatorname{Prec}(r)$ $\times$ $\text{rel}_r$) 暗示我们只在遇到相关文档（即 $\text{rel}_r = 1$）时，才将其位置的精度 $\operatorname{Prec}(r)$ 累加到总和中。
• 分母是 $\min(k, R)$。这处理了两种情况：如果真实相关文档数 $R$ 比截断位置 $k$ 小，那么最多只能找到 $R$ 个相关文档，分母就是 $R$。否则，分母就是 $k$。
• 特殊情况：如果一个查询没有任何相关文档（$R=0$），则规定其 AP@k 为 0。

d. 单个查询的计算流程总结

1. 将 scores 和 labels 配对，并根据 scores 降序排序。

2. 计算真实相关文档总数 $R = \sum \text{labels}$。

3. 如果 $R=0$，此查询的 AP@k 为 0，计算结束。

4. 初始化一个累加器 ap_sum = 0 和一个已发现的相关文档计数器 relevant_count = 0。

5. 遍历排序后结果的前 min(k, len(labels)) 项，索引从 1 到 k'：

   • 如果当前位置 $r$ 的文档是相关的（label == 1）：

     • relevant_count 加 1。
     • 计算当前精度 $\operatorname{Prec}(r)$= $\frac{\text{relevant\_count}}{r}$。
     • 将 $\operatorname{Prec}(r)$ 累加到 ap_sum 中。

6. 计算分母 denominator = min(k, R)。

7. 此查询的 AP@k = ap_sum / denominator。

2. 计算 MAP@k (Mean Average Precision @ k)

这一步非常简单。

1. 创建一个列表，用于存放每个查询计算出的 AP@k 值。
2. 遍历所有查询，按照上述步骤计算每个查询的 AP@k，并存入列表。
3. 对列表中的所有 AP@k 值求平均数，即为最终的 MAP@k。
4. 将结果四舍五入保留 6 位小数。

import json
import sys

def calculate_map_at_k(input_data: dict) -> float:
    """
    计算给定查询集的 MAP@k。

    Args:
        input_data: 包含 'k' 和 'queries' 的字典。

    Returns:
        MAP@k 值。
    """
    k = input_data['k']
    queries = input_data['queries']
    
    if not queries:
        return 0.0

    ap_scores = []

    for query in queries:
        scores = query['scores']
        labels = query['labels']

        # 1. 将 scores 和 labels 配对并按 score 降序排序
        # zip 将分数和标签打包成元组 (score, label)
        # sorted 的 key 使用 lambda 函数指定按元组的第一个元素（即 score）排序
        # reverse=True 表示降序
        sorted_docs = sorted(zip(scores, labels), key=lambda x: x[0], reverse=True)
        
        # 提取排序后的标签列表
        sorted_labels = [label for score, label in sorted_docs]
        
        # 2. 计算该查询的真实相关文档总数 R
        R = sum(labels)

        # 3. 如果 R=0，AP@k 直接为 0
        if R == 0:
            ap_scores.append(0.0)
            continue
            
        # 4. 迭代计算 AP@k 的分子部分
        ap_numerator = 0.0
        relevant_count = 0
        num_retrieved = len(sorted_labels)
        
        # 确定循环的截断位置，不能超过 k 和实际返回的文档数
        cutoff = min(k, num_retrieved)
        
        for r in range(1, cutoff + 1):
            # 列表索引从0开始，所以用 r-1
            label_at_r = sorted_labels[r-1]
            
            if label_at_r == 1:
                relevant_count += 1
                precision_at_r = relevant_count / r
                # 公式中的 rel_r 实际上是作为开关，只有当 rel_r=1 时才累加 Prec(r)
                ap_numerator += precision_at_r
        
        # 5. 计算分母并得到 AP@k
        # 注意题目定义：分母是 min(k, R)，不是 R
        ap_denominator = min(k, R)
        
        ap = ap_numerator / ap_denominator
        ap_scores.append(ap)

    # 6. 计算 MAP@k
    map_at_k = sum(ap_scores) / len(ap_scores)
    
    return map_at_k

if __name__ == '__main__':
    # 从标准输入读取单行 JSON
    input_line = sys.stdin.readline()
    data = json.loads(input_line)
    
    # 计算 MAP@k
    result = calculate_map_at_k(data)
    
    # 按要求格式化输出，四舍五入保留6位小数
    print(f"{result:.6f}")

题目内容

在信息检索与推荐系统中，$MAP@k$ 是衡量检索结果整体质量的经典指标。

请你编写一个确定性评估器：给定若干查询 $(query)$ 的检索结果，计算它们在截断位置 $k$ 处的平均平均精度，四舍五入保留 $6$ 位小数。

1.逐查询 $Average$ $Precision (AP @ k)$

对某一查询，已按系统得分从高到低返回文档序列 $(d_1,..,d_m)$ ，其对应二值相关性 $rel_r∈${$0,1$}( $1$ 表示相关)。

$\mathrm{AP} @ k=\frac{\sum_{r=1}^{k}(\operatorname{Prec}(r) \times \text { rel } r)}{\min (k, R)}, \quad \operatorname{Prec}(r)=\frac{\sum t=1^{r} \mathrm{rel} l_{t}}{r}$

• $R=\sum^m_{r=1}rel_r$ ： 该查询真实相关文档数
• 若 $R=0$ (该查询没有任何相关文档) 规定 $AP @ k=0$
• 当返回结果不足 $k$ 条时，用现有条目长度替代 $k$

2. $MAP$ $@$ $k$

$\mathrm{MAP} @ k=\frac{1}{Q} \sum_{q=1}^{Q} \mathrm{AP} @ k(q)$

其中 $Q$ 为查询总数。

输入描述

单行 JSON：

{
 "k":3,         //截断位置 k(1≤k≤100)
 "queries":[
  {
   "labels":[1,0,1],  //相关性标签1/0，与 scores 等长
   "scores":[0.8,0.9,0.7]// 系统得分,分数越大在处理时排序越靠前
  },
  ...
  ]
}

• $queries$ 数量 $≥1$

• $labels$ 与 $scores$ 长度相等且 $≥1$

• $labels$ 仅含 $0/1;scores$ 为任意实数

输出描述

仅输出一行：

$0.583333$

即 $MAP @ k$，四舍五入保留 $6$ 位小数。

样例1

输入

{"k":3,"queries":[{"labels":[1,0,0],"scores":[0.9,0.8,0.7]},{"labels":[0,1,0],"scores":[0.9,0.8,0.7]}]}

输出

0.750000