GCJ Round 1A 2016 Problem B. Rank and File

問題

Dashboard - Round 1A 2016 - Google Code Jam

行列が以下の条件を満たしている。

• 各行について, 要素が左から右に狭義単調増加
• 各列について, 要素上から下に狭義単調増加

各行, 各列単位で見るとそれぞれ N 個の要素がある。これらのうち, 2*N-1 個の情報がわかっている時, 残りの行/列の N 個の要素はどうなっているか。

解法

2*N 個の行, 列をカウントするとすべての要素を 2 回ずつ数えることになります。よって, 奇数回しかカウントされていない数を小さい順に並べたのが答えです。

int heights[110][55];
int cnt[2555];

void solve() {
    int N;
    cin >> N;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < 2*N-1; i++) for (int j = 0; j < N; j++) {
        int num;
        cin >> num;
        cnt[num]++;
    }
    vi v;
    for (int i = 0; i < 2555; i++) if (cnt[i]%2) v.push_back(i);
    assert(v.size() == N);
    for (int i = 0; i < N; i++) {
        cout << v[i];
        if (i < N-1) cout << " ";
    }
    cout << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": " ;
        solve();
    }
    return 0;
}