ダイクストラ法っぽいことをする。 (時間、誰(ウサギ、カメ), 場所, 始点) のようなタプルを優先順位付きキューに入れていく。 まず、 場所＝始点、時間0で両者をすべての頂点からスタートさせる。 以降、各始点からの最短経路だけを考える。 今いる場所と始…

蛍光灯が途切れずに照らしている範囲を左端から右端へ伸ばしていこう。 最適解では、手前で使った蛍光灯をi、次の蛍光灯をjとすると、l[i]<l[j] が成り立つ。なので、事前に蛍光灯をlの昇順にソートしておく。 dp[x] = 0からxまでが途切れずに照らされているときの最小コスト とする。dp[L]が解。 はじめ dp[0] = 0である。 蛍光灯をソートされた順にみよう。いま、i番目の蛍光灯の使用を考る。dp[r[i]]が更新されるかもしれない。 蛍光灯は[l[i], r[i]] の範囲を照らすので、 前の範囲 => (重複) => [l[i], r[i]] のようになっていれば、左端からr…</l[j]>

解説付き const int MO = (int)1e9 + 7; string S[2001]; RollingHash rh[2001]; int f[2001][2001]; mint ans[2001], fact[2001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; rep(i, N) { cin >> S[i]; } // 接頭辞の問題＝＞…

p(T)を 読み上げられたカードの集合がTであるときのパターン数とする。 p(Φ) = 1 p(T(!=Φ)) = Σ[i ∊ T] ( p(T-{i}) ) で簡単に求まる。 e(T)を読み上げられたカードの集合がTであるときの 期待値 と パターン数の積とする。 E[K] * P[N,K] = Σ[T⊆読み札, |T|…

各桁に使える数は0,1,6,8,9のいずれかであってその特徴は以下のようになる。 先頭可 先頭不可 中心可 1 8 0 中心不可 6 9 先頭からceil(N/2)桁が決まると、残りfloor(N/2)桁は1通りに定まる。なので先頭からceil(N/2)桁だけ考える。場合分けする。 <1> Nが偶…

SAの値が決まっているとする。 f[i](l,r)をB以外の問題について正答数がiとしたときのl<=B[j]

const int R = 14; // isp[k-1][l][r]は // 部分文字列s[l, r)が // k-回文であるかどうかを表す bitset<5001> isp[R][5000]; // 部分文字列s[l, r)のハッシュ値 pii ha[5001][5001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); string s; cin >…

// 思いつき方 // 明るさが最大11種類しかないことに注目 // s, x, y // 部分和sm[s][x][y2]-sm[s][x][y1]は // 初期の明るさsの星のうち、 // (x, y1), (x, y1+1), ... , (x, y2-1) // にある星の数 int sm[11][101][101]; int main(){ ios::sync_with_stdi…

f(i, x, y) をi番目までの値のうちx個を使って z * 5^x * 2^y を作れるとして、その最大のy ただし、2∤zかつ5∤z これをDPで解く。 つまり、素因数分解したときの形で 5の次数は添え字として、2の次数は最大値として計算していけばいい。 ちなみに5の次数は l…

値1からNまで順にみていき、もともと空の配列のどこかに1つずつ挿入する。 今、1~K-1の値からなる順列のどこかにKを挿入したい。Kが挿入できる位置は、K-1の位置だけに依存する。(K+1は順列内にはないので） よって、以下のようなDPを考えればよい。 dp[i][j…

まず1番目のスイッチを押すかどうか決める。1番目のライトをON/OFFするのは1番目のスイッチだけなので、1番目のライトがONならば押さない。OFFならばスイッチをおす。これで1番目のスイッチを押すかどうか決めて処理した。以後、1番目のスイッチは考えない。…

(1) (R1+C1) ≢ (R2+C2) (mod 2) の場合 移動できない。市松模様の同じ色しか移動できない。 以下、(1)でないと仮定する。 (2) (R1,C1) = (R2,C2)の場合 0回 (3) (R1, C1)が(R2,C2)の対角線上にある場合 1回 (4) (R1, C1)が(R2,C2)の対角線上にない場合 まず…

i!=jとしたとき辺(i, j)または(j, i)のどちらか1つだけを必ず使いたい。すべての異なる2値{i, j}でそうしたい。最大フローっぽいが、出次数の制約も考えなければならない。出次数の制約より、x!=iとして(x, i)であるような辺はs[i]個以下でなければならない…

まず初期状態のdeviationを計算しておく。 1回のcyclic shiftでdeviationの値がどのように変化するかを知りたい。 基本的には p[i] < iのときp[i]の位置はiに近づくので、そのような値はdeviationを1だけ減らす。 p[i]>=iのときp[i]の位置はiから離れるので…

まず与えられた木の全点対の距離を計算しておく。 これを d[u][v]: (u, v)間の距離 としておく。 d[u][v] ∈ Sかつu!=v であるような辺(u, v)をすべて持つようなグラフをHとする。このグラフでスタート地点の頂点0から探索して到達可能な頂点の集合をVとする…

ab<=bc<=caを仮定すると下の図のように解を構成できる。 実際はab, bc, caの大小関係はこのとおりとは限らない。なので、ソートしてから3個の文字列を作ってみる。あとはこの3個の文字列がa, b, cのどれに対応するかを全部試して、実際にLCSを計算してみれば…

magical bridgeの数はたかだか100個しかないので、使うmagical bridgeの数も100個以下である。di[v][a]: magical bridgeをa回使ったときのSiからvの最短距離。ただし、magical bridgeの距離は0とする。ダイクストラ法によりd1とd2を事前に計算しておく。xをm…

実は解候補は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]がすでに同じ連結成分内にある場合…