問題1<=a,b<=Na mod b >= K組(a, b)としてありうるものを数えよ1<=N<=10^5 解説0<=K<b, q>=0r >= Ka = bq + rr = a-bqK<=r</b,>

問題二人でニムっぽいゲーム山N個各山A[i]個の石山iから1<=a<=floor(X/K[i])個取れるA[i]=0, 1<=i<=N の状態で自分のターンになったら負け1<=N<=2001 <= A[i], K[i] <= 10^9 解説Grundy数がわかればいい。g(x, k) : x個の山, k個取れるときのGrundy数k>xのと…

問題Pは順列|P| = NLIS(P) = ALDS(P) = BPを求めよ(ないかも)1<=N,A,B<=3*10^5 解説 LISとLDSで重複している要素はたかだか1つなのでA + B <= N + 1Nが大きすぎると駄目で最大のケースで例えばA=2, B=3とするとN = A*B=6で3, 2, 1, 6, 5, 4のように構成でき…

便宜上、時刻を[1, n]=> [0, n)で表すことにする。f(i):= 時刻iにコンテストを開始したときの参加人数の合計とする。(f(i), -i) を最大にするようなiを求めたいのでf(i)が知りたい。f(i)は累積和で計算する。f(i) = g[i] のような配列gを考えるとタイムゾー…

f(n, m):= nxnのときの配置可能な最大の1の数とする。ただし、1<=m<=n任意のnについてf(n, 1) = 0よって x = 0 のときは例外として処理する。以下、m>=2、x>=1とする。nxnのm-free行列について1が最大となる置き方の一つはmxmの部分行列ごとに、右下に1個0の…

すべての頂点iについて(a[i], i)を終点候補として優先順位度付きキューに突っ込んおく。(u[i], v[i]) 間をコスト2w[i]の無向辺で接続したグラフでダイクストラ法っぽいことをする。 まず往復についてであるが、往路と復路の最短経路の長さが等しいことは明ら…

すべての順列を見ていくのは明らかに無理なので、a[j]ごとに計算していく。つまり、f[a] = f[a] + a[M(もとの配列の添字はj)] となるような順列を数える。その数えをg(j)としておく。g(j)さえ求まれば解はΣa[j]g(j) a[j]より大きい値の数えをx, a[j]以上値の…

dp[i][d]:= 「i番目の台からd∈{左, 右}に落ちたとき最後にボールが行き着くx座標」とする。 iをyの昇順に決定することでこのDPを解ける。よって、事前にソートしておくことでi<=j ⇔ y[i]<=y[j]とする。台iの端dからボールが落ちたとする。このとき、x[i][d]…

実験すると以下を得る最下位ビットが1のとき勝ち最下位ビットが0のとき負け 証明(1)最下位ビットが1のとき常に最下位の1を選ぶことで相手に最下位ビットが0の状態を押し付けられる。値の変化はDAGになっていて(つまり値が必ず減少する)相手のターンで最後に…

ダイクストラ法っぽいことをする。 (時間、誰(ウサギ、カメ), 場所, 始点) のようなタプルを優先順位付きキューに入れていく。 まず、 場所＝始点、時間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…