No.14 最小公倍数ソート - yukicoder
- 印象深かったのでメモ
- 最初方針はあっていたのだけど、O(N^2) で TLE してしまった。
- 以下は他の人のコードを見て修正して通したやつ。
- swap で pivot の位置をずらしてループの回数を減らすのはうまいと思った。(solve1)
- int の set じゃなくて pair の set に (a[i],i) を突っ込んでソートさせるのはうまいと思った。(solve_optim)
- こういうデータ構造の選定がうまくできるようになりたい。
class LCMsort {
public:
void solve1(void) {
int N;
cin>>N;
vector<int> a(N,0);
REP(i,N)
cin>>a[i];
REP(pivot,N)
{
cout<<a[pivot]<<" ";
int mx = (1<<30);
int mi = -1;
FOR(i, pivot+1, N)
{
int k = lcm(a[pivot], a[i]);
if (k < mx || (k == mx && a[i] < a[mi]))
{
mx = k;
mi = i;
}
}
if (mi < 0)
break;
swap(a[pivot+1], a[mi]);
}
cout<<endl;
}
void solve_optim(void) {
int N;
cin>>N;
vector<int> a(N,0);
int maxA = 0;
REP(i,N)
{
cin>>a[i];
maxA = max(a[i], maxA);
}
vector<vector<int>> div(N+1);
vector<set<pair<int,int>>> S(maxA+1);
REP(i,N)
{
int x = a[i];
for (int d = 1; d*d <= x; ++d)
{
if (x%d == 0)
{
div[i].push_back(d);
if (d != x/d)
div[i].push_back(x/d);
S[d].emplace(x,i);
S[x/d].emplace(x,i);
}
}
}
int pivot = 0;
REP(_,N)
{
cout<<a[pivot]<<" ";
int mx = (1<<30);
int mi = -1;
for (auto d : div[pivot])
{
S[d].erase(make_pair(a[pivot], pivot));
if (S[d].empty())
continue;
int aa, ii;
tie(aa,ii) = *S[d].begin();
int k = lcm(a[pivot], aa);
if (k < mx || (k == mx && a[ii] < a[mi]))
{
mx = k;
mi = ii;
}
}
if (mi < 0)
break;
pivot = mi;
}
cout<<endl;
}
void solve(void) {
solve_optim();
}
};