解题思路

本题的核心是在资源约束下最大化注意力信息总量。问题可以分解为以下几个步骤进行求解：

首先需要对所有特征向量进行RMSNorm归一化处理。对于每个d维特征向量，计算其均方根值，然后将向量的每个分量除以该均方根值。这一步保证了后续注意力得分计算的标准化基础。

接着计算所有位置对之间的注意力得分。对于任意两个位置i和j（其中i<j），使用归一化后的向量进行缩放点积运算，得到注意力得分 $A_{ij}$ ，并计算其平方值 $A_{ij}^2$ 。由于最终目标函数中使用的是平方值，因此可以直接存储平方值以便后续使用。

问题的关键在于构造路径矩阵M。对于每个位置j，需要从前面的所有位置中选择最多 $c_j$ 个位置建立连接。为了最大化目标函数S，应当采用贪心策略：对于每个位置j，将所有前置位置按照 $A_{ij}^2$ 的值从大到小排序，然后选择前 $c_j$ 个最大的值。这样可以保证每个位置获得的注意力信息量最大。

P4227.第2题-动态注意力掩码调度问题

3000ms

Tried: 1734

Accepted: 481

Difficulty: 5

所属公司 : 华为

算法与标签>贪心算法

题目内容

你正在设计一种跨模态知的大模型精准度机制，给定一个长度为 $n$ 的输入 $token$ 序列，每个位置 $j$ 拥有一个 $d$ 维特征向量 $X_j \in \mathbb{R}^d$ 和一个正整数计算容量 $c_j$ ，表示该位置最多可接收来自前 $j$ 位置的信息连接数。

系统需完成以下步骤：

$RMSNorm$ 归一化：对所有特征向量进行 $RMSNorm$ 归一化本题取 $(\gamma = 1, \epsilon = 0)$ ：

每个特征向量记为 $x_i \in \mathbb{R}^d$ ，其第 $k$ 个分量为 $x_i[k]$ 。 $RMSNorm$ 定义为：

$\hat{X_i} = \frac{ x_i}{\sqrt{\frac{1}{d}\sum_{k=1}^{d}x_i[k]^2 + \epsilon}}\cdot\gamma$
注意力得分计算：计算每对位置 $i<j$ 的注意力得分，使用标准缩放点积公式（基于 $RMSNorm$ 归一化向量）：

$A_{ij} = \frac{\hat{x_i} \cdot \hat{x_j}}{\sqrt{d}}$
掩码矩阵构造：构造下三角注意力掩码矩阵 $M \in \{0,1\}^{n \times n}$ ，满足入度约束：

$\forall j \in [0, n), \sum_{i=0}^{j-1} M_{ij} \leq c_j$
目标函数最大化：最大化全局注意力信息总量，全局注意力信息总量定义为所有激活连接的平方注意力得分之和：

$S = \sum_{j=0}^{n-1} \sum_{i=0}^{j-1} M_{ij} \cdot A_{ij}^2$
输出整数化得分：最终返回将最大化 $S$ 乘以 $100$ 后四舍五入得到的整数，以实现保留两位小数精度的整数化表示：

$\text{round}(100 \cdot S)$

输入描述

第 $1$ 行: $n$ $d$ ，以空格分隔，分别表示 $token$ 序列长度和向量维度。
接下来 $n$ 行：每行 $d$ 个浮点数，以空格分隔，表示 $x_j$ 。
最后 $1$ 行: $n$ 个正整数，以空格分隔，表示 $c_j$ 。

约束条件

$1 \leq n \leq 1000$
$1 \leq d \leq 100$
所有向量非零

输出描述

返回一个整数，即上述步骤 $5$ 的整数化得分

样例1

输入

输出

说明

位置 $0$ ： $RMSNorm$ 归一化为 $[1, 1]$ ；无前置位置 $→$ 对信息总量贡献 $0$

位置 $1$ ： $RMSNorm$ 归一化为 $[\sqrt{2}, 0]$ ；前置位置 $j=0$ ， $A_{01}^2 = 1；c_1 = 2$ ，选择接收来自 $j=0$ 的信息 $→$ 对信息总量贡献 $1$

位置 $2：RMSNorm$ 归一化为 $[0, \sqrt{2}]$ ；前置位置 $j=0$ 和 $j=1$ ，计算 $A_{02}^2=1$ , $A_{12}^2 = 0$ ； $c_2 = 1$ ，选择接收来自 $j=0$ 的信息 $→$ 对信息总量贡献 $1$

位置 $3：RMSNorm$ 归一化为 $[1, 1]$ ；前置位置 $j=0$ 和 $j=1$ 和 $j=2$ ，计算 $A_{03}^2 = 2$ ， $A_{13}^2 = 1$ ， $A_{23}^2 = 1$ ； $c_2 = 3$ ，选择接收来自 $j=0$ 和 $j=1$ 和 $j=2$ 的信息 $→$ 对信息总量贡献 $4$

最大化 $S=6$ ，输出整数化得分 $600$

样例2

输入

输出

说明

位置 $0：RMSNorm$ 归一化为 $[\sqrt{2}, 0]$ ；无前置位置 $→$ 对信息总量贡献 $0$

位置 $1：RMSNorm$ 归一化为 $[0, \sqrt{2}]$ ；前置位置 $j=0$ ， $A_{01}^2 = 0$ ； $c_1 = 1$ ，选择接收来自 $i=0$ 的信息 $→$ 对信息总量贡献 $0$

位置 $2：RMSNorm$ 归一化为 $[1, 1]$ ；前置位置 $j=0$ 和 $j=1$ ，计算 $A_{02}^2 = 1$ ， $A_{12}^2 = 1$ ； $c_2 = 2$ ，选择接收来自 $j=0$ 和 $j=1$ 的信息 $→$ 对信息总量贡献 $2$

最大化 $S=2$ ，输出整数化得分 $200$

输入

预期输出（选填）

解题思路

P4227.第2题-动态注意力掩码调度问题

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About