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

2020年9月12日2020年12月13日

問題

方針

\( 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)\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int S[N], T[N];
    int s1 = 0, s2 = 0, t1 = 0, t2 = 0;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        if (S[i] == 2) s2++;
    }
    for (int i = 0; i < N; i++) {
        cin >> T[i];
        if (T[i] == 2) t2++;
    }
    for (int i = 0; i < N; i++) {
        if (s2 == 0 && T[i] == 1) t1++;
        if (t2 == 0 && S[i] == 1) s1++;
    }
    //int k = N * s2 + N * t2 - s2 * t2;
    int ans = N * s2 + N * t2 - s2 * t2 + max(s1, t1);
    cout << ans << "\n";
}