windows10の環境でC++のマルチスレッド・べクトル化プログラムを実行してみます。 cpuがintel core i7-3700 (4core/8thread)の環境です。 実行ポリシーを指定できる <execution> *1 が gcc9(C++17) から使えるそうなので *2 mingw-w64のgccのインストールからやりました</execution>…

boost の boost/integer/extended_euclidean というライブラリに1次不定方程式を拡張ユークリッド互除法で解く型があるので使ってみます． 1次不定方程式 $mx + ny = \operatorname{gcd}(m, n)$ の解 $x, y$ を1つ求めることができます． 以下のプログラムを…

boost の boost/integer/common_factor_rt というライブラリで整数配列の最大公約数や最小公倍数を求める関数があるので使ってみます． 最大公約数を求めるのは gcd_range，最小公倍数を求めるのがlcm_range です．戻り値のpairの1成分目に値が入っています…

Atcoder ABC150D D - Semi Common Multiple 時間内にはできませんでした．解説を見ながらやり直したのでまとめます． a = { a₁ ，a₂ ，... ，aN } a/2 = { a₁/2 ，a₂/2 ，... ，aN/2 } と表すことにします．a が偶数列なので，a/2 は整数列です．a の半公倍…

グラフの最大流問題を解くアルゴリズムのFord-Fulkerson法のC++実装例が プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ （蟻本）p190にあります．アルゴリズム自体は本文にある説明…

C++ で1次元配列の最大値を求めるならばfor文を使わずに max_element を使うと楽です． 2次元配列の最大値を一度に求めるSTL関数は私は見つけられませんでしたが，各行に対して max_element を繰り返せばいいでしょう． max_element のおかげで for を書く手…

C++ でstd::queue の内容を全て削除したくなったのですが，std::queue には clear 関数がありませんでした． なので，私は直観的には queue が空になるまで pop を繰り返せばいいと思ったのですが，これはqueueのサイズに比例した時間がかかります． もっと…