https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_d

解説

https://atcoder.jp/contests/hhkb2020/submissions/17318367

色々な考察が必要で、方針もたくさん見えるような問題。

引くべき方針1「余事象」

今回は余事象を考えるとすっきりする。
つまり、赤い正方形と青い正方形が重なる方法の数を数えて全体から引くことで答えを導こう。

まず、全体の方法の数を考える。
青い正方形を置ける場所は、正方形の左下をどの座標に置くかで(N - A + 1)²通りとなる。
同様に、赤い正方形を置ける場所は、正方形の左下をどの座標に置くかで(N - B + 1)²通りとなる。
よって、全体の方法の数は(N - A + 1)² × (N - B + 1)²通りである。

余事象部分をいかに計算するか

2つの正方形がかぶっている方法の数をいかに計算するかであるが、実験してみると、とても計算が大変そうに見える。
そこで、問題が簡単化できないかと画策する。
AとBの大小関係が気になるが、特にAとBが入れ替わっても場合の数的には問題がないので、A≦Bと固定して考えることにする。
さて、ここからが本番であるが、以下の性質を見つけてくる必要がある。

引くべき方針2「縦横独立に考える」

(2つの正方形がかぶっている方法の数) = (数直線[0,N]の範囲に長さAの棒と長さBの棒をかぶって配置する方法の数)²

つまりは、何が言いたいかというと、2つの正方形がかぶっている方法の数は、縦と横で独立に考えることができるということ。
2つの正方形がかぶっている状況をよくよく見てみると、x軸でも線分がかぶっていて、y軸でも線分がかぶっている。
更によくよく見てみると、x軸でも線分がかぶっていて、かつ、y軸でも線分がかぶっているなら、2つの正方形はかぶっているといえる。
つまり、

(x軸で線分がかぶっている方法の数)×(y軸で線分がかぶっている方法の数)=(2つの正方形がかぶっている方法の数)

となる。ここで、x軸とy軸はどちらも正方形で同じ長さ、同じ状況なので、同じ数となるので、最終的に2乗になって

(2つの正方形がかぶっている方法の数) = (数直線[0,N]の範囲に長さAの棒と長さBの棒をかぶって配置する方法の数)²

となる。

最も小さい問題

これで問題を最小化できた。
「数直線[0,N]の範囲に長さAの棒と長さBの棒をかぶって配置する方法の数」が分かれば答えになる。
これを解くのも厄介だが、場合分けして解くことにしよう。

Bの中にAが完全に包含されている
Bの末尾とAの先頭がかぶっている
Aの末尾とBの先頭がかぶっている

このうち、2と3は、左右をひっくり返せば同じ状況になるので、同じ組み合わせとなる。
よって、1と2が分かればいい。

1. Bの中にAが完全に包含されている inner

これは、Bの場所の組み合わせと、その中でAがどこにあるかの組み合わせの掛け合わせである。
この2つは独立である。
Bの場所の組み合わせはN-B+1
その中でAがどこにあるかの組み合わせはB-A+1
その2つの積が組合せとあんる。

2. Bの末尾とAの先頭がかぶっている outer

Bの線分を一番右に配置すると、Aが置ける場所は0通り
1つ左に動かすと、Aが置ける場所は1通り
…
A-2つ左に動かすと、Aが置ける場所はA-2通り
A-1つ左に動かすと、Aが置ける場所はA-1通り
Aつ左に動かすと、Aが置ける場所はA-1通り
…

とこのようになる。
なので、1+2+...+(A-2)+(A-1)+...+(A-1)となる。
前半の1+2+...+(A-2)は等差数列の和で計算すればいいし、
(A-1)+...+(A-1)は(N-A-B+2)個分あるので、積をとればいい。

これで2も計算できた。

最終的には？

(N - A + 1)² × (N - B + 1)² - (inner+outer×2)²

が答え。

ll N, A, B;
//---------------------------------------------------------------------------------------------------
int solve() {
    cin >> N >> A >> B;
    if (A > B) swap(A, B);

    if (N < A + B) return 0;

    mint allCombination = mint(N - A + 1) * mint(N - A + 1) * mint(N - B + 1) * mint(N - B + 1);
    mint inner = mint(N - B + 1) * mint(B - A + 1);
    mint outer = (mint(0) + mint(A - 2)) * mint(A - 2 + 1) / 2 + mint(A - 1) * mint(N - A - B + 2);
    mint ans = allCombination - (inner + outer * 2) * (inner + outer * 2);
    return ans.get();
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) printf("%d\n", solve());
}

はまやんはまやんはまやん

hamayanhamayan's blog

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

解説