問題概要

長さ $ N (\leq 500) $ の数列 $ x$ が与えられるとき，次の 2 つの条件を満たす数列 $ a$ が与えられるか判定し，与えられるならば 1 つ構成せよ．

$ a$ の長さは $ N^2$であり，整数 $ 1, 2, \cdots, N$をちょうど $ N$ 個ずつ含む．
各 $ 1 \leq i \leq N$ について，$ a$ に含まれる整数 $ i$ のうち左から $ i$ 番目に位置するものは、$ a$ 全体では左から $ x_i$ 番目に位置する。

解法概要

以下，この例を使って解法を考える．また，いつもの 0-indexed ではなく 1-indexed で考える．

f:id:noimin:20190416134638p:plain

まずは Yes/No 判定．これは取りうる全てのインデックス $ 1 \leq i \leq N$ について，「あるインデックス i よりも絶対に前にないといけない要素数が，iを超えてしまう」または「あるインデックス i よりも絶対に後にないといけない要素数が N²-i+1 を超えてしまう」と No となる．そうでなければ，条件に当てはまるような数列 a が存在する．

a の構成の仕方は以下の 3 つに分けて考える．

整数 $ i$ のうち前から $ i$ 番目に位置するもの (入力の $ x_i$ ．上の図で言うインデックス 3, 5, 8)
整数 $ i$ のうち前から $ (i-1)$ 番目以前に位置するもの (上の図で言うインデックス 1, 2, 4)
整数 $ i$ のうち前から $ (i+1)$ 番目以降に位置するもの (上の図で言うインデックス 6, 7, 9)

1 は入力から直接与えられるので，$ x_i$ の通りに配置すれば良い．

2 は，各$ i$ について，$ x_i$ より前に配置しなければならない．あらかじめ Yes/No 判定でそもそも条件に当てはまる数列 a が構成できない場合を弾いているとすると，数列 a を前から順番に見ていき，埋まっていないインデックスについて， $ x_i$ の小さい $ i$ から貪欲に埋めていけば良い．2 に当てはまる要素というのはインデックス $ x_i$ よりも前に消費していなければならないので， $ x_i$ が小さいものほど入れられる場所が少ないためである．上の図の場合，$ i = 3$ から順番に消費していくことになる．ただし 2 の段階で埋めるべきなのは各 $ i$ について $ (i-1)$ 個ぶんであることに気をつける．

3 は 2 とほぼ同じ．2 とは逆で $ x_i$ が大きいほど入れられる場所が少ないので， $ x_i$ の小さい $ i$ については早めに消費して損はない．3 で配置するべきは， 1 と 2 で配置されていない残りの各 $ i$ について $ (i-1)$ 個ぶんであることに気をつける．

ソースコード

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

typedef pair<int, int> Pii;

const int N_MAX = 500;

vector<Pii> v(N_MAX+1, Pii(0, 0));
 
bool check(int n) {
    // それぞれ [1, i], [i, n] に含まれるべきことが確定している要素の数
    vector<int> cnt_l(n*n+1, 0), cnt_r(n*n+2, 0);
    for(int i=1;i<=n;++i) {
        cnt_l[v[i].first] += i;
        cnt_r[v[i].first] += n-i+1;
    }
    for(int i=1;i<=n*n;++i) cnt_l[i] += cnt_l[i-1];
    for(int i=n*n;i>=1;--i) cnt_r[i] += cnt_r[i+1];

    for(int i=1;i<=n*n;++i) {
        if(i < cnt_l[i] || n*n-i+1 < cnt_r[i]) {
            return false;
        }
    }
    return true;
}

vector<int> construct(int n) {
    vector<int> ret(n*n+1, 0);
    sort(v.begin(), v.begin()+n+1);

    // x_i にしたがって数値を入れる
    for(int j=1;j<=n;++j) {
        int idx = v[j].first;
        int num = v[j].second;
        ret[idx] = num;
    }

    // x_i で指定されたインデックスより前の部分を埋める
    int j = 1;
    int num = v[j].second;
    int num_cnt = num - 1;
    for(int i=1;i<=n*n;++i) {
        if(ret[i]) continue;
        while(j < n && !num_cnt) {
            ++j;
            num = v[j].second;
            num_cnt = num - 1;
        }
        if(j == n && !num_cnt) break;
        ret[i] = num;
        --num_cnt;
    }
    
    // x_i で指定されたインデックスより後の部分を埋める
    j = 1;
    num = v[j].second;
    num_cnt = n - num;
    for(int i=1;i<=n*n;++i) {
        if(ret[i]) continue;
        while(j < n && !num_cnt) {
            ++j;
            num = v[j].second;
            num_cnt = n - num;
        }
        if(j == n && !num_cnt) break;
        ret[i] = num;
        --num_cnt;
    }

    return ret;
}

int main() {
    int n, x;
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> x;
        v[i] = {x, i};
    }

    if(check(n)) {
        cout << "Yes" << endl;
        vector<int> ans = construct(n);
        for(int i=1;i<=n*n;++i) {
            cout << ans[i] << " ";
        }
        cout << endl;
    } else {
        cout << "No" << endl;
    }

}

所感

バタフライシーカーにはまりすぎて競プロすら手につかなくなっていたところ，主人公と同じ名前の問題を見つけたので解きました．圭介くん大好きなので自力 AC できて嬉しいです．プレイ可能な年齢の方はぜひプレイしてみてください (ダイナミック布教)

競プロの実力は完全に鈍っているので天下一コンまでに少しでも取り戻さなければ．

NoiminのNoise

AtCoder Grand Contest 008 D - K-th K

問題概要

解法概要

ソースコード

所感