けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

第6回 ドワンゴからの挑戦状 予選 D - Arrangement (橙色, 800 点)

AtCoder AtCoder800点 Greedy 順列を題材とした問題 数学的帰納法に基づく考察 小さいところで帳尻を合わせる 辞書順 橙色diff 順列の最適化問題 Greedy:辞書順最小を求める

今回は惨敗したけど次回また頑張りたい！！！

問題へのリンク

問題概要

1, 2, \dots, N の順列であって、以下の条件を満たすもののうち、辞書順最小のものを求めよ。存在しない場合は -1 を出力せよ。

  • i (=1, 2, \dots, N) の右隣の値は a_{i} ではない

制約

  • 1 \le N \le 10^{5}

考えたこと

色々手を動かしてみると、条件を満たすものが存在しないことは、そうそうない気がしてくる。1 個 1 個の条件はゆるくて、 N! 通りすべての可能性を潰すことなどできなさそうである。 N = 2 の場合だけ、存在しないことがありうる (サンプルにある)。

そして、ほとんどの場合、

  • まだ使っていないもののうち、現在の最後尾の右に来れるやつのうち、最小のものを選ぶ

という感じの Greedy で良さそうに思える。しかしこれには例外があって、たとえば N = 7 として a = (7, 7, 7, 7, 7, 7, 1) とかの場合、先頭に 7 以外を置いてしまうと詰む。

修正として、残り 3 個になるまでは

v を貪欲に選んだ要素とする。ここで v を採用してしまうと、残ってるものがすべて a_{v} を嫌っている状態になったら、 v の代わりに a_{v} を採用する

という風にすれば OK。 v を選んでしまうと a_{v} を置けなくなってしまうのだが、その瞬間に a_{v} を選べば大丈夫。ただし最後の 3 個あたりは微妙なので最後の方は全探索する。ちゃんとした証明は editorial にあって、厳密には、以下のことを残りの要素数に関する帰納法で示せるっぽい。

要素 v を選んだときに、残りの要素が 3 以上とする。このとき、残りの要素の中に a_{v} を嫌っていないものが存在するならば、残りの要素で条件を満たすようにできる

迷走したこと

以下のことを心配してしまった。実際はそんなことは起こらない。 v を採用したときに、新たに「詰み」を増やしてしまう可能性があるのは a_{v} のみ。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

int N;
vector<int> p;
vector<set<int>> ip;

bool check(const vector<int> &res) {
    for (int i = 0; i + 1 < res.size(); ++i) {
        if (res[i+1] == p[res[i]]) return false;
    }
    return true;
}

void last(vector<int> &res, vector<int> &rem) {
    do {
        if (res.size() > 0 && rem[0] == p[res.back()]) continue;
        if (check(rem)) {
            for (int i = 0; i < res.size(); ++i) cout << res[i] + 1 << " ";
            for (int i = 0; i < rem.size(); ++i) cout << rem[i] + 1 << " ";
            cout << endl;
            return;
        }
    } while (next_permutation(rem.begin(), rem.end()));

    cout << -1 << endl;
    return;
}

const int NOKORI = 5;
void solve() {
    if (N <= NOKORI) {
        vector<int> res, rem(N);
        for (int i = 0; i < N; ++i) rem[i] = i;
        last(res, rem);
        return;
    }

    vector<int> res;
    set<int> rem;
    for (int i = 0; i < N; ++i) rem.insert(i);
    while (N - (int)res.size() > NOKORI) {
        int dame = -1;
        if (res.size() > 0) dame = p[res.back()];

        // とりあえず Greedy に
        int ne = -1;
        for (auto it : rem) {
            if (it == dame) continue;
            ne = it;
            break;
        }

        // ne を選んでしまうと詰むときは取り替える
        if (ip[p[ne]].size() + res.size() == N-1) {
            ne = p[ne];
        }

        // ne を選ぶ
        res.push_back(ne);
        rem.erase(ne);
        ip[p[ne]].erase(ne);
    }
    vector<int> vrem;
    for (int i = 0; i < N; ++i) if (rem.count(i)) vrem.push_back(i);
    last(res, vrem);
}

int main() {
    while (cin >> N) {
        p.resize(N);
        ip.assign(N, set<int>());
        for (int i = 0; i < N; ++i) {
            cin >> p[i];
            --p[i];
            ip[p[i]].insert(i);
        }
        solve();
    }
}