← 返回题目列表

AtCoder · genocon2021_c

C. 练习3

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

问题陈述

鉴于 m 字符串组成 A, C, G, T。让我们插入空白符号(每个符号用 -)到字符串以制作另一组 m 字符串,使得所有长度都相等并生成 m by n 矩阵 S 其中每一行都是字符串之一 n 是字符串的长度。我们表示一个元素(即字符) i第行和 j第列 S by S_{i, j} (1 \leq i \leq m, 1 \leq j \leq n)。我们还表示行向量和列向量 分别为 S_{i,*} 和 S_{*,j} 。 让我们考虑插入 - at 适当 位置,以便我们可以生成 对齐 S ,其中每个列向量中包含相同的字符。为此,我们定义以下分数 C 测量给定列向量的大小 t 对齐良好。

C(t) = min_{x \in \{A, T, G, C, -\}} \left| \{ t[i] \; | \; t[i] \neq x \; (i=1, \ldots, m) \} \right|

C(t) 计算字符数 t 不等于出现在 t 最频繁。例如,当 t=CCCC-T, C 出现频率最高,因此不等于的字符数 C (即, - 和 T) 变为 C(t)=2。当 t=CCAA-T,可以选择其中之一 C or A as x 因为计数 C 和 A 相等。如果 C 选择为 x, C(t) 变为 4 通过添加计数 A, - 和 T.

如果我们可以生成 S 这样的总和 C(S_{*,j}) 对于所有列都变小,预计给定 m 字符串对齐良好。我们将这样的问题称为多重对齐并定义以下分数。

C_{all}(S) = \sum_{j=1}^n C(S_{*,j})

例如,如果我们对齐三个字符串 GGATC, GGAT, 海关总署 通过插入 - 如下,

  GGATC
  GGAT-
  G-ACC

分数 C_{all}(S) 变为 C(S_{*,1}) + C(S_{*,2})+ C(S_{*,3})+ C(S_{*,4})+ C(S_{*,5}) = 0 + 1 + 0 + 1 + 1 = 3.

鉴于 m 字符串 s_{1}, \ldots, s_{m},输出多重对齐,使得 C_{all}(S) 变得尽可能小。

约束

  • s_1,...,s_m 是由以下组成的字符串 A, C, G, T.
  • 测试用例(小)
    • 8 \leq m \leq 10.
    • 80 \leq |s_1|, \ldots, |s_m| \leq 100 (长度 x 表示为|x|.)
  • 测试用例(大)
    • $35 \leq m \leq
    • 700 \leq |s_1|, \ldots, |s_m| \leq 750

输入

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

m
s_{1}
s_{2}
 :
s_{m}

输出

打印输入字符串的多重对齐,使得 C_{all} 变得尽可能小。 插入后 - 在每个输入字符串中,它们的打印顺序应与输入字符串的顺序相同。

评审系统只能在以下情况下接受用户的输出: - 每行等于相应的输入行,如果 - 已删除。 - 所有线的长度都相等。


示例输入 1

10
GGAGGTTATTGCTGTGGAGGTACTGGAGAAGGAGGATGCTAGCGTTGGGTAAACCACGAGCATTTTGACTTGTACTTCGCCTC
GGGTTATTGCTGTTGTGAGTACTGGAGACAGGAGGGAGTGTTAGAGTTGGGGTAAACCACAGTAGCTCATGTCACTTGGATAACTCGTCAGCCTC
GGTCACTCGCTGTGGAGAGTACTTTGAGACAGGAGGGAGTGCTAGAGTTTGGGGTAAAACCACAGCAGCTCATGCACTTGGATATCTGTGAGCC
GAGGTTAGTGCTGTGGAGAGTACTGGAGACAGGAGGGAGTGCTAGAGTTGGGGTAAAGCACAGCACCATTCACTGATAAATGTCAGGCCTAGGGG
GAGGTATTGCTGTGGAGGGTACTGGAGACAGGAGGAGTGCTAGAGGTTGGGGTAAAACCACAGCAGCTCATTTACTTGATACTGTCAGGCTCAGG
GAGGTTATTTGCTGTGGAGAGTTACTGAGACATGGGGTGCCAAGTTGGGTAGCTACAGCAGCTCATTTCACTTGATACTGCAGGCTCTCAG
GAGTTAATTTCGTGGAGAGTACTAGAGCACAGGAGGGAGGCCAGATTGGGGTATACCACAGCAGCTCGTTCACTTTAACTGTCAGGCCCTCA
ACAGTTTAATTGATGGGCGGAGAGTACTGGAGACAGGAGGGAGTGCTAGAGTGGGGTAAACCACAGCAGCATCTTTCATTATAACTGTCAG
CAAGGTTTTTTCGCTGTGGAGAGTACTGGAGACCGGGGAGTGTAGACTTTGGGGTATCACGTAGCAGCTTATTTCGACTTTGTACTGTAA
GAGTTATTTCTGTGGAGAGAACTGGAGACGGAGGGAGTGCTAGAGTTGGGGTAAACACCAGGCAGCCATTTCACTTGATAACTGTCAGGCCTT

示例输出 1

GGAGGTTA-TTGCT--GTGGAG-GTAC-TGGAGA-AGGA-GGA-TGCTAGCG-TT-GGGT-AAACCAC-G-AGC-ATTTTGACTT-G-T-ACT--TC-GCCTC----
--GGGTTA-TTGCT--GTTGTGAGTAC-TGGAGACAGGAGGGAGTGTTAGAG-TTGGGGT-AAACCACAGTAGCTCATGTCACTTGGATAACTCGTCAGCCTC----
---GGTCACTCGCT--GTGGAGAGTACTTTGAGACAGGAGGGAGTGCTAGAGTTTGGGGTAAAACCACAGCAGCTCATG-CACTTGGATATCT-GTGAG-C-C----
-GAGGTTA-GTGCT--GTGGAGAGTAC-TGGAGACAGGAGGGAGTGCTAGAG-TTGGGGT-AAAGCACAGCA-CCATTCACTGATAAATGTCAGGCCTAGGGG----
--GAGGTA-TTGCT--GTGGAGGGTAC-TGGAGACAGGA-GGAGTGCTAGAGGTTGGGGTAAAACCACAGCAGCTCAT-TTACTT-GAT-ACT-GTCAGGCTC-AGG
-GAGGTTATTTGCT--GTGGAGAGTTACT-GAGACA--TGGG-GTGCCA-AG-TT-GGGT--AGCTACAGCAGCTCATTTCACTT-GAT-ACT-G-CAGGCTCTCAG
--GAGTTAATTTC---GTGGAGAGTACTAGAGCACAGGAGGGAG-GCCAGA--TTGGGGT-ATACCACAGCAGCTCGT-TCACTT---TAACT-GTCAGGC-CCTCA
ACAGTTTAATTGATGGGCGGAGAGTAC-TGGAGACAGGAGGGAGTGCTAGAG--TGGGGT-AAACCACAGCAGCATCTTTCA-TT--ATAACT-GTCAG--------
CAAGGTT-TTTTCGCTGTGGAGAGTAC-TGGAGAC-CG-GGGAGTG-TAGACTTTGGGGT---ATCAC-GTAG--CAGCTTATTTCG--ACTTTGT-A--CT-GTAA
--GAGTTA-TTTCT--GTGGAGAGAAC-TGGAGAC-GGAGGGAGTGCTAGAG-TTGGGGT-AAACACCAGGCAGCCATTTCACTT-GATAACT-GTCAGGC-C--TT

积分

提交的程序通过两种测试用例类型进行评估:小型和大型,如约束部分中所示。 Small 包含 2 个案例,Large 包含 8 个案例。分数将给予在时间限制内满足格式的输出。 对于 Small 中测试用例的每个输出,参赛者将获得 \{200 - \lfloor C_{all}(S) * 0.2 \rfloor \} 或 0,以较大者为准。对于大型测试用例,参赛者获得 \{700 - \lfloor C_{all}(S) * 0.1 \rfloor \} 或 0,以较大者为准。例如,如果可以生成两个输出 S_1 和 S_2 限期内格式正确的小型案件,可赚取 max\{200 - \lfloor C_{all}(S_1) * 0.2 \rfloor, 0\} + max\{200 - \lfloor C_{all}(S_2) * 0.2 \rfloor, 0\}.

我们不保证最优解能够达到最高分(6000分)。最终排名由用于生成当前测试用例的相同方法生成的其他数据集决定。

测试用例的生成方法

我们提取子字符串 s 第一步来自人类参考基因组序列的 22 号染色体。 s 被提取,因此它不包括 N 并且仅包含 A, T, G 和 C。在第二步中,我们生成插入/删除/替换 s 创建一个新字符串 s' 基于模拟特定测序仪的测序错误模型。在第三步中,我们重复第二步来生成所有输入字符串。请注意 s 不包含在测试用例中。我们不描述我们使用的排序错误模型,但提供可从以下 URL 获取的示例测试用例。