[AtCoder] ARC 107 B – Quadruple

2020年10月31日2020年12月12日

問題

方針

\( K \geq 0 \) として考えます。\( a + b = K + c + d \)  を満たす \( a, b, c, d \) の組み合わせを考えます。\( 2 \leq a + b \leq 2N \wedge 2 + K \leq K + c + d \leq K + 2N\) なので、

\[ 2 + K \leq a + b \leq 2N\]

の範囲で考えます。ここで、 \( a + b = n \) を満たす \( a, b \) の組み合わせの数を考えます。

\( 2 \leq n \leq N + 1 \) のとき

このとき、

\[(a, b) = (1, n – 1), (2, n – 2), \cdots , (n – 1, 1) \]

となるので、\( n – 1 \) 通りあります。

\( N + 2 \leq n \leq 2N \) のとき

このとき、

\[(a, b) = (N, n – N), (N – 1, n – N + 1), \cdots , (n – N, N) \]

となるので、\( 2N – n + 1 \) 通りあります。

\( a + b \) を固定

\( a + b = K + c + d \) において、\( a + b = n \) と固定したとき、\( c + d = n – K \) となるような \( c, d \) の組み合わせは上記同じように求められるので、\( f(n) \) を \( x + y = n \ (1 \leq x \leq N \wedge 1 \leq y \leq N)\) となるような \( x, y\) の組み合わせの個数とすると、

\[ \sum_{i = 2 + K}^{2N} f(i)f(i – K)\]

を求めれば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, K;

ll func(int n) {
    if (n >= N + 2) {
        return N - (n - N - 1);
    } else {
        return n - 1;
    }
}

int main() {
    cin >> N >> K;
    K = abs(K);
    ll v = 0;

    // a + b = c + d + K
    for (int i = K + 2; i <= 2 * N; i++) {
        v += func(i) * func(i - K);
    }
    cout << v << "\n";
    return 0;
}