ARC 107 | B - Quadruple

問題

https://atcoder.jp/contests/arc107/tasks/arc107_b

考えたこと

式を変形する。

$$a+b-c-d=K$$

$$(a+b)-(c+d)=K \tag{1}$$

$$(a+b) = K + (c+d) \tag{2}$$

条件 $1 \leq a,b,c,d \leq N$ と $-2(N-1) \leq K \leq 2(N-1)$ より $(1)$ は答えが存在するので整数 $(a,b,c,d)$ の組は最低1個ある。

$(2)$ は $X = (a+b)$ 、 $Y = (c+d)$ と置き換えると以下である。

$$X = K + Y$$

$K$は与えられているので$X$を定めると$Y$が求められる。
よってすべての$2 \leq X \leq 2N$に対して$Y$を求めてから、$X$、$Y$、それぞれに対して何通りあるか求め、それをかけ合わせればいい。

$X = a + b$かつ$X=2,3,\ldots,2N$の$a$と$b$の組み合わせの数は以下で求められる。

$$min(X - 1, 2N + 1 - X)$$

たとえば$N=3$のときは以下のようになる。

X	$(a,b)$の組み合わせ
2	$(1,1)$
3	$(1,2),(2,1)$
4	$(1,3),(2,2),(3,1)$
5	$(2,3),(3,2)$
6	$(3,3)$

コード

実装時のTips

• 条件の範囲外のYはあらかじめ除いておく

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n, k;
  cin >> n >> k;
  ll ans = 0;
  // x = a + b, y = c + d
  for (ll x = 2; x <= 2 * n; x++) {
    ll y = x - k;
    if (y < 2 || 2 * n < y) {
      continue;
    }
    ans += min(x - 1, 2 * n + 1 - x) * min(y - 1, 2 * n + 1 - y);
  }

  cout << ans << endl;
}

参考

• https://atcoder.jp/contests/arc107/editorial/262