No.1324 Approximate the Matrix
タグ : / 解いたユーザー数 34
作問者 :
theory_and_me
/ テスター :
opt
Problem Statement
You are given positive integers $N, K$ and non-negative integers $A_1, A_2, \ldots, A_N$ and $B_1, B_2, \ldots, B_N$. Here, it is assumed that $\sum_{i=1}^N A_i = \sum_{i=1}^N B_i = K$ holds.
Let $G$ be the set of all matrices satisfying the following conditions.
- The size is $N \times N$.
- All elements are non-negative integers.
- For $i = 1, \ldots, N$, the sum of the elements in row $i$ is equal to $A_i$.
- For $i = 1, \ldots, N$, the sum of the elements in column $i$ is equal to $B_i$.
You are given a matrix $P$ of size $N \times N$ whose elements are all non-negative integers. Find $\min_{Q \in G} \| P-Q \|_\mathrm{F}^2$.
Here, $\| \cdot \|_\mathrm{F}$ denotes the Frobenius norm of a matrix, defined for a matrix $R$ of size $N \times N$ by $\| R \|_\mathrm{F} := \sqrt{\sum_{i=1}^N \sum_{j=1}^N R_{i, j}^2}$.
It can be proved that $G$ is non-empty under the conditions of this problem, so $\min_{Q \in G} \| P-Q \|_\mathrm{F}^2$ is always defined.
Input
$N\ K$
$A_1\ A_2\ \ldots\ A_N$
$B_1\ B_2\ \ldots\ B_N$
$P_{1, 1}\ P_{1, 2}\ \ldots\ P_{1, N}$
$P_{2, 1}\ P_{2, 2}\ \ldots\ P_{2, N}$
$\vdots$
$P_{N, 1}\ P_{N, 2}\ \ldots\ P_{N, N}$
Output
Print a newline at the end.
Sample
Sample 1
Input
2 3 1 2 2 1 1 1 1 1
Output
1
In this case, the elements of $G$ are the two matrices $\begin{bmatrix} 0 & 1 \\ 2 & 0 \end{bmatrix}$ and $\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$.
When $Q = \begin{bmatrix} 0 & 1 \\ 2 & 0 \end{bmatrix}$, $\| P-Q \|_\mathrm{F}^2 = (1-0)^2 + (1-1)^2 + (1-2)^2 + (1-0)^2 = 3$, and when $Q = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$, $\| P-Q \|_\mathrm{F}^2 = (1-1)^2 + (1-0)^2 + (1-1)^2 + (1-1)^2 = 1$, so the minimum value to be found is $1$.
Sample 2
Input
2 4 2 2 3 1 2 0 1 1
Output
0
In this case, $P \in G$, so $\| P-Q \|_\mathrm{F}^2$ takes its minimum value $0$ when $Q = P$.
Sample 3
Input
3 6 2 2 2 4 1 1 3 2 1 1 8 10 2 3 5
Output
171
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。