問題一覧 > 通常問題

No.1225 I hate I hate Matrix Construction

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 165
作問者 : tyawanmusityawanmusi / テスター : nok0nok0
6 ProblemId : 4833 / 出題時の順位表
問題文最終更新日: 2020-08-31 11:03:01

元ネタ

I hate Matrix Construction
面白い問題です。

問題文

整数 $N$ 及び長さ $N$ の配列 $S,T$ が与えられます。

以下の条件を満たす $N \times N$ の行列 $a$ を考えます。

  • $a_{i,j}=0,1$
  • $S_i = 0$ のとき $i$ 行目の論理和は $0$
  • $S_i = 1$ のとき $i$ 行目の論理和は $1$
  • $S_i = 2$ のとき $i$ 行目の論理積は $1$
  • $T_j = 0$ のとき $j$ 列目の論理和は $0$
  • $T_j = 1$ のとき $j$ 列目の論理和は $1$
  • $T_j = 2$ のとき $j$ 列目の論理積は $1$

条件を満たす行列 $a$ が存在することは保証されます。

$\sum_{i=1}^{N} \sum_{j=1}^{N} a_{i,j}$ の最小値を求めてください。

制約

  • 入力は全て整数
  • $1 \le N \le 500$
  • $0 \le S_i \le 2$
  • $0 \le T_i \le 2$

入力

$N$
$S_1\ \ S_2\ \dots \ S_N$
$T_1\ \ T_2\ \dots \ T_N$

$1$ 行目には $N$ が与えられます。
$2$ 行目には $S$ が空白区切りで与えられます。
$3$ 行目には $T$ が空白区切りで与えられます。

出力

答えを $1$ 行に出力してください。
最後に改行してください。

サンプル

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

条件を満たす行列として、 $\left(\begin{array}{ccc} 1 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{array}\right)$ や $\left(\begin{array}{ccc} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right)$ や $\left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{array}\right)$ などが挙げられます。

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

条件を満たす行列として、 $\left(\begin{array}{ccc} 0 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right)$ や $\left(\begin{array}{ccc} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array}\right)$ などが挙げられます。

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