解法 最小費用流 (7.9G) 実はこの問題、トラックの移動経路を固定すると、最適解を求めることが出来ます。最適解というのは、$h_{ij} < 0$なのに更に掘り出すケース、あるいはトラックが複数回同じ頂点を通るケース等も対応した上での厳密な最適解です。 う…

疑似乱数の生成速度について軽く調べた。まず結果から紹介する。それぞれ $10^8$ 回乱数を生成してかかった時間をAtCoderのコードテストで計測した。実験コードはここ Name Output bit Time LCG32 32bit 114ms mt19937 32bit 325ms mt19937_64 64bit 389ms x…

div2by1というアルゴリズムがある -> https://gmplib.org/~tege/division-paper.pdf これはBarrett reductionやMontgomery乗算と違い、 (k, k) -> 2k-bitの乗算器でk-bitの剰余算ができる(Barrett reductionは(2k, 2k) -> 4k-bitの乗算器を必要とする) modが…

問題 長さNの整数列a_iが与えられます $Q$個のクエリを処理してください given l, r, x: $a_l \cdots a_r$を$x$倍 given l, r: $a_l \times a_{l+1} \times \cdots \times a_r \bmod 998244353$を出力 $O(\log N)$ per queryで解けるがおそらく$O( \log^{2} …

AHC030に出て、11位でした。 自分は長期マラソンは殆どやったことがなく、2015年に3回topcoder MMに出たのが最初で最後(のはず)でした。 なので今回のAHCで環境整備系も全て一からやることになりました。なのであえてそちらについての感想や振り返りを書きま…

背景 次のような問題を考えます 2個の木が与えられます。部分木の頂点数を$n, m$とした時に、$O(\min{(n, m)})$時間で小さいほうの部分木の頂点を列挙してください。 このような問題は「データ構造をマージする一般的なテクの逆」などと呼ばれるテクニックを…