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

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

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

これの Easy バージョン。すごく楽しくて好き!!!!!

  • Easy:操作の結果が所望になる入力を求める逆問題
  • Hard:操作に入力を与えた結果を求める問題

という風になっていて、普通「操作の結果を求めるだけ」の問題の方が絶対簡単なことが多いのに、Easy と Hard でその関係性が逆というのが面白すぎる。

drken1215.hatenablog.com

問題へのリンク

問題概要

正の整数  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);
}