AtCoder Regular Contest 052 B. 円錐:解き方と解答例
昨日(4/30)、AtCoder (アットコーダー)にてAtCoder Regular Contest 052 (ARC 052)が開催されました。この記事では、このコンテストで出され、私が解けた問題の一つである、B: 円錐 - AtCoder Regular Contest 052 | AtCoderという問題について、学習の記録を兼ねて解き方と解答例を示しておきます。
問題の趣旨*1
N個の円錐が、互いに重なり合わないようにxyz空間に存在する。円錐の底面の中心のx座標、底面の半径、高さはそれぞれである。どの円錐の底面もyz平面に平行であり、すべてのiについて円錐の頂点のx座標はと表される。また、の内部をとする。いま、Q個の整数の二つ組が与えられる。各二つ組について、が成り立つ。このときに、各に対し、二平面で挟まれる領域との共通部分の体積を求めよ。
方針*2
領域は(それがでなければ)円錐台(とする)の内部です。この領域の体積をとすると、題意からとなります。よって、各二つ組ごとにを計算し、その総和を求めればよいでしょう。この方法では時間計算量がとなりますが、制約条件からこれでも間に合います。なお、ほかの方法として、公式の解説のように累積和を用いる方法もありますが、ここでは扱いません。
図のように両領域のありうる位置関係をまずは示してみましょう。赤い帯が領域を、青い三角形が領域を、それらの重なりがを表します。場合(4)および(5)ではです。そのほかの場合(1)-(3)では、円錐台の上底面、下底面のx座標がそれぞれとなります。ただし、です。
続いて、各を図示し、各の求め方を考えましょう。図のように長さや角度を定義します。いま、であり、およびが成り立ちます。あとは、円錐台の体積の公式から*3、が成り立つことを利用すればよいでしょう。
感想
一見、何やら難しそうな問題に見えましたが、問題文の状況を図示することで、解法がわかってきました。見た目だけで安易にあきらめず、少し踏ん張ってみることの重要性を感じました。
*1:以下では領域についてややあいまいな扱いをしていますが、本問を解くうえでは特に差し支えないと思われます。
*2:やや記述が複雑なので、下のコードとあわせて読んだ方がわかりやすいかもしれません。
*3:wikipedia:円錐台によります。