HHKB プログラミングコンテスト 2020 D - Squares

2年前の問題になりますが HHKB プログラミングコンテスト 2020のD - Squaresについてです。
atcoder.jp

問題としては1辺Nの正方形のグリッド中にA(1辺a),B(1辺b)の２つの正方形を重ならないような配置の総数を求めるというもの。

解説だと余事象から求めている(全体からA,Bが重なる方法を引く)のだけれど、別解で解いたので書いておきます。

包除原理で重ならない方法を直接的に計算する方法です。

2つの正方形が重ならないためには、x軸もしくはy軸に並行に引いた線でA、Bの正方形を分離できる必要があります。

上下に分けることができる配置を $X$ 、左右に分けることができる配置を $Y$ とすると、 $|X \cup Y| = |X|+|Y|-|X \cap Y|$ が答えです。
$|X \cap Y|$ はA,Bが対角の位置となるように十字に線を引くことができる配置です。

上下にABの順に並ぶものを $X_{AB}$ 、同様に左右にABの順に並ぶものを $Y_{AB}$ とします。
対称性から、以下が成り立ちます。

$\displaystyle |X| = |Y| = 2|X_{AB}| \\ |X \cap Y| = 4|X_{AB} \cap Y_{AB}|$

ということで最終的に以下の値を求めます。
$|X \cup Y| = 4|X_{AB}|-4|X_{AB} \cap Y_{AB}|$

Bの左端をx,上端をyとすると $|X_{AB}|, |X_{AB} \cap Y_{AB}|$ はそれぞれ以下の式で求めることができます。

$\displaystyle \begin{eqnarray} |X_{AB}| &=& \sum_{x=a}^{N-b} (N-a+1)(x-a+1)(N-b+1) \\ |X_{AB} \cap Y_{AB}| &=& \sum_{x=a}^{N-b}\sum_{y=a}^{N-b} (x-a+1)(y-a+1) \end{eqnarray}$

展開して整理すると以下のようになります。展開は Wolfram|Alpha: Computational Intelligence を使いました。

$\displaystyle \begin{eqnarray} \begin{split} |X \cup Y| &= 4|X_{AB}|-4|X_{AB} \cap Y_{AB}| \\ &=2(N-a-b+1)(N-a-b+2)(N-a+1)(N-b+1) \\ &\quad\quad-(N-a-b+1)^2(N-a-b+2)^2 \end{split} \end{eqnarray}$

$w=N-a-b+1$ とするとすっきりします。
$|X \cup Y| = 2w(w+1)(w+a)(w+b)-w^2(w+1)^2$

atcoder.jp