AOJ1026:Hedro's Hexahedron
N✕N✕2の直方体の容器の中に容積2Nの液体を入れる。N✕Nの平面に垂直な軸で容器を1回転させた時、液体に触れる面積はいくつか求める問題。ただし、タイル状で考え、少しでもそのタイルにかすればその1タイルは液体に触れたとする。
Hedro's Hexahedron | Aizu Online Judge
底面は間違いなく液体に触れる。でも、側面は…分かるんだけど描いてみたかったので描きました。
綺麗な包絡線が出来てますね…反比例のグラフのようです。
面積Nで左端からの幅をw、高さをhとおけばN=wh/2が成立するので当然ですが。
取り敢えず、今回は左下の1/4の部分のみを考えて、後に裏面も考慮して8倍してあげればいいでしょう。
N≦10^12より左端から数えていって時間内に間に合うようにするには、N≦w^2の範囲のみ数えて、それを2倍、被ったところを引いてあげます。O(√N)。
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ while(true){ ll n; cin>>n; if(n==0) return 0; ll ans=8*n;// 底面積 ll ans2=n/2; ll w=1; for(;w*w<n/2;w++){ ans2+=(n+2*w-1)/(2*w); } ans2=2*ans2-w*w; if(n&1) ans2++; ll s=ans+ans2*8; cout<<s<<endl; } }
考察ゲーでした。ちなみにifのところは一番外側の一周がNが奇数の時に重複するためそれを避けるものです。と思ったけど、Nって偶数なんだ…要りません。かなり考えさせられたのになぁ…
実質2周目までは絶対全部使います。それを使っても良かったな…とか、今高2で数Ⅲ終えたばかりなので積分と挟み撃ち使って何か出来そうだな…とか思ったりしていました。