PythonとC++の速度差を痛感した話 ARC109 B - log

先日のAtCoder Regular Contest 109にて。
atcoder.jp

背景

この問題は、N+1の丸太をどう分割するかの走査（i=1,2,3...）がキモなわけですが、制約も大きいし、ハナから愚直にやってもダメだ、二分探索が必須だと思っていました。しかし、それすら必要ないという呟きを見かけたので、検証してみました。

結果

言語	処理	時間
Python	二分探索	34 ms
Python	愚直 ①	余裕のTLE
PyPy	愚直 ①	約2300 ms ③
C++	愚直 ②	540 ms

制約10¹⁸において、走査はi=10⁹超まで行くわけですが、ループ内の処理が大したことないこともあり、実はそこまでヤバくないようです。たぶん、文字列操作とか、配列だとか、性質が変われば、同じ理屈にはならないとは思いますが。

C++なんかはまだまだ余裕ですね。PyPyでも、もう1割ほど走査が少なければ、もしくは書き方で間に合うのかもしれない。

なんとなく、10⁹まできたら、ワンチャンもないと思っていましたが、そうでもないようですね。
自明なことかもですが、ちょっと驚いたのでメモ。。。

ソースとか備考

①こんなの

def resolve():
    N=int(input())
    temp=N+1
    i=1
    while True:
        temp-=i
        if(temp<0):
            i-=1
            break
        i+=1
 
    print(N-i+1)
 
resolve()

②こんなの

int main() {
    ll N;
    cin >> N;
    ll temp = N + 1;
    ll i = 1;
 
    while (true) {
        temp -= i;
        if (temp < 0) {
            i--;
            break;
        }
        i++;
    }
    cout << N - i + 1;
}

③：制約より1割程度小さいテストケースで、ギリギリ2000msを割っているため、推測値。