← 返回题目列表

AtCoder · ahc047_a

A. 可爱的语言模型

中文机器翻译题面 查看原题

问题陈述

高桥有 N 最喜欢的字符串。的 i-th 字符串表示为 S_i,其偏好是 P_i。每个 S_i 仅由小写英文字母组成 a to f.

最近,Takahashi 对生成字符串的概率模型产生了兴趣。他想设计一个生成模型,称为 可爱的语言模型(法学硕士),以高概率生成他喜欢的字符串。

该模型包括 M 状态。指定一个小写字母 C_i 来自 a to f 到每个州 i (0 \leq i < M)。此外,对于每对状态 (i, j),定义状态的转移概率 i 说明 j 作为整数 A_{i,j},表示百分比值。这些值必须满足以下所有条件 i:

\[ \sum_{j=0}^{M-1} A_{i,j} = 100 \]

模型从状态开始 0 并在生成长度的字符串后停止 L。生成的字符串的第一个字符是分配给状态的字符 0,即 C_0。然后,模型根据转移概率执行状态转移,按顺序输出分配给每个新转移状态的字符。

对于每个字符串 S_i,如果出现 至少一次 作为生成字符串中的连续子字符串,高桥获得其相应的优先级 P_i。你的任务是设计角色分配 C_0, C_1, \dots, C_{M-1} 和转移矩阵 A 最大化预期总偏好。

评分

让 Q_i 是生成的长度为字符串的概率 L 包含字符串 S_i 至少一次 作为连续子字符串。

然后,您的分数计算如下:

\[ \mathrm{round}\left(\sum_{i=0}^{N-1} P_i \cdot Q_i\right) \]

有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入由标准输入按以下格式给出:

N M L
S_0 P_0
S_1 P_1
\vdots
S_{N-1} P_{N-1}
  • N 是字符串的数量。它固定在 N = 36 在所有测试用例中。
  • M 是模型中的状态数。它固定在 M = 12.
  • L 是要生成的字符串的长度。它固定在 L = 10^6.
  • 每个 S_i 是由小写英文字母组成的字符串 a to f,长度满足 6 \leq |S_i| \leq 12.
  • 每个偏好 P_i 是满足以下条件的正整数 1 \leq P_i \leq 17000.
  • 全部 S_i 是不同的。

输出

在设计的模型中,让 C_i 是分配给状态的字符 i,和 A_{i,j} 是状态的转移概率 i 说明 j.

然后,按以下格式输出到标准输出:

C_0 A_{0,0} \cdots A_{0,M-1}
\vdots
C_{M-1} A_{M-1,0} \cdots A_{M-1,M-1}
  • 每个 C_i 必须是以下小写字母之一 a to f.
  • 每个 A_{i,j} 必须是满足以下条件的整数 0 \leq A_{i,j} \leq 100,并且对于每个 i,必须满足以下条件:

\[ \sum_{j=0}^{M-1} A_{i,j} = 100 \]

您的程序可能会输出多个解决方案。 如果输出多个解,则仅使用最后一个进行评分。 您可以使用可视化工具的网络版本来比较多个解决方案。

显示示例

输入生成

\mathrm{rand}(L, U): 生成一个均匀随机的整数 L 和 U,包括在内。

字符串的生成 S_i

对于每个 S_i,确定其长度 \ell_i 使用 \ell_i = \mathrm{rand}(6, 12),然后生成一个长度的字符串 \ell_i 如下:

  • 随机选择 字母中的 \ell_i 字符 a to f 并将它们连接起来。
  • 同一字符可能会出现多次。

如果生成的字符串 S_i 与任何先前生成的字符串相同,从长度选择步骤重新开始生成。

偏好的生成 P_i

对于每个字符串 S_i,生成其对应的首选项 P_i 如下:

  • 计算上限 U_i = \left\lfloor 1.5^{2 \cdot \ell_i} \right\rfloor.
  • 生成 P_i = \mathrm{rand}(1, U_i) 均匀随机。

独立重复此过程以生成 N = 36 对 (S_i, P_i).

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。


示例输入 1

36 12 1000000
acafbafdb 166
baeebdacd 86
baaffdcf 76
cfddcba 251
acdecbbfddaf 12423
ebcebe 107
feddecdb 373
acadbc 40
dcfaabebefcd 15639
fcebaade 438
cbefcedaaf 2468
efcfafcbcaac 4414
dbddcfa 96
cabacbdb 219
cbdeadcbad 3110
bbdeacbbe 894
deafadebdad 7067
dceedaacfefa 6453
deffecdee 280
cfffaaeca 651
aeffcbcfec 1021
ccefdcddadfd 6189
ffcdcb 91
afddebceadc 2283
ffebaff 258
aeceafebd 1235
fbbfec 83
fcdeceffbaf 1787
ddfffeb 188
bebffddaa 238
eedbfbaed 500
cacbccdbd 1346
cafbfbedcff 393
eccbdecdfefa 4423
fdfaddae 522
befebddfe 507

示例输出 1

e 66 0 0 0 0 12 0 0 0 0 9 13
e 36 12 0 0 0 0 0 0 0 11 0 41
d 0 20 0 56 0 0 0 0 5 0 19 0
a 0 8 12 79 1 0 0 0 0 0 0 0
f 0 0 0 0 0 0 41 0 0 10 37 12
c 0 0 0 31 0 0 0 53 15 0 1 0
b 0 0 0 0 23 0 65 1 0 0 0 11
f 34 0 8 0 0 0 0 0 0 14 0 44
e 21 0 0 0 10 57 0 0 0 12 0 0
f 0 41 18 0 0 22 0 0 0 0 19 0
a 6 0 0 46 0 0 16 0 0 0 32 0
b 12 0 0 21 24 43 0 0 0 0 0 0