No.1166 NADA DNA
蜜蜂
MitarushiProblem Statement
$N$ species of monkeys live in the Nada region.
You are going to build a phylogenetic tree of the monkeys of the Nada region using DNA sequences.
A phylogenetic tree is a full binary tree showing the relationships between species of organisms, where leaf nodes correspond to organisms and internal nodes correspond to branch points.
A DNA sequence is represented by a string consisting of A, T, G, C, and for each of monkey species $1$ through monkey species $N$, DNA sequences $G_1$ through $G_N$ of length $L$ are given.
As a measure of the inaccuracy of a phylogenetic tree, the "cost of a phylogenetic tree" is defined as described below.
----
<Cost of a Phylogenetic Tree>
First, the DNA distance ${\rm D}(X,\ Y)$ between $2$ species of monkeys is defined as follows: for the DNA sequences $G_X,\ G_Y$ of $2$ distinct monkey species $X, Y$, the number of positions where the $i$-th characters from the left $(1\leq i\leq L)$ of $G_X$ and $G_Y$ do not match (the Hamming distance) is defined as the DNA distance between those $2$ species, and is denoted by ${\rm D}(X,\ Y)$.
For example, if $G_X,\ G_Y$ are ACGTTA, ACCTGA respectively, the characters at positions $3, 5$ from the left differ, so ${\rm D}(X, Y) = 2$.
Next, the cost of a branch point is defined as follows: let species $A$ be one of the species belonging to the binary tree on one side of the branch point, and species $B$ be one of the species belonging to the binary tree on the other side; the minimum value of ${\rm D}(A,\ B)$ is the cost of that branch point.
The sum of the costs of all branch points of a phylogenetic tree is the "cost of the phylogenetic tree".
----
You want to build a phylogenetic tree with as low a cost as possible. Output the minimum possible value of the cost of a phylogenetic tree of the $N$ species of monkeys.
Input
$N\ \ \ L$
$G_1$
$G_2$
$\ \vdots$
$G_N$
$N,\ L$ are integers
$2\leq N\leq 1000$
$1\leq L\leq 50$
$G_i$ is a string of length $L$ consisting of A, T, G, C $(1 \leq i \leq N)$
Output
Output the answer on $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
3 4
AAAA
AGGA
AGGT
Output
3
There are $3$ possible patterns of phylogenetic trees.
In case (A), the cost of the branch point of species $2$ and species $3$ is ${\rm D}(2,\ 3)=1$, and the cost of the branch point of species $1$ is $2$, the smallest of the values ${\rm D}(1,\ 2)=2$ and ${\rm D}(1,\ 3)=3$ (these $2$ values). Therefore, the cost of the phylogenetic tree (A) is $3$.
The costs of (B), (C) are $4, 3$ respectively, so the minimum value to output is $3$.
Sample 2
Input
4 7
TCAAGCT
TAACGCC
ACACGTT
ACGACTC
Output
10
There are $15$ possible patterns of phylogenetic trees.
For the phylogenetic tree below, the cost of the branch point of species $1$ and species $2$ is ${\rm D}(1,\ 2)=3$, the cost of species $3$ and species $4$ is ${\rm D}(3,\ 4)=4$, and the cost of the branch point closest to the root of the phylogenetic tree is the smallest of ${\rm D}(1,\ 3)=3,\ {\rm D}(1,\ 4)=5,\ {\rm D}(2,\ 3)=4,\ {\rm D}(2,\ 4)=6$, which is $3$. Therefore, the cost of the phylogenetic tree below is $10$.
No phylogenetic tree with a cost of $9$ or less exists, so the minimum value to output is $10$.
Source
Nada School 75th Class Junior High School Graduation Commemorative Contest: NADA DNA
writer: tetanura
tester: Mitarushi
Ported in accordance with the HackerRank terms of service. Some parts have been modified.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。