🔥

ARC 107 | B - Quadruple

2020/10/31に公開約1,300字

問題

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を求めてから、XY、それぞれに対して何通りあるか求め、それをかけ合わせればいい。

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

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;
}

参考

Discussion

ログインするとコメントできます