アルゴリズム
予選落ちました 本番で AC しましたが、証明の誤りがありましたらご指摘をお願いします。 解法 c=a-b をして階差を取ると、次のような問題に帰着できます。 c[0]...c[n] があります。「c[i]+=1, c[j]-=1 (i
2021/02/18 数式を修正しました 拡張ユークリッド互除法とは 方程式 の解 を 1 つ求めるアルゴリズム*1です。 注意 qnighy.hatenablog.com 書いた後で、概ね同じ内容を説明している記事を見つけました。分かりやすさには個人差があると思うので、本記事にも…
2019/04/20 実装の誤りなどを修正しました。 2021/02/18 説明を大幅に変更しました。 概要 qiita.com こちらの記事を読んで 値だけでなく一般の 値について拡張できそうだと思ったので、それを書きます。 値転倒数が伴う群 \begin{align} G &= \mathbb{Z}^k …
添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモ 高速化前の実装と、実用例などが書かれています 概要 kazuma8128.hatenablog.com 高速ゼータ変換は添え字を集合とみなして各添え字について部分集合の和を計算します。これと同じことを約数でも…
はじめに ARC098お疲れさまでした。Fを終了１分前に記念提出したらサンプル以外ACしていた(=埋め込みで全完狙えてた)ので少し残念な気持ちです。それはそうとE問題が準線形時間で解けることが解説で示唆されていたのでそれについて書こうと思います。E問題の…
O(N * log(max(a))解法 解法の軸は解説の通りですが、いくらかの工夫をします。まず、数列のソートに桁ごとのバケットソートを使用します。下位の桁から順に計算していけば基数ソートの動きそのままになるので、各桁で O(N) でソートが可能です。数列 a, b …
2018/06/16 ライブラリの変更に伴い、コードを書き直しました。 概要 二部グラフ判定の方法を調べるとBFS/DFSが良く出てくるのですが、UnionFindTreeと頂点拡張を用いた方法が簡潔で使いやすいと感じたため覚え書きを兼ねて書きます。 アルゴリズム 全ての頂…
LISは競プロでも低くない頻度で出現する題材です。 一般に知られている計算方法では単純な配列を用いてO(NlogN)でLISの計算が可能ですが、BITを用いることで同じ計算量でより直感的に(個人差あり)LISの計算が可能なのでそれについて少し書きます。 与えられ…
