[yukicoder] No. 1225 I hate I hate Matrix Construction

問題

方針

\( S_i = j\) となる個数を \( s_j \)、\( T_i = j \) となる個数を \( t_j \) とします。\( S_i = 2\) のとき、\( i \) 行目は全て \( 1 \) となり、\( T_i = 2 \) となるとき、\( i \) 列目は 全て \( 1 \) となります。この条件から少なくとも、

\[ N(s_2 + t_2) – s_2 t_2\]

個の \( 1 \) があることが分かります。次に、\(S_i = 1 \) となるとき、 \( i \) 行目には少なくとも \( 1 \) が \( 1 \) つ以上存在する必要がありますが、\( s_2 \neq 0 \) のとき、既に \( i \) 行目には \( 1 \) が置かれているので、新たに \( 1 \) を置く必要はありません。同様に \( T_i = 1 \) についても同じことが言えます。

ここで、\( t_2 = 0 \wedge S_i = 1 \) となる個数を \( s_1 \)、\( s_2 = 0 \wedge T_i = 1 \) となる個数を \( t_1 \) と再定義します。 このとき、\( s_1 + t_1 \) 個の \( 1 \) を置く必要はありません。\( 1 \) を新たに置く個数は \( \max(s_1, t_1) \) となります。例えば、\( t_1 < s_1\) のとき、\( s_1 \) 個の \( 1 \) を好きな列に置くことができるので、\( T_i = 1\) を満たすことができます。

したがって、求める答えは、

\[ N(s_2 + t_2) – s_2 t_2 + \max(s_1, t_1)\]

となります。

コード