[AtCoder] ARC 107 B – Quadruple
問題
方針
\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません