Posts

概要 Stern Brocot Tree を扱うライブラリを書いた． Stern Brocot Tree 連分数 $$ a_0 + \cfrac{1}{a_1 + \cfrac{1}{\ddots a_{n - 1} + \cfrac{1}{a_n}}} $$ を，$[a_0, a_1, \dots, a_n]$ と書く．各 $a_i$ は，非負整数． $x + 1 = x + \cfrac{1}{1}$ だから，$[a_0, a_1, \dots, a_n]$ と $[a_0, a_1, \dots, a_n - 1, 1]$ は同じ数を表す． これを除くと表現は一意になる．そこで，$[a_0, a_1, \dots, a_n]$ の表現では，$a_n \neq 1$ と約束する． 例外として，$1$ は，$[1]$ で表現する． 連分数 $\alpha = [a_0, a_1, \dots, a_n]$ に対して， $u(\alpha) = [a_0, a_1, \dots, a_n + 1]$ と， $v(\alpha) = [a_0, a_1, \dots, a_n - 1, 2]$ を考える．これは，連分数最後のパートが...

概要 問題へのリンク 公式解説 は，ちゃんと読んでいない． ユーザ解説 で紹介されている解法を読んだ． 次の2つのクエリを処理するものを，Range Parallel Unionfind (仮称) というらしい merge(a, b, l) : $i \in [0, l)$ について，頂点 $a + i$ と 頂点 $b + i$ の間に辺を結ぶ． leader(a) : 頂点 $a$ を含む連結成分の代表元を返す． この問題は，次のように解ける． $2N$ 頂点のグラフを考える． 気持ちは，前半が $S$ で，後半が $S$ を逆順にしたもの 各 $i$ に対して，回文になるために必要なところ (前半と後半を使う) を線で結ぶ． これは，上の Range Parallel Unionfind の merge(a, b, l) でできる． 頂点 $i$ と $2*N - 1 - i$ を線で結ぶ．これは普通の Unionfind を使う． 回文の一つ外側の文字どうしが同じ連結成分に入っていたら不可能． そうでなければ，辞書順最小のものを求めるために，貪欲に各連結成分の値を決めていく． ということで，Range Parallel Unionfind なるものができれば良い．2つ紹介されている．...

Wavelet 行列ライブラリを書いた． 使用法 vector<ll> vec{...}; WaveletMatrix wm(vec, -1); cout << wm.kth_rank(10, 20) << endl; コンストラクタ WaveletMatrix wm(vec, amax); vec … データを格納したベクトルなど．すべて非負整数であることが必要． amax … 「データがこの値を超えない」という値．-1 を与えると，ライブラリの方で最大値を取ってくれる データメンバ wm.N … データの個数 他にもあるが，使わないと思う． データ値の取得 wm.access(i); i 番目の値を取得する．vec[i] と同じになるはずなので，あまり使いではない． 出現回数 wm.rank(t, r); 区間 [0, r) に t が現れる回数を返す． t は非負整数であればよい． r は，wm.N 以下でなければならない． k番目 wm.kth_smallest(k, l, r); wm.kth_largest(k, l, r); 区間 [l, r) で，k 番目に小さい / 大きい 値を返す． k は 0-indexed. たとえば最小値は kth_smallest(0, l, r)....

解法に詰まったとき，以下の方法が適用できないか，考えてみる． 二分探索 bit64倍高速化 convolution 半分全列挙 フロー 平方分割 CHT trie wavelet 行列 行列累乗 (期待値) = sum_i (i以上になる確率) deque はランダムアクセスが O(1) 区間 [a, b] を2次元平面の点 (a, b) で表現 区間の問題を距離の問題に言い直して Dijkstra (例題 ) 積の和典型 集合のハッシュ． Zobrist Hashing (有限集合の部分集合) 多重集合のハッシュ (例題 )

set, multiset, priority_queue などの比較関数の指定方法

この組合せで適切かどうか分からないが，こう作った． ライブラリソース 解ける問題 Bellman-Ford アルゴリズム 重み付き有向グラフで，特定の点からすべての点への距離 (パスの重みの和の最小値) を求める． 重みは負でも良い．負閉路があると距離が定義できない ($-\infty$ になる) が，このアルゴリズムはその検出ができる． 計算量は，頂点数 $N$，辺数 $M$ として，$O(NM)$． 牛ゲー 次の制約問題を解く． 変数 $x_i$ ($i = 1, \ldots, n$) に関し，次の制約の下で，$x_n - x_1$ の最大値 (または最小値) を求めよ． $x_{A_j} - x_{B_j} \leq C_j$ $\quad(j = 1, \ldots, m)$ $C_j$ は負でも良い．移項すれば良いので，$x_{A_j} - x_{B_j} \geq C_j$ という制約でも良い． この問題で，求める最大値は，「重み $C_j$ の有向辺 $(B_j, A_j)$ を持つグラフで，$1$ から $N$ への距離」になる (参考リンク )． 次が対応する． 制約を満たせないことと，グラフが負閉路を持つこと いくらでも大きな値を取れることと，グラフで$1$から$N$に到達できないこと 最小値バージョンは，同じ制約の下で $x_1 - x_n$ の最大値を求めて符号を反転すれば良い． 注意: このライブラリでは，Bellman-Ford を用いるので，変数の数$N$，制約の数$M$に対して， $\Omega(NM)$ 時間かかる．制約によっては，(適当な変換をして) ダイクストラなどの 速いアルゴリズムを使う必要があるかもしれない．...

問題概要 問題へのリンク 整数 $N$，$M$ と列$L$，$R$，$S$ が与えられる． $M$個の制約 $$\sum\{ A_j \mid j = L_i, \dots, R_i \} = S_i$$ を満たす長さ $N$ の正の整数の列 $A$ が存在するかどうか判定し， 存在する場合には $A$ の総和の最小値を求めよ． 制約 $1 \leq N, M \leq 4000$，$1 \leq S_i \leq 10^9$ 解 公式解説 略解．click to open 牛ゲー．累積和 $B_i := \sum\{A_j \mid 0 \leq j < i\}$ に関して，次を解けば良い． 次の条件の下で，$B_{N + 1} - B_{1}$ を最小化する $B_{i + 1} - B_i \geq 1$ $B_{R_{i} + 1} - B_{L_i} \geq S_i$ $B_{R_{i} + 1} - B_{L_i} \leq S_i$

問題概要 問題へのリンク 整数 $N$ と，長さ $N$ の正の整数列 $(A_1, \ldots, A_N)$ が与えられる． $m = 1, 2, \ldots, N$ に対して，次の問題を解け 列 $(A_1, \dots, A_m)$ の空でない部分列のスコアの総和を 998244353 で割ったあまりを求めよ． ただし，列 $(B_1, \ldots, B_k)$ のスコアは，$\displaystyle\sum_{i = 1}^{k-1} \textrm{gcd}(B_i, B_{i + 1})$ である． 制約 $1\leq N \leq 5\times10^{5}$，$1 \leq A_i \leq 10^5$ 解 公式解説へのリンク ユーザ解説 (noshi91) へのリンク すこし考察すると，解を $R_1, \ldots, R_N$ として， $$ R_i = 2R_{i - 1} + \sum_{j = 1}^{i - 1} 2^j \textrm{gcd}(A_i, A_j) $$...

問題概要 問題へのリンク 整数 $n$, $m$, $k$ と，長さ $k + 1$ の整数の組の列 $((x_1, y_1), (x_2, y_2), \dots, (x_{k + 1}, y_{k + 1}))$ が $(x_i, y_i)$ は，サイズ $n\times m$ のグリッドのセルの座標であり，重複は無い． $(x_i, y_i)$ と $(x_{i + 1}, y_{i + 1})$ の間に1つずつセルを挿入して， 縦横につながった単純パスを作る方法の数 (作れなければ $0$) を mod $10^9 + 7$ で求めよ． 制約 $1 \leq n, m \leq 1000$， $nm \geq 3$，$1 \leq k \leq \lfloor (nm - 1) / 2 \rfloor$ 解 tutorialへのリンク 略解．click to open $P_i = (x_i, y_i)$ と書く．$\{|x_i - x_{i + 1}|, |y_i - y_{i + 1}|\}$ は， (1) $\{0, 2\}$ であるか，(2) $\{1, 1\}$ であるか，でなければならない． 間に入れる点は，(1) では1つに決まる．(2) では，2つの点のうちのどちらか．...

K番目の要素の二分探索による求め方と，ベクトルのt付近の要素

問題概要 問題へのリンク 1辺の長さが1の正方形である2種類のタイルがある． 種類A: 種類B: 高さ $H$，幅 $W$ のグリッドに，このタイルが敷き詰められている． (A, B からなる長さ $W$ の文字列が $H$ 個与えられる) 各タイルは回転可能． グリッドをトーラスとしてみたときに，線分が行き止まりにならずつながるように配置する方法の数を mod 998244353 で求めよ． 制約 $2 \leq H$，$2 \leq W$，$HW \leq 10^6$ 解 公式解説へのリンク 略解．click to open 正しく敷き詰められているとする． $p[i, j]$ を，セル $(i, j)$ の左側の縦の線分の中点を線が通るかどうか (true/false) $q[i, j]$ を，セル $(i, j)$ の上側の横の線分の中点を線が通るかどうか (true/false) とする． トーラスになるように同一視する． $i$を固定し，横一列に $p[i, j]$ ($j = 0, 1, \ldots, W)$ を考えると， セル $(i, j)$ が A なら，$p[i, j] = \neg p[i, j + 1]$ セル $(i, j)$ が B なら，$p[i, j] = p[i, j + 1]$ だから，A の横の個数は偶数でなければならない．縦も同様．...

問題概要 問題へのリンク 整数 $N$ と長さ $N$ の整数列 $A$ が与えられる．最初スコアは $0$ である． 次の操作を，$A$ の長さが $1$ 以下になるまで繰り返す: $A$の (その時点で) 隣接する2項を選び，どちらも削除する． 2項の差の絶対値がスコアに加算される． 得られるスコアの最大値を求めよ． 制約 $2 \leq N \leq 3\times 10^5$，$1 \leq A_i \leq 10^9$ 解 公式解説へのリンク 略解．click to open $N$ が偶数の時 大きい方の半分をプラスに，小さい方の半分をマイナスにした和がスコアの上界． この上界が達成できる． $N$ が奇数の時 最後に残る1個を決めると，その左右それぞれで，上記偶数の時と同じ議論になる． 最後に残る1個を，左から順に全部調べる．

問題概要 問題へのリンク 整数 $N$ と，長さ $N$ の整数列 $A = (A_0, \ldots, A_{N - 1})$ が与えられる． $A$ を 2箇所で区切って，3個の空でない連続する部分列に分解するとき， おのおのの部分列に含まれる数の種類数の和の最大値を求めよ． 制約 $3 \leq N \leq 3\times10^5$，$1 \leq A_i \leq N$ 解 公式解説 略解．click to open $L_i := (A_0, \ldots, A_{i - 1})$ に含まれる種類数 $R_i := (A_i, \ldots, A_{N - 1})$ に含まれる種類数 $dp[i][j] := (A_0, \ldots, A_{j - 1})$ と $(A_j, \ldots, A_{i - 1})$ に含まれる種類数の和 ($j \in [0, i)$) とする．求める値は $\max_i (R_i + \max_j(dp[i][j]))$．...

問題概要 問題へのリンク 長さ$N$の文字列 $S$ が与えられる．$S$ に現れる文字は B と P だけ． 次の操作によって，B を左に P を右に寄せ $S$ を BB...BPP...P という形にする． 操作の最小回数を求めよ． $S$ の長さ3の部分列をとり，その部分の B を左に，P を右に寄せる． つまり，1回の操作は，以下のいずれか: (あ) PPB $\to$ BPP (い) PBP $\to$ BPP (う) PBB $\to$ BBP (え) BPB $\to$ BBP 制約 $3 \leq N \leq 2\times10^5$ 解 tutorialへのリンク 略解．click to open 奇数番のみ，偶数番のみの列を考えると， 操作は，次のいずれかになっている: (ア) 奇数列の隣接入替，偶数列の隣接入替 (あ, う) (イ) 奇数列と偶数列の B, P の入替 (い，え) 全体としてみたときの転倒数を $r$ とする．(ア)では転倒数が2減り， (イ) では転倒数が1減る． 最終形を考えると，奇数列，偶数列の B, P の個数は決まっている． だから，(イ) の最低必要な回数 $x$ が決まる． 「最初に (イ) を $x$ 回行って，あとの操作はすべて (ア)」が実現できれば， それ以上回数は減らせない．...

問題概要 問題へのリンク 整数 $N \geq 1$ と，整数の multiset $ A, B$ が与えられる．$A$, $B$ の要素数は $N$ である． 整数 $K$ で，multiset $ \{ a \bmod K \mid a \in A \}$ が $B$ と等しくなるものがあるか判定し， あれば1つ与えよ． 制約 $1 \leq N \leq 10^4$，$0 \leq a_i, b_i \leq 10^6$ 解 tutorialへのリンク 略解．click to open そういう $K$ があれば $K$ は，$d := \sum_i a_i - \sum_i b_i$ の約数になる． ($10^{10}$ 以下の数の約数の個数の最大値は $2304$ 個である．)