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

atcoder.jp

400点にしては難しいと感じた問題だった。

まず上下左右の自由度は独立して考えられること、及び全体から重なっている場合の組み合わせを引けば良いことに気づくのが重要。X軸方向にA, Bが重なっているとき、AとBの重なる幅 について全探索することを考えると、 のときはAまたはBの大きいほうが小さい方を完全に含んでおり、そうでないときは重なり方が2通りしかないことがわかる。いずれも幅 の間で動かせる範囲だけ自由度があるので結局いずれの場合もの一次式で表されることがわかる。この一次式の和なので、結局等差数列の公式を使って で計算できる。

あとはY軸方向は結局X軸と同じなので平方をとってやり、AとBのあり得るパターン全てから引けばよい。全体でも (テストケースの数は除く)。