三浦と窮理とブログ

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

競技プログラミング

剰余の変域

問題 L ≦ x ≦ R な自然数 x に対して, 自然数 m を法とする剰余の値 y = x%m の変域は if (R - L ≥ m) 0 ≦ y ≦ m - 1 else if ($\lfloor$L/m$\rfloor$ = $\lfloor$R/m$\rfloor$) L%m ≦ y ≦ R%m else if ($\lfloor$L/m$\rfloor$ + 1 = $\lfloor$R/m$\rfloor$…

A - Diverse Word:AGC22

問題 A - Diverse Word 入力された多彩な単語に対し,辞書順で次の多彩な単語を求める. 理解 多彩な単語の辞書がすぐには想像できないので書き下すことにする.「見たものは想像できる」の精神. a から始まる多彩な単語について,次の図のように木の形に単…

冪剰余と剰余の逆元を求めるC++/Boostライブラリ

冪剰余 冪剰余 $a ^ b \bmod m$ を求めます.たぶん二分累乗法だと思います. #include <boost/multiprecision/integer.hpp> boost::multiprecision::powm(a, b, m) 剰余の逆元(拡張ユークリッド互除法) 剰余の逆元 $a^{-1} \bmod m$ が存在すれば求めます. (2019年10月5日追記:これはboos</boost/multiprecision/integer.hpp>…

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のサイズに比例した時間がかかります. もっと…