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