問題一覧 > 通常問題

No.1324 Approximate the Matrix

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 34
作問者 : theory_and_me / テスター : opt
お気に入りにしたユーザー ProblemId : 5545 / 自分の提出
問題文最終更新日: 2021-04-03 12:29:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2020 (順位表) の他の問題:

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}$

  • All inputs are integers.
  • $1 \leq N, K \leq 200$
  • $0 \leq A_i \leq 200 \quad (i=1, 2, \ldots, N)$
  • $0 \leq B_i \leq 200 \quad (i=1, 2, \ldots, N)$
  • $\sum_{i=1}^N A_i = \sum_{i=1}^N B_i = K$
  • $0 \leq P_{i, j} \leq 200 \quad (i, j=1, 2, \ldots, 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もしくは右上の雲マークをクリックしてアカウントを作成してください。