ARC107 – B Quadruple

• 問題

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

• 解き方

与えられた式は

a + b – c – d = K

a + b – ( c + d ) = K

と変形できるので、a + b = x, c + d = yとすれば、制約よりxについての全探索をO(N)で済ませることが出来る。というのも、xを決めれば

( a + b = xとなる場合の数 ) * ( c + d = y = K – xとなる場合の数 )

という式によって求まるからである。

従って、a + b = xとなる場合の数を前計算しておく。

ここで、1≦ a, b ≦ N , a + b = Kである場合の数は以下のように求められる。

min( K – 1 , 2N + 1 – K )

これは a を 1 ~ N まで動かすことを考えて

K ≦ Nの時

(a, b) = (1, K – 1), (2, K – 2), …, (K – 1, 1)のK – 1通り

K > Nの時、pをK – p = Nとなる値として

(a, b) = (p, K – p), (p + 1, K – p – 1), …, (N, K – N)の2N + 1 – K通り

であることを考えると成立していることがわかる。

提出したコードはこの方法ではないので（汚く解いたので）載せません。