問題概要

正の整数 $N, x$ があたえられる。
条件を満たすような順列 $1, 2, \dots, 2N-1$ を求めたい。いま、この順列を下図左のようにピラミッドの最底辺に書き込む。各マスに対して

そのマスの直下にある 3 マスの中央値を書き込む

という操作を下から順に行ったとき、頂上には $x$ が書き込まれた。このようなことが起こる順列を一つ求めよ。存在しない場合はその旨を報告せよ。

f:id:drken1215:20190209151314p:plain

制約

$2 \le N \le 10^{5}$
$1 \le x \le 2N-1$

考えたこと

こういうのはとにかく実験してみるのが良さそう。そして実験することで本質的な構造として、ピラミッドのどこかに

(a 未満) - (a) - (a 以上)

という横並びがあったら、それより上はすべて

(a 未満) - (a) - (a 以上)

という状態のままずっと上まで登っていくということがわかる。したがって、 $x = 1, 2N-1$ の場合は自明にダメだが、それ以外の $x$ であれば

... $1, x, 2N-1$ , ...

という風に、真ん中に $x$ をおいて、左に 1、右に $2N-1$ としておけば、からなず頂上が $x$ になる。

#include <iostream>
#include <vector>
using namespace std;

void solve(int N, int x) {
    if (x <= 1 || x >= N*2-1) {
        cout << "No" << endl;
        return;
    }

    cout << "Yes" << endl;
    vector<int> res(N*2-1, -1);
    res[N-2] = 1;
    res[N-1] = x;
    res[N] = N*2-1;
    int iter = 0;
    for (int v = 2; v < N*2-1; ++v) {
        if (v == x) continue;
        while (res[iter] != -1) ++iter;
        res[iter] = v;
    }
    for (auto v : res) cout << v << endl;
}

int main() {
    int N, x;
    cin >> N >> x;
    solve(N, x);
}

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

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

AtCoder AGC 006 B - Median Pyramid Easy (青色, 400 点)

問題概要

制約

考えたこと