三浦と窮理とブログ

自分の経験したことを検索可能にしていくブログ.誰かの役に立ってくれれば嬉しいです.

C++

1次不定方程式を解くC++/boostライブラリ

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

整数配列の最大公約数を求めるC++/boostライブラリ

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

ABC150D - Semi Common Multipleまとめ

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

Ford-Fulkerson法の実装解説

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

C++ で2次元配列の最大値を求める.

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

C++ で std::queue を定数時間で空にする方法

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