第6回ドワンゴからの挑戦状予選 D - Arrangement

問題ページ
辞書順最小を求めるのときの定石の一つとして，あとの方をうまく並べることで（辞書順最小を無視して）答えとなる要素のうち，最小のものを末尾に追加する操作を繰り返すという貪欲法がある．擬似コードを書くと以下のような感じ．

REP(i, n) {  
    REP(j, n) if(jを追加可能) {  
        jを追加する  
        break;  
    }  
    追加できるものがなければ不可能  
}

追加する要素の条件を考える．

$A_i$ が集中している場合
まだ答えに追加していない要素の集合を st と表す．このとき，st に含まれる要素 $s$ について， $A_x = s\ (x \in st, x \neq s)$ となる場合， $s$ を答えの末尾に追加すべきである．ここで $s$ を追加しない場合，他の要素のあとのいずれにも $s$ を追加することはできない．
残りの要素数が3で，サイクルを残すことはできない
st の要素数が3でである場合にを追加できる条件
- $A_q = r, A_r = q$ ではない
- 一つ前に追加した要素で $p$ が来ることを禁止されない
  $q, r$ についても同様の条件となる．追加可能な最小な要素を追加すればよい．
一つ前に追加した要素で右に来ることを禁止される
追加できるならset のうち最小の要素，最小の要素がだめなら2番目の要素を追加する

$A_i$ が集中する条件を判定するために map を用意する． $mp \lbrack i \rbrack = (A_s=i$ となる要素数 $)\ (s \in st)$ となるように map を管理することで， $A_i$ が集中している場合の判定を行うことができる．
st.size() == 3 の場合はどうせ要素数が少ないので愚直にやっても問題ない．
どちらでもない場合は st の最小値，小さい方から2番目の値を求め，禁止されないより小さい方を追加すればいい．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i], a[i]--;  
  
    if(n == 2) {  
        cout << -1 << endl;  
        return 0;  
    }  
  
    map<ll, ll> mp;  
    REP(i, n) mp[a[i]]++;  
    set<ll> st;  
    REP(i, n) st.insert(i);  
    vector<ll> ans;  
  
    auto add = [&](ll x) {  
        ans.push_back(x);  
        st.erase(x);  
        mp[a[x]]--;  
        if(mp[a[x]] == 0) mp.erase(a[x]);  
    };  
  
    REP(i, n) {  
        ll mi = st.size() ? *st.begin() : INF;  
        ll mi2 = st.size()>=2 ? *(next(st.begin())) : INF;  
        // dump(ans, st, mp);  
        if(mp.size() == 2) {  
            auto p1 = *mp.begin();  
            auto p2 = *(next(mp.begin()));  
            if(st.find(p1.first) != st.end() && p2.second == 1) {  
                add(p1.first);  
                continue;  
            }  
            if(st.find(p2.first) != st.end() && p1.second == 1) {  
                add(p2.first);  
                continue;  
            }  
        }   
        if(st.size() == 3) {  
            vector<ll> v;  
            for(auto j: st) v.push_back(j);  
            bool f0 = true, f1 = true, f2 = true;  
            if(a[v[1]] == v[2] && a[v[2]] == v[1]) f0 = false;  
            if(i && a[ans.back()] == v[0]) f0 = false;  
            if(a[v[0]] == v[2] && a[v[2]] == v[0]) f1 = false;                  
            if(i && a[ans.back()] == v[1]) f1 = false;  
            if(a[v[0]] == v[1] && a[v[1]] == v[0]) f2 = false;  
            if(i && a[ans.back()] == v[2]) f2 = false;  
  
            if(f0) add(v[0]);  
            else if(f1) add(v[1]);  
            else if(f2) add(v[2]);  
            else {  
                cout << -1 << endl;  
                return 0;  
            }  
        }  
        else if(i == 0) add(0);  
        else if(a[ans.back()] == mi) add(mi2);  
        else add(mi);  
    }  
  
    REP(i, n) cout << ans[i]+1 << (i==n-1 ? '\n': ' ');  
    cout << flush;  
  
    return 0;  
}

ferinの競プロ帳

競プロについてのメモ

第6回ドワンゴからの挑戦状予選 D - Arrangement