paiza上で何回計算できるかの目安(C++)を計測してみた。

競技プログラミング系は許容される実行時間と消費メモリ量が決まっている

paizaにかぎらずAtcoderとか競技プログラミング系はリソースに制約がかかっている場合があります。
問題に対する解法の計算量を先に計算しておかないと、実装してから制限時間内に終わりませんでしたでは悲しすぎます。
計算量を時間に換算するとこれによると、、$O(10^7)$から$O(10^8)$くらいで1秒になるらしいです。
・・・本当かなぁ。

計測してみた。

ということで実際に計測してみました。

計測のプログラムは下にあります。
プログラムは、オーダー分だけ乱数を計算するだけです。
Nの大きさが$10$の乗数になるのでそのままオーダーの大きさになります。
countが計測回数です。
計測ページは、paiza.ioを使いました。
※サーバーに負担がかかるのでむやみやたらにやらないほうが良いです。
計測の結果、$10^8$回で、大体$0.21$秒 かかっているため、$5 \times 10^8$くらいで1秒になります。
よって概ね正しいです。
実際に問題を解く場合、計算量がさらに少なくなり高速になる場合もありますが、メモリへのアクセスを伴うことがほとんどの場合で想定されます。
よって実際には更に時間がかかると思われます。
計算に使う変数がCPUのキャッシュに乗った場合、かかっても1桁から2桁増えるくらいになりそうなので、多くても$O(10^7)$くらいのオーダーだったら、paizaの問題は制限時間3秒(paiza.ioは2秒)のため通ることになります。
※コンパイルの最適化が行われないこと前提なプログラムです。最適化が行われる場合、ループ中のxorShift()の値が利用されていないため、ループが消える可能性もあります。。
よって目安は$O(10^7)$としてアルゴリズムを考えましょう。

#include <iostream>
#include <chrono>
#include <array>
#include <numeric>

#include <cinttypes>
#include <cstdlib>

using std::cin;
using std::cout;
using std::endl;
using std::cerr;

template<class T>
constexpr T spow(T base, T exp) noexcept {
    //static_assert(exp >= 0, "Exponent must not be negative");
    return exp <= 0 ? 1
        : exp == 1 ? base
        : base * spow(base, exp - 1);
}
uint32_t xorShift(void) {
    static uint32_t y = 2463534242;
    y = y ^ (y << 13); y = y ^ (y >> 17);
    return y = y ^ (y << 5);
}
int main(void)
{
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    constexpr size_t N = 8;
    constexpr size_t orderSize = spow<size_t>(10, N);
    constexpr size_t count = 10;
    std::array<double, count> timeArray;
    cout << "O(10^" << N << ")" << endl;
    for (auto &&elem : timeArray)
    {
        auto startTime = std::chrono::high_resolution_clock::now();
        for (size_t i = 0; i < orderSize; i++)
        {
            xorShift();
        }
        auto endTime = std::chrono::high_resolution_clock::now();
        auto elapsed_time = std::chrono::duration_cast<std::chrono::microseconds>(endTime - startTime);
        double time = elapsed_time.count() / (spow<double>(10, 6));
        cout << time << "秒" << endl;
        elem = time;
    }
    double ave = std::accumulate(timeArray.begin(), timeArray.end(), 0.0f) / (double)timeArray.size();
    cout << "平均" << ave << "秒" << endl;

    return EXIT_SUCCESS;
}