ARC071 D ### / 井井井

atcoder.jp

所見

一度解説読んでこんなん(二回目の式変形)どうやって思いつくねん(絶望)となっていたが、思ったより地続きの考察で解ける

問題概要

x軸に平行な直線m本とy軸に平行な直線n本が与えられる。それらに囲まれる長方形すべての面積を1000000007で割った余りを求めよ。

取った方針

考察をして、ある長方形が数えられる回数は上下左右にある直線の本数をかけたものであることが分かる。(理由: ある長方形Aを含む長方形を作るために直線を選ぶとすると、長方形Aの上側にある直線の選び方はその長方形の上側にある直線の本数に等しいため*上下左右)
しかし、これではすべての長方形が数えられる回数を計算するのにO(N²)かかり、間に合わずに死亡
解説を読んで、x軸とy軸を個別に計算することが可能だと知る。
これは、長方形の面積の計算において、縦の長さを固定して横の長さの総和を計算してから縦の長さを掛けることに等しい。

ある区間xがいくつの長方形に含まれるかは"長方形が数えられる回数"と同じように求まる。
気持ち: ある区間xを含む区間の数は、その区間より左にある点から一つ選ぶ場合の数 * その区間より右にある点から一つ選ぶ場合の数である

写真がデカい
よって、縦の長さの総和と横の長さの総和が求まるので、掛けると答えが得られる、O(n+m)

正しい方針

同上、でもないけれど(数式を立てて式変形している)、やってることは本質的には同じはず

得られた知見

• 含まれる長方形の個数 -> 場合の数っぽく計算できる
• 式をくくると見通しが良くなることがある
• m次元->1次元×mにしてO(N^m)をO(N*m)にするテク(頻出っぽい)

  解くのに必要な要素

• 式変形 or m次元->1次元×mにしてO(N^m)をO(N*m)にするテク

周辺調査によって得られた知見

特になし