POJ Hacks

POJ のジャッジシステムは残念なので、計算量的に問題が無くても Time Limit Exceeded になることがよくあります。 これを回避するための方法を列挙します。

POJ 固有っぽいものも、一般的に使えるものもあります。

iostream ではなく stdio.h を使う

cincout は遅いので scanfprintf を使います。

どうしても cin を使いたい場合は cin.sync_with_stdio(false); を最初に書いておくと高速化が期待できます。 std::ios_base::sync_with_stdio

コンパイラを C、C++ に変える

POJ では C/C++ のコンパイラとして C、GCC、C++、G++ を選べますが、C、C++ でコンパイルしたほうが G、G++ でコンパイルした場合よりも高速であることが多いようです。

vector<bool> ではなく vector<int> を使う

vector<bool> は特殊化されており、メモリ消費量が少ないかわりに添字アクセスが遅くなります。

vector ではなく配列を使う

要素数が多い場合は int a[MAX_N]; と宣言してしまうとスタックが溢れることがあるので、 グローバルに宣言するか static で静的に確保しましょう。

string ではなく C 文字列を使う

文字列操作が必要な場合でも単純に string を使うと TLE することもあり、 そのときは C の文字列操作の関数を使いながらがんばりましょう。

文字列を setmap のキーに入れたい場合、C 文字列だとめんどくさいことがあります。 そういうときは struct fixed_string { char str[MAX_N]; } のようなクラスを用意して、これを使うようにすると楽だと思います。

重複削除に set ではなく sortunique を使う

単に一回だけ重複を削除したい場合は sort してから unique する方法のほうが高速です。 要素を削除するには erase する必要があることに注意しましょう。

重複カウントに map ではなく sortunique を使う

重複をカウントしたいときは map<int,int> m を用意して ++m[x]; とすると楽ですが、POJ ではこれで TLE することもあります。 上の hack と同様に vector に入れてから sortunique して自分で数えると高速化します。

オブジェクトを STL コンテナに入れず、適当にエンコードした数値を入れる

pair のような単純なオブジェクトであっても、vectorqueuemap に入れる際には適当にエンコードした数値を入れ、取り出したときにデコードするようにすると高速化が期待できます。

動的にメモリを確保せず、静的に確保して割り当てる

POJ では動的なメモリ確保が遅く、new を使わないのはもちろん、 vector 等の内部で動的にメモリを確保する STL のコンテナを避ける必要があることもあります。

グラフを隣接リストで保持しようとするとどうしても vector がほしくなりまが、 頂点数が多いグラフの場合これだけで TLE することがあります。 そんなときはエッジリストで保持すると TLE を回避できるかもしれません。 事例: POJ 3107

グローバルに最大の要素数分の配列 objects とインデックス object_index を用意しておき、 本来なら new したい箇所で objects[object_index++] を割り当てる、という方法もあります。 各テストケース後に object_index = 0; としてこの領域を使い回します。

言語を Java に変える

POJ では Java で提出すると Time Limit が C/C++ の3倍程度になります。 どうしても通したいクソゲーは Java で書き直すのも意味があるかもしれません。