プログラミングにおける時間制御技術

背景

時折、私たちの検索処理は非常に長時間かかり、タイムリミットエラー（TLE）が発生します。TLEが発生した場合のスコアは0ですが、タイムリミット直前に現在の最適解を出力できれば、スコアは0以上となります。このような状況では、時間制御技術が必要になります。

時間制御とは

時間制御、その名が示す通り、時間を制御することです。現在の時間を記録し、タイムリミットが近づいたら、現在の最適解を出力してプログラムを終了させるという技術です。

実装方法

基本版（誤った例）

#include 
//#include <ctime>
// bits/stdc.hを使用しない場合はctimeを必ずインクルード

using namespace std;

int start_time;

int main() {
    start_time = clock();  // 現在の時間を記録
    
    while(1) {  // 検索処理を模倣
        if(clock() - start_time >= 0.95) break;
        // 現在の時間 - 開始時間が1秒を超えたら終了
    }
    
    cout << 52520 << endl;  // 検索中に見つかった最適解を出力
    
    return 0;
}

このコードを競技プログラミングサイトに提出すると、各テストケースが**1ms**以内に終了していることに気づくでしょう。これは、競技プログラミングサイトがLinuxシステムを使用しており、時間計算の単位がマイクロ秒（μs）であるためです。0.95は0.95μs、つまり1ms未満を意味します。提出先の評価機がどの単位を使用しているか分からないため、単位を統一する必要があります。

改善版

必要なのは`CLOCK_PER_SEC`という定数です。これはシステムが1秒あたりに使用する時間単位の数を示し、1秒に相当します。これに0.95を掛けると950msになります。

#include 

using namespace std;

int start_time;

int main() {
    start_time = clock();  // 現在の時間を記録
    
    while(1) {  // 検索処理を模倣
        if(clock() - start_time >= 0.95 * CLOCK_PER_SEC) break;
        // 現在の時間 - 開始時間が1秒を超えたら終了
        // CLOCK_PER_SECは1秒あたりの時間単位の数
    }
    
    cout << 52520 << endl;  // 検索中に見つかった最適解を出力
    
    return 0;
}

最適化版

ここで実数乗算があることに気づきます。一般的に知られているように：

もし加算の時間を1とすると、減算も1です。乗算はどうでしょうか？ 100 それほどではありません。32程度です。 除算はどうでしょうか？ 100 それほどではありません。1000程度でしょう。

ここでは乗算ですが実数なので、整数乗算に変換したいと考えます。両辺に1000を掛けることで解決できます。

#include 
#include <ctime>

using namespace std;

int start_time;

int main() {
    start_time = clock();  // 現在の時間を記録
    
    while(1) {  // 検索処理を模倣
        if((clock() - start_time) * 1000 >= 950 * CLOCK_PER_SEC) break;
    }
    
    cout << 52520 << endl;  // 検索中に見つかった最適解を出力
    
    return 0;
}

最終版（DFS実装）

#include 
#include <ctime>

using namespace std;

int start_time;

void dfs() {
    if((clock() - start_time) * 1000 >= 950 * CLOCK_PER_SEC) {
        cout << 52520 << endl;  // 現在の最適解を出力
        exit(0);  // プログラム全体を終了（return 0とほぼ同等）
    }
    dfs();
}

int main() {
    start_time = clock();  // 現在の時間を記録
    
    dfs();
    
    return 0;
}

時間制御の長さ

999msで良いのでしょうか？いいえ。まず、最適解の出力とプログラムの終了にも時間がかかります。また、評価機の動作により時間が変動する可能性があります（例えば、ある学生が同じコードを最初に提出したら80点だったのに、2回目の提出で100点になったというケース）。

では950msはどうでしょうか。実際には可能ですが、CCF（中国情報オリンピック）では再テストのタイムリミットが950msを超えると再テストが受けられません（再テストの成功例はないと先生の話では）。

以上のことから、900ms程度が適切でしょう。