中央値がxの場合=>中央値がx以上の場合 f(x) := 「x以上の値が中央値となる連続部分列の個数」とする。 ここで部分列がH(N, 2)個あるので、そのちょうど真ん中になるのが中央値。 つまり f(x) >= ceil(H(N, 2)/2) を満たす最大のxが解。fは単調増加なので二…

排他的論理和が総和以下っぽい。詳しく説明する。 とする。 まずが成り立つ。更にも成り立つ。 部分文字列の左端lを固定してみる。このときr=lならば明らかに条件を満たす。 A[l]⊕A[l+1]⊕...⊕A[r] < A[l]+A[l+1]+...+A[r] が成り立つと仮定する。このとき、…

気づき 操作はkの降順だけ考えれば良い。 vに対して整数k1で操作したあとk2で操作したとする。 k1 <= k2を仮定する。 vをk1で割った余りv'は v' < k1 を満たす。 k1 <= k2より v'をk2で割った余りもv'である。よってk2による操作で値が変わらず、 k2の操作が…

解説付き 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]; } // 接頭辞の問題＝＞…

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

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

p[i]<=1000に注目する。p[i]/2000 <= 1000/2000 = 1/2 (1) i = 0,1,2,...,Tターンたったときに全種類そろっている確率をf[i]とし、これをすべて求めてl[i] = (p[i]-ε)/2000 の値で二分探索すればいい。ただし、(1)よりf[T]>=1/2でなければならない。そのよう…