ながめも

競技プログラミングについて

トップ > AtCoder > AtCoder Beginner Contest 058 ABC058 D - 井井井

AtCoder Beginner Contest 058 ABC058 D - 井井井

AtCoder ABC 数え上げ 主客転倒

問題へのリンク

解説

問題の言い換え

数え上げの典型として、「問われている対象を別のものの数え上げで考える」という方針があります。今回もその例に漏れず、出てくる長方形全てではなく、「長方形の最小単位がそれぞれ何回出てくるかを数え上げる」という方針を取りたくなります。

直線 x_iと x_{i+1}、 y_jと y_{j+1}に囲まれた長方形の面積を S_{i,j}、登場回数を C_{i,j}とすると、求める値は

\displaystyle{ \sum_{i = 1}^{N-1}\sum_{j = 1}^{M-1} S_{i,j} \times C_{i,j} }

と言い換えられます。

このままでは、たとえ Sや Cが適切に前計算できたとしても計算量が \Theta(NM)になってしまいます。

面積Sの計算

面積 Sは簡単に計算できて、

便宜上 xx_{i} = x_{i+1} - x_{i}、 yy_{j} = y_{j+1} - y_{j}とおくと、

S_{i,j} = xx_{i} \times yy_{j}

となります。

登場回数Cの数え上げ ~ xとyは独立 ~

登場回数の数え上げですが、ある長方形は直線を x側から 2つ、 y側から 2つ選択することに対応することを考えると、 x側と y側は独立に選ぶことになります。

xについて、 i番目の区間が含まれるように二直線を選ぶ場合の数は i \times (N - i)となります。 yについても同様です。

便宜上 a_{i} = i \times (N - i)、 b_{j} = j \times (N - j)とおくと、

C_{i,j} = a_{i} \times b_{j}

となります。

シグマの計算

以上で Sと Cが立式できたので、答えに入れてみると

\displaystyle{ \sum_{i = 1}^{N-1}\sum_{j = 1}^{M-1} S_{i,j} \times C_{i,j} }

\displaystyle{ = \sum_{i = 1}^{N-1}\sum_{j = 1}^{M-1} xx_{i} \times yy_{j} \times a_{i} \times b_{j} }

\displaystyle{ = \sum_{i = 1}^{N-1}xx_{i} \times a_{i} \sum_{j = 1}^{M-1} yy_{j} \times b_{j} }

よって \Theta(N + M)の前計算で解くことができました。

実装

提出へのリンク

struct mint {
    /* 省略 */
};
int main() {

    ll N, M;
    cin >> N >> M;
    vector<ll> x(N), y(M);
    rep(i,N)cin >> x[i];
    rep(i,M)cin >> y[i];

    vector<mint> xx(N-1), yy(M-1);
    rep(i,N-1)xx[i] = x[i+1] - x[i];
    rep(i,M-1)yy[i] = y[i+1] - y[i];
    
    vector<mint> a(N-1), b(M-1);
    rep(i,N-1) a[i] = mint(i+1) * mint(N - i - 1);
    rep(i,M-1) b[i] = mint(i+1) * mint(M - i - 1);

    mint sum[] = {0,0};
    rep(i,N-1)sum[0] += xx[i] * a[i];
    rep(j,M-1)sum[1] += yy[j] * b[j];
    mint ans = sum[0] * sum[1];
    cout << ans << endl;
}