AOJ1026:Hedro's Hexahedron

N✕N✕2の直方体の容器の中に容積2Nの液体を入れる。N✕Nの平面に垂直な軸で容器を１回転させた時、液体に触れる面積はいくつか求める問題。ただし、タイル状で考え、少しでもそのタイルにかすればその1タイルは液体に触れたとする。
Hedro's Hexahedron | Aizu Online Judge

底面は間違いなく液体に触れる。でも、側面は…分かるんだけど描いてみたかったので描きました。

綺麗な包絡線が出来てますね…反比例のグラフのようです。
面積Nで左端からの幅をw、高さをhとおけばN=wh/2が成立するので当然ですが。
取り敢えず、今回は左下の1/4の部分のみを考えて、後に裏面も考慮して８倍してあげればいいでしょう。
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って偶数なんだ…要りません。かなり考えさせられたのになぁ…
実質２周目までは絶対全部使います。それを使っても良かったな…とか、今高２で数Ⅲ終えたばかりなので積分と挟み撃ち使って何か出来そうだな…とか思ったりしていました。