Soohの嘆き呟き

競プロ解説記事をかくぞ。

Codeforces Educational Round 111 D - Excellent Arrays

  • 問題

codeforces.com

  • 解法

1-indexedで扱う. N は 配列のサイズである.

B_i = A_i - i と定義する.

A_i + A_j = i + j は B_i = -B_j と書き換えられる.

L <= A_i <= R だったので L - i <= B_i <= R - i である.

F(a)の最大値を達成するのはどんな時かを考えると,

B_i = x となる i が floor(N/2) 個あり、B_i = -x となる i が ceil(N/2) 個の時である.

これは帰納法により証明できるが省略する.

とはいえ、この問題では必ずF(a)がfloor(N/2) * ceil(N/2)になるかまだ分からない.

なぜなら、任意の x について B_i = x となるのが s_x 個で、B_i = -x となるのが t_x 個だったとして、s_x + t_x < N しかならない場合があるかもしれないからだ

正の整数を x として、x と -x のペアを作ることを考える.

以下の式変形では問題の制約による L <= 1, R >= N に気をつける.

B_i = x となる i の条件は L - i <= x <= R - i すなわち 1 <= i <= R - x

同様に B_i = -x となる i の条件は L - i <= -x <= R - i すなわち L + x <= i <= N

この2つの不等式から以下のことが言える.

R - x >= N かつ L + x <= 1 つまり 1 <= x <= min(R - N, 1 - L) の時は

「任意の i について、B_i = x にも B_i = -x にも出来る」が成立 - 1.

R - x <= 0 または L + x >= N + 1 つまり x > min(R, N + 1 - L) の時は、「任意の i について B_i = x に出来ない」または 「任意の i について B_i = -x に出来ない」が成立 - 2.

1 について

L < 1 かつ R > N の時は必ずこのような x が存在し、

この時の F(a) の最大値は floor(N/2) * ceil(N/2) であることが容易にわかる.

要は、B_i = x にする i の個数を K, -x にする i の個数を (N - K) とした時

K(N - K) を最大化したいので、K = N/2, (N+1)/2 が最適だからだ. (割り算は切り捨て)

よって、この範囲の各 x については B_i を x か -x にするかを選んで半々にすればよく、

どの i を選んで x にするかを決めればいいので二項係数で計算できる.

また、この場合の数は x に依らないのでまとめて計算できる.

2 について

x が 当該の範囲にある時は、(x, -x)というペアを作ることが出来ないのでこの範囲は無視しても良い事になる.

x <= min(R - N, 1 - L) の時と x > min(R, 1 - L + N)の時は 1, 2でカバーしたので、

min(R - N, 1 - L) < x <= min(R, 1 - L + N) を考えればよい.

1, 2のどちらでもないので、「任意の i について、B_i = x または B_i = -x の少なくとも一方にできる」

先程の考察から、

B_i = x に出来ない i は R - x < i <= N

B_i = -x に出来ない i は 1 <= i < L + x

B_i = x に出来ないような i については、B_i = -x にするしかない.

同様に B_i = -x に出来ないような i については B_i = x にする事になる.

残りの要素については、x か -x のどちらにも出来るので、うまく数合わせをしてF(a)の最大値を達成できるなら、それを答えに足し合わせれば良い.

L = 1 または R = N の場合は、1 において F(a) = floor(N/2) * ceil(N/2) になるとは言えなかったが、x がこの範囲にある場合は不等式を睨むと必ず達成できることも分かる.

この範囲はO(N)個しかないので、1つずつ考えても大丈夫である.

以上によって、この問題が解けた.

  • コード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;

const int MAX = 200001;
long long fact[MAX], finv[MAX], inv[MAX];

void Comb_init(){
    fact[0] = fact[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fact[i] = fact[i-1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod; 
    }
}
long long comb(long long n, long long k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fact[n] * finv[k] % mod * finv[n - k] % mod;
}

void add(ll &a, ll b){
    a += b;
    if(a >= mod) a -= mod;
}

void solve(){
    int n, l, r; 
    cin >> n >> l >> r;
    ll k = min(r - n, 1 - l);
    // 1 <= x <= k の範囲では、全ての i でB[i]が x にも -x にもできる
    ll ans = 0;
    // x になる i を n/2 or (n/2 + 1) 個になるように選ぶ
    add(ans, k * comb(n, n/2) % mod);
    if(n % 2 == 1) add(ans, k * comb(n, n/2+1) % mod);
    for(int x = k + 1; x <= min(r, 1 - l + n); x++){
        int a = max(0, n - (r - x)); // B[i] = -x にしか出来ない
        int b = max(0, l + x - 1);   // B[i] = x にしか出来ない
        int rem = n - a - b; // b[i] = x にも -x にもできる
        add(ans, comb(rem, n/2 - a));
        if(n % 2 == 1) add(ans, comb(rem, n/2 + 1 - a));
    }
    cout << ans << endl;
}

int main(){
    Comb_init();
    int t; cin >> t;
    while(t--) solve();
}