問題一覧 > 通常問題

No.1479 Matrix Eraser

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 69
作問者 : 👑 fairy_lettucefairy_lettuce / テスター : ngtkanangtkana nok0nok0 ygussanyygussany PCTprobabilityPCTprobability
17 ProblemId : 5676 / 出題時の順位表
問題文最終更新日: 2021-04-11 14:04:35

問題文

$H$ 行 $W$ 列からなる行列 $A$ が与えられます。この行列の $i$ 行 $j$ 列の成分を $A_{i,j}$ と表します。

あなたは以下の操作を好きな順序で $0$ 回以上任意の回数行えます。

  • 行列 $A$ の $i$ 行目を選ぶ。このとき、$A$ の $i$ 行目の要素の中で $A$ の $i$ 行目の要素の最大値に等しい要素を全て $0$ にする。
  • 行列 $A$ の $j$ 列目を選ぶ。このとき、$A$ の $j$ 列目の要素の中で $A$ の $j$ 列目の要素の最大値に等しい要素を全て $0$ にする。

あなたの目標は、行列 $A$ の全ての要素を $0$ にすることです。目標を達成するのに必要な最小の操作回数を求めてください。

入力

$H\ W$
$A_{1,1}\ A_{1,2}\ \dots\ A_{1,W}$
$A_{2,1}\ A_{2,2}\ \dots\ A_{2,W}$
$\vdots$
$A_{H,1}\ A_{H,2}\ \dots\ A_{H,W}$

制約

  • $1\le H,\ W\le 500$
  • $0\le A_{ij}\le 5\times 10^5$
  • 入力は全て整数である。

出力

最小の必要な操作回数を整数で出力してください。最後に改行してください。

サンプル

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

例えば、以下のような手順で行列の要素を全て $0$ にできます。

  • $2$ 行目に操作を適用する。
  • $3$ 行目に操作を適用する。
  • $1$ 列目に操作を適用する。
  • $3$ 列目に操作を適用する。

サンプル2
入力
7 6
19 26 0 10 27 7
10 5 0 4 6 29
9 26 21 12 30 29
23 4 25 2 13 8
16 7 28 12 6 21
8 17 13 21 3 26
27 3 12 9 7 19
出力
36

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