Codeforces #323 Div. 2 C GCD Table

2015/10/04 (Sun) Codeforces 貪欲

問題

問題文

方針

最初は $a$ を空にして順々に追加していく方針で解く. 残っている整数を multiset などで管理しながら,テーブルの確定する正方形の部分を広げていく. 最初に multiset 中で最大のものを $x$ とすると $\gcd(x,x)=x$ 以外にそれを作れる 2 つの整数は無いので, $a$ に $x$ を追加する.$x$ を使ったので multiset から除く. 次に大きい整数 $y$ も同様に $a$ に追加する. すると $x$ と $y$ の行と列が交わる部分の 2 マスに入るべき整数が確定するので,それも multiset から除く. これを $a$ の長さが $n$ になるまで続ける.

std::multiset で 1 つだけ消す方法を知らなかったので下の実装では std::map を使ってひどいことをしている. multiset で 1 つだけ消すにはイテレータを渡すといいらしい.

実装

int n;
vector<int> a;

#define ERASE(m,e)                              \
    do {                                        \
        m[e]--;                                 \
        if(m[e]==0) m.erase(e);                 \
    } while(0)                                  \

void show(map<int,int> m){
    vector<int> a;
    for(auto & e : m){
        rep(i,e.second) a.push_back(e.first);
    }
    dump(a);
}

vector<int> solve(){
    vvi tab(n,vi(n,-1));
    vector<int> idx(n);
    int size = 0;
    map<int,int> m;
    rep(i,a.size()) m[a[i]]++;
    while(size < n){
        int t = m.rbegin()->first;
        ERASE(m,t);
        idx[size] = t;
        tab[size][size] = t;
        size++;
        rep(i,size)rep(j,size){
            if(tab[i][j] != -1) continue;
            int g = __gcd(idx[i], idx[j]);
            tab[i][j] = g;
            ERASE(m,g);
        }
        dump(idx);
        for(auto & e : m){
            dump(e);
        }
    }
    return idx;
}

signed main(){
    while(cin >> n){
        a.resize(n*n);
        rep(i,n*n) cin >> a[i];
        cout << solve() << endl;
    }
}