【ICPC国内予選】テストケース並列化でなぐろう

# 【ICPC国内予選】テストケース並列化でなぐろう ICPC 国内予選は今年からルールが大きく変わり，事前の電子的準備が可能になり，提出までに 6 分の時間制限が追加されました． ## 並列化の威力 [AOJ への移植](https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim) を見ればわかる通り，ICPC 国内予選の問題は想定解が 8 秒 (定数倍を考えると 3 秒程度が妥当か) 以内に実行が終わるように設計されていると考えられます．しかし，実際の競技では時間制限は **6 分** で，その他の操作を取り除くと，5 分半 (330 秒) 程度をプログラムの実行に使うことができます． $\Theta(n^2)$ の計算量を $\Theta(n \log n)$ や $\Theta(n)$ に落とすような問題を考えてみましょう．入力長はそこまで大きくしたくないので，$n = 10^6$ 程度が妥当でしょう． 1 秒間にできる "計算" の回数を $10^9$ 回として，$n^2$ 回の "計算" が必要な愚直解で計算すると，$10^{12} / 10^9 = 10^3$ 秒となり間に合いません．しかし，マルチスレッド等の並列化により $10$ 並列で計算できるとすると，実行時間は $100$ 秒となり間に合います！競プロでよく言われる $10^9$ くらいのボーダーは，ICPC 国内予選では並列化をすると $10^{12}$ くらいになってしまうわけです． (一方，想定解は $10^9$ くらいのボーダーで作られていて，$10^3$ 倍に耐えるような問題を作るのは大変…, AtCoder でも $10$ 倍はないのに…) ## OpenMP 並列化といえばやはり OpenMP でしょうか． `#pragma omp parallel for` と書いて `-fopenmp` でコンパイルするだけで，for 文が並列に動きます．しかし，自分で並列化できるところを見つけて，その場に応じて並列化構文を書かないといけないので，面倒だし覚えることが多いです．もっと簡単に並列化できる部分として，テストケースの並列化がありますね． ## テストケース並列化テストケースを並列化するには， 1. 入力を分解 2. 各テストケースごとに並列に答えを計算 3. 出力を結合の処理が必要です．中でも，入力の分解が厄介ですね．できれば，入力を分解するためのコードを書かずに，普通に解くのと同様なコードで並列化したいです． ## マルチプロセス化 `std::thread` だとなぜか全然処理が進まなかったので，`fork()` を使ったマルチプロセス並列化をやります． - 普通に解くのとほとんど同じコードで並列化できる - RE や TLE をキャッチして，どのケースで落ちたかがわかるを目標にしましょう． ↓できたライブラリがこちらになります↓ https://gist.github.com/tatyam-prime/1161da013a31632690d616016d51d743 ## 技術解説 #### `fork()` https://manpages.ubuntu.com/manpages/noble/ja/man2/fork.2.html `fork()` は現在のプロセスを複製する関数です．メモリの状態やファイルディスクリプタ (現在開いているファイルなどの位置を表す構造体への参照) など，すべてが同じプロセスが 2 個できます．これらのプロセスは，`fork()` 関数の戻り値によって区別することができます．0 なら子プロセスで，正なら親プロセスです．このときの値は子のプロセス ID になっています．以下のようにして使います． ```cpp= const pid_t p = fork(); if (p == -1) { perror("fork"); return 1; } if(p) { // 親プロセス } else { // 子プロセス } ``` このライブラリでは，テストケースごとに子プロセスを作って，子プロセスでテストケースの入力から出力までを行っています． `fork()` はファイルディスクリプタも複製し，ファイルディスクリプタは参照なので，`fork()` する前に親が開いていたファイルについて，**親子で読み込み・書き込み位置が共有されます．** 実行時に最初から開かれているファイルディスクリプタが 3 つあって， - 0 番 : 標準入力 - 1 番 : 標準出力 - 2 番 : 標準エラー出力です．これらが `fork()` により子プロセスに複製されるので，**全プロセスで読み込み・書き込み位置が共有される**ようになっています． #### 共有メモリ共有した標準入出力を使って入出力を行いたいので，いつ入出力して良いかを知るために親子間での通信が必要です．しかし，メモリは複製されていて共有はされないので，このままだとプロセス間通信ができません．プロセス間通信の第一の手法はパイプですが，親プロセスが (複製するので子プロセスも) テストケース数 × 4 のファイルディスクリプタを使用してしまい大変そうだったので，違う方法を使います． ChatGPT に聞いたところ，プロセス間でメモリを共有することができるようです．これを使って，現在のプロセスの状態を共有メモリに書き込むことによって，プロセス間通信して，いつ入出力して良いかを伝えることにします．親プロセスは，以下の 2 つの処理を並行して行います． ##### 入力の処理 1. 生成された子プロセスは，標準入力から入力を行い，「入力が終了した」か「0 のみからなる行だった」を共有メモリに書き込みます． 2. 「0 のみからなる行だった」場合は，親プロセスは，子プロセスの生成を終了します． 3. 「入力が終了した」ら，親プロセスは，次の子プロセスを生成します． ##### 出力の処理 1. 子プロセスは，出力の準備ができたら，出力の許可が出るまで sleep します． 2. 子プロセスは，出力の許可が出たことを確認したら，標準出力に出力を行い，「出力が終了した」を共有メモリに書き込み，プロセスを終了します． 3. 親プロセスは，子プロセスの終了を確認したのち，「出力が終了した」であることを確認して，次のプロセスに出力の許可を出します． ## 使用例 --- <h3>連鎖行列積</h3> <div> 整数 N と整数列 L0, L1, …, LN が与えられる． N 個の行列 A0, A1, …, AN−1 があり，各 i = 0, 1, …, N−1 について，行列 Ai は縦 Li 行，横 Li+1 列の行列である． これから，行列積 A0・A1・…・AN−1 を計算したい．行列の積は 2 つの行列の間に定まる結合法則を満たす演算で，X 行 Y 列の行列 A と Y 行 Z 列の行列 B を掛けると，X 行 Z 列の行列 A・B が得られる． 結合法則により，どの部分の積から先に計算しても正しい答えが得られるが，どの部分の積から先に計算するかによって，その計算量は異なる． X 行 Y 列の行列と Y 行 Z 列の行列の積の計算に X × Y × Z のコストがかかるとき，行列積 A0・A1・…・AN−1 を計算するためのコストの最小値を求めよ． より厳密には，以下の漸化式で定義される f(0, N) の値を求めよ． <ul> <li>各 i = 0, 1, …, N−1 に対し，f(i, i + 1) = 0．</li> <li>0 ≤ i < i + 1 < j ≤ N を満たす整数の組 (i, j) に対し，f(i, j) = mink∈{i+1,…,j–1} {f(i, k) + f(k, j) + Li × Lk × Lj}．</li> </ul> </div> <h3>Input</h3> <div> 入力は複数のデータセットからなり，各データセットは次の形式で表される．データセットの個数は 100 を超えない． <blockquote>N L0 L1 … LN</blockquote> N は行列の個数で，2 以上 3000 以下の整数である．Li は行列 Ai の行数および行列 Ai–1 の列数を表す 1 以上 10000 以下の整数である． 入力の終わりは 1 つのゼロからなる行で表される．すべてのデータセットにわたる N の総和は 30000 を超えない． </div> <h3>Output</h3> <div> 各データセットについて，答えを 1 行に出力せよ． </div> <h3>Sample Input</h3><div><pre>3 2 1 5 9 3 1 5 6 3 4 4 5 4 1 4 5 6 5 2 7 9 5 6 2260 2043 2528 3798 3052 4693 646 2 10000 10000 10000 0 </pre></div><h3>Output for the Sample Input</h3><div><pre>63 48 56 336 29262352960 1000000000000 </pre></div> --- $N = 3000$ が最大 $10$ ケースありますが，$N^3 / 6 \times 10 \approx 4.5 \times 10^{11}$ なので並列化で間に合うでしょう．まずは普通に解いてみましょう． ```cpp= #include <bits/stdc++.h> using namespace std; using ll = long long; void chmin(ll& a, ll b) { if(a > b) a = b; } int main() { while(1) { ll N; cin >> N; if(N == 0) break; vector<ll> L(N + 1); for(ll& x : L) cin >> x; vector dp(N + 1, vector<ll>(N + 1, LLONG_MAX)); for(ll i = 0; i < N; i++) dp[i][i + 1] = 0; for(ll i = N; i--; ) for(ll j = i; ++j <= N; ) for(ll k = j; ++k <= N; ) { chmin(dp[i][k], dp[i][j] + dp[j][k] + L[i] * L[j] * L[k]); } cout << dp[0][N] << endl; } } ``` 使用 CPU : M2 Mac ``` ./a.out < input.txt 25.44s user 0.12s system 97% cpu 26.176 total ``` 26 秒で終わってしまいました．$N = 7000$ くらいまで間に合う計算です．続いて，ライブラリを使って解いてみましょう．テストケースの処理は `void solve()` に書き， - 入力の始めに `MP::begin_input();` を， - 入力の終わりに `MP::end_input();` を， - 出力の始めに `MP::begin_output();` を， - 出力の終わりに `MP::end_output();` を， - テストケースが終了していたら，`MP::end_of_file();` を書きます． ```cpp= #include "dataset_parallel_MP.cpp" #include <bits/stdc++.h> using namespace std; using ll = long long; void chmin(ll& a, ll b) { if(a > b) a = b; } void solve() { MP::begin_input(); ll N; cin >> N; if(N == 0) MP::end_of_file(); vector<ll> L(N + 1); for(ll& x : L) cin >> x; MP::end_input(); vector dp(N + 1, vector<ll>(N + 1, LLONG_MAX)); for(ll i = 0; i < N; i++) dp[i][i + 1] = 0; for(ll i = N; i--; ) for(ll j = i; ++j <= N; ) for(ll k = j; ++k <= N; ) { chmin(dp[i][k], dp[i][j] + dp[j][k] + L[i] * L[j] * L[k]); } MP::begin_output(); cout << dp[0][N] << endl; MP::end_output(); } ``` ``` ./a.out < input.txt 61.95s user 0.38s system 679% cpu 9.170 total ``` 9 秒で終了し，3 倍の高速化が実現されました:tada: ## おわり今年の模擬国内予選は，並列化でオーダーを落とさず通せる問題がいくつかあったんですが，本番の方はあまり有用ではなさそうで，ちゃんと準備されているなあ… と思うなどしました．