GCJ 2016 Round 1A B - Rank and File

問題

Dashboard - Round 1A 2016 - Google Code Jam

問題概要

兵士を1辺がの正方形のグリッドに1人ずつ立たせる．兵士にはそれぞれ身長があり，身長に関してどの行を左から順にみても厳密に増加する列になっているし，どの列を前方からみても厳密に増加する列になっている(この定義からも察するに，同じ行や同じ列には同じ身長の兵士はいないが，正方形のグリッド全体を見ると同じ身長の兵士がいる可能性はある)．

いま，それぞれの行および列に関して身長の値を調べた計個のリストがあるが，その内の1つをなくしてしまった．なくしてしまった1つのリストに何が書いてあったか復元せよ．答えは1つに定まることが保証されている．

• 兵士の身長について，

アイデア

まず，smallはである．それでも，愚直に順列をしらべるのはとても時間がかかる(最大で20!通り)．そこでちょっと考え方を変えて，無くなったリストが列に関するものだとしよう(これにより一般性は失わない)．すると，必ず個の行に関するリストはあることになる．そうすると個の中から個を選ぶという全探索にかわり(通り)，これは大きくても100000通りくらいに抑えられる．あとは列の中から個全てがある列と一致してたら残りの1列を答えにすれば良い．

では，largeはどうするか．今度はである．到底間に合わない．まず，問題に立ち返ってみるとグリッドの復元は必要なく，欲しいのは無くなったリスト1つの構成だけである．これをうまく活かしたい．

さて，今リストはなくなっておらず，個のリストがある状態を考えてみる．そのリストを作成するにあたって，各行・各列をそれぞれ1回ずつ線形的になめていってリストが作成されるのがシンプルなリストの構成方法である．こうしていったときに，それぞれのグリッド内の値はに対して行のリストと列のリストに載るわけなので，2回登場することになる．そこから，1つだけリストがなくなった状態を考えてみると，その行・または列は1回しか数え上がられていないことになる．

つまり，身長の値の登場回数を数え上げて，奇数のものを個小さい方から選んだものが答えに他ならない．

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int main()
{
    int T;
    cin >>T;
    rep(t,T)
    {
        int n;
        cin >>n;

        int ct[2501]={0};
        rep(i,2*n-1)rep(j,n)
        {
            int a;
            cin >>a;
            ++ct[a];
        }

        vector<int> ans;
        rep(i,2501)
        {
            if(ct[i]%2==1) ans.pb(i);
        }

        printf("Case #%d:",t+1);
        for(const auto& x:ans) printf(" %d",x);
        printf("\n");
    }
    return 0;
}

smallすら通してなかったのは多分この問題にとりかかろうかと思った時点でもう1000人をとうに超す人が通しててやる気が喪失してたからだった気がする，朝っぱらだったし...