実は解候補はlca(A,B), lca(B,C), lca(C, A)の3通りしかない。 与えられた木を根付き木とし、簡単のため depth(A) <= depth(B) <= depth(C) とする。Aを考慮しなければ、下のような図が描ける。 (1)Aがパス(B,C)上にある場合 明らかにAが解になる。 A=lca(A,…

文字列a,ab,abc,abdが与えられているとする。上図のようなtrieを描いてみよう。 簡単のため、文字列の最大の長さは考えないでみる。 K=1とすると明らかにaだけを使えばいい。 では、K=2の場合は？ K=1のときと同じようにaを使おうとすると、うまくいかない。…

更新の操作は以下のように表せる。 A[i]+=s A[j]+=-s/(N-1), j!=i 前者を変形すれば A[i]+= (s+s/(N-1)) -s/(N-1) となる。なので 全体に-s/(N-1)を加算し、A[i]にs+s/(N-1)を加算したとすれば、1クエリO(1)で処理できる。

n=1のとき明らかにNOよってn>=2とする。とりあえず、挿入は考えずに配列を前の部分(S)と後の部分(T)に分けてみる。ただし、S,Tは空であってもよいとする。z=Σ[x∈S](x), w=Σ[y∈T](y)とする。場合1. z=wの場合 ある要素を選んで同じ場所に挿入すればいいからYE…

エディトリアル見て書いたコード。コメントつき /* エディトリアルのとおりの解法 */ /* 重さ1, 2のsouvenirだけを使ったとき、重さの和がiとする。 このときdp[i]=(x,y,z)は以下の意味。 xはコストの和の最大値 yは重さ1のsouvenirをいくつ使ったか。 zは重…

上図は3番目の入力例の文字列t="abcab"にダミーの1文字を加えたt+'#'="abcab#"に対してKMP法のDFAを描いたもの。!はその他の文字を表す。tはオーバーラップしてもよいので、最終状態からの遷移もほしい。そこで、末尾にダミーの文字を加えた。これにより、最…

解説付きコード /* 解説 二人とも好むアイテムの集合をX, MashaだけのはY, ArkadyだけのはZとする 全体でちょうどm個でなければならないが、とりあえずそのことは考えない。 Xからx個選ぶとする。xは|X|から0まで総当りする。 k-x個だけYとZから取る必要があ…

解説付きコード /* 解候補は4種類ある。 何も買わない コインとダイヤモンドでそれぞれ1個ずつ噴水を買う コインで2個噴水を買う ダイヤモンドで2個噴水を買う 前二者は自明 後二者について 噴水をコインで2個買うとする 安い方の必要なコイン数を固定すると…

まずa[i]は大きい方を優先して使ったほうがいいので降順にソートしておく。 2^17>10^5かつa[i]>=2より 掛け算は縦横合わせてたかだか17+17=34回 よって f[i番目までは掛けた][横の長さ]=縦の長さの最大値 をDPで解けばいい。

順列はいくつかのサイクルで表記できる。 [l, r)に含まれるサイクルの長さをc[l],...,c[r-1]のように表すと lcm(c[l], ..., c[r])回だけ、各要素は値が変わる。i番目の要素は lcm/c[i] 回だけサイクルを回るので、そのサイクルに含まれる数の和をS[i]とする…

接頭辞の長さごとに、辞書順最小となるものを求めるようなダイクストラ法。ゴールへの経路は、もし閉路を含まなければN個以下の頂点からなるはずで、接頭辞の長さの最大値は6*(N-1) これより長い接頭辞で、辞書順がさらに小さいような経路があれば、その呪文…

int N, M, INF = 10000000, vis[100001], dis[100001], U[100001], V[100001]; vector<pii> G[100001]; void solve() { rep(i, N)G[i].clear(), vis[i] = 0; // Union-Find木 UnionFind uf(N); // クエリの種類 // 0: 返答可能な質問 // INF: 返答不可能な質問 //</pii>…

性質を満たす木が存在する必要十分条件は、すべての頂点についてクエリに現れた回数が偶数であることである。 (1)すべて偶数回の出現だった場合 すべてのクエリについて 辺(a[i], b[i])で2頂点をつなぐ。ただし、a[i], b[i]がすでに同じ連結成分内にある場合…

k回目の魔法で部屋を開いた状態にする操作は、k+1回目以降の移動にしか影響しない。 よって、魔法を以下のように捉え直す。 1回目の魔法は移動のみ 2回目の魔法は部屋を開く操作ののち、移動 2回目以降の操作はK個以下の部屋を開き、K個以下のマスを移動でき…

int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<set<int> > G(N); rep(i, N - 1) { int a, b; cin >> a >> b; --a; --b; G[a].insert(b); G[b].insert(a); } /* 完全マッチングが存在するか判定 木なので、葉は必ずその親とペアにな</set<int>…

事前に文字列を辞書順にソートしておく。l番目の文字列とr番目の文字列のLCPをlcp(l, r)のように表すことにする。|lcp(l, r)| <= |lcp(l+1, r)|が成り立つからlcp(l, r)= lcp(lcp(l, l+1), lcp(l+1, r))よって、長さx以下のprefixについて、lcp(i, j)を求め…

f(X, Y)を質問(X, Y)の結果とすると f(0, 0) + f(10^9, 0) = 10^9 + 2AY AY = (f(0, 0) + f(10^9, 0) - 10^9) / 2 求まったAYを利用して AX = f(0, AY)

コメントつきコード // 頂点の数、辺の数、連結成分のID、最も遠い点までの距離、連結成分の直径 int N, M, Q, cmp[100001], far[100001], nc, dia[100001]; // グラフ、連結成分ごとに最も遠い点までの距離をすべてもってソートしたもの vi G[100001], F[10…

2番目の入力例n=10を考えてみよう。 とりあえず、(i+j) mod (n+1) = 0 となるような辺(i, j)はコスト0なので全部張ろう。 1-10 2-9 3-8 4-7 5-6 あとはコスト1以上の辺を貼るしかない。 実はすべてコスト1の辺で繋げられる。 10+2≡1 9+3≡1 8+4≡1 7+5≡1 よっ…

abのような形が残らないので、操作していくと最終的に bbb....baa...a のような形になる。 とりあえず実験してみる。 ab →bba bはaを飛び越えるときに1個から2個になった。 abに対する操作は1回。 aab →a<ab> →abba →<ab>ba →bbaba →bb<ab>a →bbbbaa aを2個飛び越えるこ</ab></ab></ab>…

コメント付きコード // 頂点の数、色の数、頂点vに含まれるアイスの数 int N, M, S[300001]; // グラフ, 頂点vに含まれるアイス vi G[300001], C[300001]; // 解, 色iを使ったかどうか int X[300001], use[300001]; int main(){ scanf("%d%d", &N, &M); rep(…

コメントつきコード /* 解法 漸化式で解を表して行列を作ってみる。 行列は添字ごとに異なるので累乗では解けない。 [l, r)の積 A[r-1]A[r-2]...A[l] の求め方 (1) セグメント木を使って求める http://yukicoder.me/problems/no/510 の解法 今回の問題ではTL…

sに含まれる文字xの数をn(x)とする。c, dが無いものと見做してsがa, bだけから成り立つと考えてみよう。f[i]を文字a, bをちょうどi個ずつ含む部分列の数とする。i>min(n(a), n(b))のときaまたはbの数が足りないからf[i] = 0i<=min(n(a), n(b))のときn(a)個の…

復習用コメント付きコード /* 思いつき方 頂点を黒く塗る その黒い頂点を含む部分木は？ 根まで行く距離が長過ぎる HL分解する */ /* HL分解 Heavy-Light Decomposition 木の構築 O(|V|+|E|) あらかじめ与えられた木について、頂点u,v間のパスをセグメント木…

細かくコメント書いてみた。 /* 2個の配列u,vを値(u[i], v[i])でソートする。 */ template<class S, class T> void psort(vector<S> &u, vector<T> &v, bool isGreater); int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vll X(N), Y(N); rep(i, N) { cin ></t></s></class>…