OpenMPというものがあります（競プロでは使えないけど）

昨日のABC344-G、愚直がなんか通りそうな見た目をしています。

問題を読んでない人のために簡単に説明すると、以下が愚直の実装です。q <= 10⁷, n <= 5000。

long long ans = 0;
for(int i = 0; i < q; i++) {
    for(int j = 0; j < n; j++) {
        ans += (y[j] >= a[i] * x[j] + b[i]);
    }
}

実際、自分のPCで最大ケースを流すと約10秒でした（※自分のPCはジャッジ環境よりもやや性能がよく、実際に愚直を通すのはほとんど無理そうです）。

$ g++ -Ofast -march=native -std=c++17 main.cpp
$ time ./a.out

real    0m9.967s

さて、競プロしかやらない人には身近ではないかもしれませんが、OpenMPというものがあります。

OpenMP（オープンエムピー）は、並列計算機環境において共有メモリ・マルチスレッド型の並列アプリケーションソフトウェア開発をサポートするために標準化されたAPIである。(Wikipedia)

なんだか難しそうに聞こえるかもしれませんが、使い方は非常に簡単です。

まずは、omp.h をインクルードします。

#include <omp.h>

次に、おまじないを一行だけ付け加えます。

#pragma omp parallel for reduction(+: ans)
for(int i = 0; i < q; i++) {
    for(int j = 0; j < n; j ++) {
        ans += (y[j] >= a[i] * x[j] + b[i]);
    }
}

あとは、-fopenmp オプションをつけてコンパイルするだけです。

$ g++ -Ofast -march=native -std=c++17 -fopenmp main-omp.cpp
$ time ./a.out

real    0m2.069s

なんと！実行時間が10秒→2秒に短縮されました。うれしいですね～。

さて、じゃあなんでこれが競プロで使えないかという話なんですが、競プロの実行時間はuser timeで評価されるからです。

下の表はOpenMPを使った場合と使わなかった場合のreal/user timeの比較です。

	real	user
OpenMPなし	0m9.874s	0m9.844s
OpenMPあり	0m2.069s	0m30.183s

以上、OpenMPというものがあるという話でした。