Arrangement [Dwango Programming Contest 6th D]

https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d

解説

https://atcoder.jp/contests/dwacon6th-prelims/submissions/9429060

条件を見てみると、Nが増えていくと大体作れそうな感じがする。
で、適当にdfsで全探索するとダメ。
ちゃんとやろうということか。

今回の問題のような、つくれれは何でもいいのではなく、辞書順最小のものを構築せよという問題は、常套テクがある。
先頭から貪欲に作っていくという方針である。
それを置くことでそれよりも後ろを構築可能かというのを確認しながら、先頭から辞書順最小のものをおいていく。
今回でいうと、Nがある程度ちっさくなるまでは、適当においておいても問題ない。
本番中に、その閾値をちゃんと求めるのが難しかったら、ガチャろう。

Nがある程度から小さくなった場合はどうするかであるが、全探索してしまおう。
これで通るかなーと思ったら、通らない。

コーナーケースがある。
例えば、
6 6 6 6 6 1
となっている場合は、1～5をどうおいても6がおけなくなってしまう。
このように、残りの数が1つを除いて、その1つを指している時である。
この場合は、それらを置く前に差されているものを置く必要がある。
これは指している数をどっかで数えておけば大丈夫。

int N, A[101010];
int limit = 8;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) A[i]--;

    int originalN = N;

    vector<int> ans;
    set<int> unused;
    rep(i, 0, N) unused.insert(i);
    
    Counter<101010> counter;
    rep(i, 0, N) counter.Increment(A[i]);

    while (limit < N) {
        if (counter.Kinds.size() == 2) {
            auto ite = counter.Kinds.begin();

            int x = *ite; ite++;
            int y = *ite;

            if (counter.Count[x] == N - 1) {
                if (unused.count(x)) {
                    ans.push_back(x);
                    N--;
                    unused.erase(x);
                    counter.Decrement(A[x]);
                    continue;
                }
            }

            if (counter.Count[y] == N - 1) {
                if (unused.count(y)) {
                    ans.push_back(y);
                    N--;
                    unused.erase(y);
                    counter.Decrement(A[y]);
                    continue;
                }
            }
        }

        auto ite = unused.begin();

        if (0 < ans.size() and A[ans.back()] == *ite) ite++;
        ans.push_back(*ite);
        N--;
        counter.Decrement(A[*ite]);
        unused.erase(*ite);
    }

    vector<int> rest;
    rep(i, 0, N) {
        int x = *unused.begin();
        rest.push_back(x);
        unused.erase(x);
    }

    do {
        if (0 < ans.size() and A[ans.back()] == rest[0]) continue;
        bool ok = true;
        rep(i, 0, N - 1) if (A[rest[i]] == rest[i + 1]) ok = false;
        if (ok) {
            rep(i, 0, N) ans.push_back(rest[i]);
            break;
        }
    } while (next_permutation(all(rest)));

    if (ans.size() != originalN) {
        cout << -1 << endl;
        return;
    }

    rep(i, 0, originalN) {
        if(i) printf(" ");
        printf("%d", ans[i] + 1);
    }
    printf("\n");
}