ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

パソコン甲子園2019本選 (AOJ 0426) 三角形の個数の和

AOJ プログラミング競技プログラミング

お題箱より。

Aizu Online Judge

解いてなかったのでこのリクエストを見て解きました。

解法

言い換えを重ねる

全ての点の個数を $N = (H+1)(W+1)$ と表記することにします。

「全ての点集合について、その集合に含まれる三角形を数えて合計する」を、「全ての三角形をなす3点の組み合わせについて、それを含む点集合を数えて合計する」と言い換えます。

そうすると3点の選び方に依らず、それを含む集合は「その3点は必ず含み、残りの $N-3$ 点について含む/含まないを自由に選ぶ」ことになるので $2^{N-3}$ 通りあります。

そのため、三角形をなす異なる3点の選び方の数が分かれば良いです。その代わりに三角形をなさない（つまり一直線上にある）異なる3点の選び方の数を求めて、制限を設けない異なる3点の選び方の数 $_{N}C_{3}$ から引くことにします。

一直線上にある3点の選び方

というわけで求めるものは、一直線上にある異なる3点の選び方の数となりました。これの求め方ですが、両端になっている2点間の $y$ 座標・ $x$ 座標の差の組み合わせを全探索します。これらをそれぞれ $i, j$ とします。（ $i = j = 0$ は除外）

このとき反転させて同じになるものは重複しないように注意する必要があります。1つの手段としては、「 $i \ge 0$ かつ $j \ge 0$ の範囲を探索し、 $i \gt 0$ かつ $j \gt 0$ のものについては傾き反転のぶん2倍する」などとすると良いです。

$(i, j)$ を固定したら、まず領域内で両端として取れる場所が何通りあるかを計算します。これは $(H+1-i)(W+1-j)$ になります。

その上で、間に位置する3点目が何通り取れるかを計算します。これは $\gcd(i, j)-1$ になります。例えば $(i, j) = (4, 8)$ の場合、間の点は $(1, 2), (2, 3), (3, 6)$ の位置に相当する3通りです。

f:id:betrue12:20200502163308p:plain

これで、一直線上にある異なる3点の選び方の数を求めることができました。あとはこれまでの解説を巻き戻るように計算していけば、答えを求めることができます。

ACコード

Aizu Online Judge