はむ吉(のんびり)の練習ノート

プログラミングとことばに関する話題を中心に,思いついたこと,試してみたこと,学んだことを,覚え書きを兼ねてまとめます.その際に役立った,技術書,参考書,辞書,機器などの紹介も行います.

AtCoder Regular Contest 052 B. 円錐:解き方と解答例

昨日(4/30)、AtCoder (アットコーダー)にてAtCoder Regular Contest 052 (ARC 052)が開催されました。この記事では、このコンテストで出され、私が解けた問題の一つである、B: 円錐 - AtCoder Regular Contest 052 | AtCoderという問題について、学習の記録を兼ねて解き方と解答例を示しておきます。

問題の趣旨*1

N個の円錐\mathrm{C}_1, \mathrm{C}_2, \cdots, \mathrm{C}_Nが、互いに重なり合わないようにxyz空間に存在する。円錐\mathrm{C}_iの底面の中心のx座標、底面の半径、高さはそれぞれx_{\mathrm{bottom}, i}, R_i, H_iである。どの円錐の底面もyz平面に平行であり、すべてのiについて円錐\mathrm{C}_iの頂点のx座標はx_{\mathrm{top}, i} = x_{\mathrm{bottom}, i} + H_iと表される。また、\mathrm{C}_iの内部をD_iとする。いま、Q個の整数の二つ組(A_1, B_1), (A_2, B_2), \cdots, (A_Q, B_Q)が与えられる。各二つ組(A_j, B_j)について、A_j \le B_jが成り立つ。このときに、各(A_j, B_j)に対し、二平面x=A_j, x=B_jで挟まれる領域\Omega_j\bigcup _{i = 1} ^{N} D_iの共通部分の体積V_jを求めよ。

方針*2

領域\Omega_j \cap D_iは(それが\emptysetでなければ)円錐台(\mathrm{F}_{i,j}とする)の内部です。この領域の体積をW_{i, j}とすると、題意からV_j = \sum _i W_{i, j} となります。よって、各二つ組ごとに\{W_{i, j}\}_{i=1}^Nを計算し、その総和を求めればよいでしょう。この方法では時間計算量がO(NQ)となりますが、制約条件からこれでも間に合います。なお、ほかの方法として、公式の解説のように累積和を用いる方法もありますが、ここでは扱いません。

図のように両領域 \Omega_j, D_iのありうる位置関係をまずは示してみましょう。赤い帯が領域\Omega_jを、青い三角形が領域D_iを、それらの重なりが\Omega_j \cap D_iを表します。場合(4)および(5)ではW_{i, j} = 0です。そのほかの場合(1)-(3)では、円錐台\mathrm{F}_{i,j}の上底面、下底面のx座標がそれぞれx_{\mathrm{ub}, i, j}, x_{\mathrm{lb}, i, j}となります。ただし、x_{\mathrm{ub}, i, j}=\min(x_{\mathrm{top}, i}, B_j), x_{\mathrm{lb}, i, j}=\max(x_{\mathrm{bottom}, i}, A_j)です。
f:id:hamukichi_nbr:20160501142311p:plain

続いて、各\mathrm{F}_{i,j}を図示し、各W_{i, j}(\ne 0)の求め方を考えましょう。図のように長さや角度を定義します。いま、\tan\theta = R_i / H_iであり、r_{\mathrm{ub}, i, j} = (x_{\mathrm{top}, i} - x_{\mathrm{ub}, i, j})\tan\thetaおよびr_{\mathrm{lb}, i, j} = (x_{\mathrm{top}, i} - x_{\mathrm{lb}, i, j})\tan\thetaが成り立ちます。あとは、円錐台の体積の公式から*3W_{i, j} = \pi(r_{\mathrm{ub}, i, j} ^ 2 + r_{\mathrm{ub}, i, j} r_{\mathrm{lb}, i, j} + r_{\mathrm{lb}, i, j} ^ 2)(x_{\mathrm{ub}, i, j} - x_{\mathrm{lb}, i, j})/3が成り立つことを利用すればよいでしょう。
f:id:hamukichi_nbr:20160501152542p:plain

解答例

以下に、Python 3とC++による解答例を示します。なお、コンテスト中にはC++で解答しました。

Python 3による解答例

C++による解答例


感想

一見、何やら難しそうな問題に見えましたが、問題文の状況を図示することで、解法がわかってきました。見た目だけで安易にあきらめず、少し踏ん張ってみることの重要性を感じました。

*1:以下では領域についてややあいまいな扱いをしていますが、本問を解くうえでは特に差し支えないと思われます。

*2:やや記述が複雑なので、下のコードとあわせて読んだ方がわかりやすいかもしれません。

*3:wikipedia:円錐台によります。