AGC 006 B - 備忘録

さっきこの問題を解きました。

agc006.contest.atcoder.jp

n段のピラミッドの最も下の段のブロックに1~2 * n - 1の数字が一回ずつ書かれています。そこから上の段のブロックについては、自分のブロックの真下、左下、右下の中央値が書かれます。今、頂点の値xが与えられています。頂点の値はxかつ条件を満たすような最も下の段のブロックの記入方法があるか答えなさい。存在する場合は、その一例を
答えなさい。という問題です。

ある2つの連続したブロックについて、書かれている数字が同じであればそれらの上の2つのブロックもまた同じ数字が書かれる、ということを利用します。これにより、下から二番目の段についてその段の中央とその隣にxが書かれていれば頂点の値はxになります。したがって下から二番目の段がこうなるような記入方法を考えればいいです。
ここで、xは2以上2 * n - 2以下でないといけません。なぜならば、1と2 * n - 1は一番下の段から下から二番目の段に上がるときにどうあがいても消えてしまうからです。よってこのばあいは"No"を出力して終了します。

回答はこんな感じ。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int main()
    {
        int n, x;
        cin >> n >> x;
        if(n == 2){
            if(x == 2) cout << "Yes" << endl << 1 << endl << 2 << endl << 3 << endl;
            else cout << "No" << endl;
            return 0;
        }
        if(x == 1 || x == 2 * n - 1){
            cout << "No" << endl;
            return 0;
        }
        cout << "Yes" << endl;
        int ans[200001];
        for(int i = 0; i < 2 * n; i++){
            ans[i] = i;
        }
        swap(ans[n], ans[x]);
        if(x > n){
            if(ans[n - 1] > x - 1) swap(ans[n - 1], ans[x - 1]);
            if(ans[n + 1] != x + 1) swap(ans[n + 1], ans[x + 1]);
            if(ans[n + 2] > x - 2) swap(ans[n + 2], ans[x - 2]);
        } else if(x < n) {
            if(ans[n - 1] < x + 1) swap(ans[n - 1], ans[x + 1]);
            if(ans[n + 1] != x - 1) swap(ans[n + 1], ans[x - 1]);
            if(ans[n + 2] < x + 2) swap(ans[n + 2], ans[x + 2]);
        }
        for(int i = 1; i < 2 * n; i++){
            cout << ans[i] << endl;
        }
        return 0;
    }

まずxを中央に来るようにswapします。
次に隣に来る数を考えないといけません。このとき、自分より大きい値の数の方が、小さい値の数より多い場合とその逆の場合に分けて考えます。なぜならば、たとえばx = 2 * n - 2かつ隣に2 * n - 3が来るとしたとき、その二つのブロックの両脇には2 * n - 1が来なければxが選ばれません。しかし、これでは2 * n - 1が二回出現することになり条件を満たしません。一方隣に2 * n - 1が来るとしたとき、その二つのブロックの両脇には2 * n - 3以下の値であればどれでもいいわけです。このような場合に備えて場合分けした、というわけです。あとは、両隣に来る値を適当に書き換えればオッケーです。大体こんな感じ。

隣に来るブロックがx + 1であれば、その二つのブロックの左側にはx - 1以下の、右側にはx - 2以下のブロックが来るようにする

隣に来るブロックがx - 1であれば、その二つのブロックの左側にはx + 1以上の、右側にはx + 2以上のブロックが来るようにする

~~正直にいうとここはテストケースから判断して適当に書きました。~~
一発で通ったのでとても気持ちいい。