AtCoder ABC 050 C - Lining Up (3Q, 緑色, 300 点)

今の時代だとあまり見かけないタイプの数学ゲー問題。

• 問題へのリンク

問題概要

人 を一列に並べる方法のうち、次の条件をすべて満たすものの個数を 1000000007 で割った余りを求めよ。

人 について、左側にいる人数と右側にいる人数の差が に等しい

制約

• 
• 

考えたこと

実は大半の について、答えは 0 通りなのではないかと思われた。というのも、各人の左側人数と右側人数との差分を小さい順にソートした値は、 のみに依存するのだ。

• 1 人のとき、
• 2 人のとき、
• 3 人のとき、
• 4 人のとき、
• 5 人のとき、
• 6 人のとき、
• 7 人のとき、
• ...

という具合だ。 が奇数のときは となり、 が偶数のときは となる。

よって、そもそも数列 を小さい順にソートしたとき、上記の通りになっていなければ 0 通りなのだ。以降、 をソートしたとき、 に応じて上記の通りになっているものとする。また、適宜人の番号を入れ替えることにより、 がソート済であるとしても一般性を失わない。

場合の数を求める

これ以降、 を小さい順にソートして考えることにする。たとえば の場合を考えよう。このとき、 であると考えてよい。このとき、場合の数は

• 人 がそれぞれ、左端にいくか、右端にいくか
• 人 がそれぞれ、左端から 2 番目にいくか、右端から 2 番目にいくか

によって、 通りが考えられる。

同様に考えて、一般の についても、人 がそれぞれ左端から i 番目にいくか、右端から i 番目にいくかをそれぞれ考慮することで、

通り

の場合が考えられる。

コード

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    deque<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    if (N % 2 == 0) {
        for (int i = 0; i < N; i += 2) {
            if (A[i] != i+1 || A[i+1] != i+1) {
                cout << 0 << endl;
                return 0;
            }
        }
    } else {
        if (A[0] != 0) {
            cout << 0 << endl;
            return 0;
        }
        for (int i = 1; i < N; i += 2) {
            if (A[i] != i+1 || A[i+1] != i+1) {
                cout << 0 << endl;
                return 0;
            }
        }
    }

    long long res = 1;
    for (int i = 0; i < N / 2; i++) {
        res = (res * 2) % MOD;
    }
    cout << res << endl;
}