Posts

問題概要 問題へのリンク 整数 $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$ 個である．)

ABC399-F Range Power Sum が， 積の和典型だとのことなので，関連記事へのリンクなど． リンク 積の和典型 - ei1333の日記 ABC399-F 問題概要 問題へのリンク $A = (A_1, \dots, A_N)$ が与えられる．次を mod 998244353 で求めよ: $$ \sum_{1 \leq l \leq r \leq N}\left( \sum_{l \leq i \leq r} A_i \right)^K $$ 制約: $N \leq 2\times 10^5$, $K \leq 10$． 解法 (累積和で2項展開しても解けるが，それは置いといて…) 以下， 公式解説 より． 次のように言い換えられる． ボールが $A_i$ 個入った箱が一列に並んでいる． 箱の間に，2個の仕切りを入れる． 2つの仕切りの間にあるボールに，$1, 2, \ldots, K$ と書かれたラベルを1枚ずつ貼る 仕切りの入れ方とラベルの貼り方をセットで考えて，この方法の数が，求める答になる． DP で求める． dp[i][j][k] = (箱 i まで見て，仕切りを j 個入れていて，ラベルを k 枚貼るような方法の数)

畳み込みやゼータ変換やメビウス変換に関するメモ

WolframAlpha への入力方法のメモです

std::map に「挿入か更新をする」ときの idiom をすぐに忘れてしまうのでメモしておく． std::map<S, T> mp; と宣言されているとする． 1. 無条件で，s の値を t にする 通常は次で良い: mp[s] = t; もともと s が有ったか無かったのかも知りたい場合や，s へのイタレータも欲しい場合には，次のようにする: auto [it, b] = mp.insert_or_assign(s, t); b には，挿入が行われたかどうかが設定されるので，b が false なら，もともとキー s が存在していたことがわかる．it は s へのイタレータ． 2. キー s が無ければ，値を t にする． 次のように書くと，s の探索が2回走ってしまう． if (mp.find(s) == mp.end()) mp[s] = t; 次のようにすれば 1回ですむ． mp.emplace(s, t); もともと s が有ったか無かったのかも知りたい場合や，s へのイタレータも欲しい場合には，次のようにする: auto [it, b] = mp.emplace(s, t); b には，挿入が行われたかどうかが設定されるので，b が false なら，もともとキー s が存在していたことがわかる．it は s へのイタレータ．...

デバッグに失敗した，ないし，長時間かかった間違いの記録 ABC212E Safety Journey 問題へのリンク 2023/07/05 あさかつ 無向グラフが，完全グラフからM本の辺を除いたものとして与えられている． 除く辺は $(u, v)$ の形で与えられている． dp[i][j] = (i 回の繰返し後，頂点 j に到達できる方法の数) という DP で， 全体から 除いた辺の分を引く． $(u, v)$ と $(v, u)$ の両方を引かなければならないところ， $(u, v)$ しか引かなかった． ABC279F BOX 2023/07/05 あさかつ タイプミス 正: if (rx == -1 and ry == -1) { 誤: if (rx == -1 and ry == 1) { ARC164B 2023/07/09 コンテスト 誤読． 正: 木の好きな頂点を選んで出発できる 誤: 木の根から出発する ABC222E Red and Blue Tree 2023/08/02 あさかつ...

階段関数を表現するライブラリ intervalSet の説明です．

ダブリングを行うライブラリを書きました．ソースはこちら ． 1. できること 1.1 基本用法 $f : [0, N) \to [0, N)$ が与えられた時， $r \in [0, R]$ と $i \in [0, N)$ に対して $f^{r}(i)$ を 計算する． 1.2 追加用法 上の $f$ とともに，モノイド $(M, \oplus)$ と $m: [0, N) \to M$ も与えられて， $r, i$ に対して $\bigoplus_{k = 0}^{r - 1} m(f^{k}(i))$ も計算する． 典型例: $i \mapsto f(i)$ を1回実行するごとに $m(i)$ だけのコストがかかるとき， $f^r(i)$ の実行に要するコストを求める． $[0..N-1]$ が円環状に並んでいる．$f^r(i)$ の実行で何周するか求める． この場合には，$m(i) := \textrm{ if } r(i) < i \textrm{ then } 1 \textrm{ else } 0$ とすればよい． tree の先祖-子孫パス上の辺の重みの最大値を求める 1....

復元方法も含めた最長増加部分列に関するまとめ