Mister雑記

競プロやります。

AGC008-D 「K-th K」 (800)

割と素直な問題。

問題リンク

概要

整数 Nと長さ Nの数列 x_iが与えられるので、以下の条件を満たす長さ N^2の数列を存在すれば構築せよ。

  •  1 \sim Nがそれぞれちょうど N個ずつ含まれている。
  •  i番目の iは数列全体の左から x_i番目に位置する。

制約

  •  1 \leq N \leq 500
  •  x_iは全て異なる。

解説

 iについて x_iより前に i i - 1個埋めなければいけないので、これはできるだけ左側に埋めるべきとなる。

しかし x_i \gt x_jのとき、 iを先に埋めてしまったせいで 「 jの埋める場所がない(ただし i (x_j, x_i)にも埋められる)」という事態が発生する可能性がある。 これを防ぐには予め x_iについてソートして、貪欲に左から埋めていけばいい。

さて、仮に全部矛盾なく埋められたとして残りの N - i個の iは適当に埋めればいいか、というとそうではない(1敗)。 これらは逆に x_iより右側に埋めなければならないため、先程の操作を再び大小反転して行う必要がある。

実装例

#include <algorithm>
#include <iostream>
#include <tuple>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    pair<int, int> x[N];
    // (x_n, n)を保持
    
    for (int i = 0; i < N; ++i) {
        cin >> x[i].first;
        x[i].second = i + 1;
    }
    sort(x, x + N);
    // x_nでソート

    int a[N * N + 1], now = 0;
    fill(a, a + N * N + 1, -1);
    // aは1-indexed 埋まってなければ-1
    // 今a[now]まで埋まっている

    // x_nの小さい方から埋めていく
    for (int i = 0; i < N; ++i) {
        int idx, n;
        tie(idx, n) = x[i];
        a[idx] = n;

        // -1の箇所にnを左から詰めていく
        for (int j = 0; j < n - 1; ++j) {
            while (true) {
                if (a[++now] < 0) {
                    a[now] = n;
                    break;
                }
            }
        }

        // idxより左側にn-1個埋められなかったらアウト
        if (now > idx) {
            cout << "No" << endl;
            return 0;
        }
    }

    // 大小反転して同じことをする
    now = N * N + 1;
    for (int i = N - 1; i >= 0; --i) {
        int idx, n;
        tie(idx, n) = x[i];

        for (int j = n; j < N; ++j) {
            while (true) {
                if (a[--now] < 0) {
                    a[now] = n;
                    break;
                }
            }
        }

        if (now < idx) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    for (int i = 1; i <= N * N; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

感想

  • AGC-Dにしては簡単だった。
  • 詰めが甘くて1WA吐いたのは惜しいところ。