問題一覧 > 通常問題

No.1324 Approximate the Matrix

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 28
作問者 : theory_and_metheory_and_me / テスター : optopt
5 ProblemId : 5545 / 出題時の順位表
問題文最終更新日: 2020-12-13 15:09:10

問題文

正の整数 $N, K$ と,非負整数 $A_1, A_2, \ldots, A_N$ および $B_1, B_2, \ldots, B_N$ が与えられます. ここで,$\sum_{i=1}^N A_i = \sum_{i=1}^N B_i = K$ が成り立つとします.

以下の条件をみたす行列全体の集合を $G$ とします.

  • サイズが $N \times N$ である.
  • 全ての要素が非負整数である.
  • $i = 1, \ldots, N$ について,$i$ 行目の要素の和が $A_i$ に等しい.
  • $i = 1, \ldots, N$ について,$i$ 列目の要素の和が $B_i$ に等しい.

全ての要素が非負整数であるサイズ $N \times N$ の行列 $P$ が与えられるので, $\min_{Q \in G} \| P-Q \|_\mathrm{F}^2$ を求めて下さい.

ただし,$\| \cdot \|_\mathrm{F}$ は行列のフロべニウスノルムであり, サイズ $N \times N$ の行列 $R$ について $\| R \|_\mathrm{F} := \sqrt{\sum_{i=1}^N \sum_{j=1}^N R_{i, j}^2}$ で定義されます.

また,本問題の条件のもとで $G$ は非空であることが証明できるため,$\min_{Q \in G} \| P-Q \|_\mathrm{F}^2$ は必ず定義されます.

入力

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

  • 入力は全て整数である
  • $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)$
  • 出力

    最後に改行してください。

    サンプル

    サンプル1
    入力
    2 3
    1 2
    2 1
    1 1
    1 1
    
    出力
    1

    この場合,$G$ の要素は $\begin{bmatrix} 0 & 1 \\ 2 & 0 \end{bmatrix}$ と $\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$ の2つの行列です.

    $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$ であり, $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$ であるため, 求める最小値は $1$ です.

    サンプル2
    入力
    2 4
    2 2
    3 1
    2 0
    1 1
    
    出力
    0

    この場合,$P \in G$ であるため, $Q = P$ とした場合に $\| P-Q \|_\mathrm{F}^2$ は最小値 $0$ をとります.

    サンプル3
    入力
    3 6
    2 2 2
    4 1 1
    3 2 1
    1 8 10
    2 3 5
    出力
    171

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。