E - Stop. Otherwise... | AtCoder Regular Contest 102
包除原理とド・モルガンの法則使って求めるやつ。
六面サイコロを考える。つまりK=6として、出目の和が7になるペアは(1, 6), (2, 5), (3, 4)の3種類。これらのペアが一つもできない場合を求めたい。すべての出目の組をUとし、それぞれのペアができてしまう出目の組をそれぞれA, B, Cとすると求めるのは以下。
fは適当な関数。ここで特にf(0)=n(U)としているのに注意。一般にペアがm種類あるとき、
を求めればよい。
あとはf(i)の求め方を考える。上式の各項のi個のペアの作り方はC(m, i)通り。その一通りに対して、残りのN-2i個のサイコロの目の出方はどれでもよく、H(K, N-2i)通り。よって
int K, N; cin >> K >> N; for (int i = 2; i <= 2 * K; ++i) { int ps = min(K, i / 2) - max(1, i - K) + 1; mint ans = 0; for (int j = 0; j <= min(N/2, ps); ++j) { mint x = comb::C(ps, j) * comb::H(K, N - 2 * j); ans += x * (j % 2 ? -1 : 1); } cout << ans << endl; }
No.767 配られたジャパリまん - yukicoder
フレンズの数K<=20なので、O(K2 * K)みたいな計算量で解けそう。
とりあえず自明に求まるものを求めてみる。
任意のフレンズの集合に対してそのフレンズのいるところを必ず通る経路をすべて求める。フレンズの位置の集合をSとする。Sのすべての要素をa[i]<=a[j]かつb[i]<=b[j]ならばi, jという順に並び変えられるならば、Sのすべてを通る経路がある。そうでなければ経路の数は0。
この経路の求め方を考えてみる。これは簡単で、Sの要素をたとえばi1,i2,i3としてこの順に並び変えられた時
(0, 0) => (a[i1], b[i1]) => (a[i2], b[i2]) => (a[i3], b[i3]) => (H, W)
の経路を見るだけ。つまり、「=>」の部分の経路の数を求めて掛けるだけ。上下方向の差をh, 左右方向の差をwとしてP(h, w)みたいなのを求めて積をとる。
このような経路の数をf(S)とする。ここでf(S)が表しているものを裏返しに考えてみる。フレンズ全体をUとしてそこからSを除いたU∖Sを見てみる。T⊆U∖Sとし、g(T)をTに含まれるフレンズだけを「通らない」経路の数とするとメビウス変換によりg(T)が求まる。
フレンズの集合Vについてh(V)をVのフレンズにジャパリまんを渡す経路の数とする。h(V)はVに含まれるフレンズのところをだけを「通ってもよい」経路ともいえる。そしてg(T)を裏返しに見れば、U∖Tだけを「通る」経路の数といえるのでゼータ変換により解が得られる。
namespace comb { const int N = 200005; mint fact[N]; mint rev[N]; void init() { fact[0] = 1; for (int i = 1; i < N; ++i)fact[i] = fact[i - 1] * i; for (int i = 0; i < N; ++i)rev[i] = fact[i].inverse(); } mint C(int n, int r) { if (n < r)return 0; return fact[n] * rev[r] * rev[n - r]; } } template<class Val> vector<Val> zeta(vector<Val> f) { int len = (int)f.size(); for (int i = 0; (1 << i) < len; ++i) { for (int S = i; S < len; ++S)if (S >> i & 1) { f[S] += f[S ^ 1 << i]; } } return f; } template<class Val> vector<Val> mobius(vector<Val> f) { int len = (int)f.size(); for (int i = 0; (1 << i) < len; ++i) { for (int S = i; S < len; ++S)if (S >> i & 1) { f[S] -= f[S ^ 1 << i]; } } return f; } void solve() { comb::init(); int H, W, K; scanf("%d%d%d", &H, &W, &K); vector<tuple<int, int, int> > abk(K); rep(i, K) { int a, b; scanf("%d%d", &a, &b); abk[i] = tie(a, b, i); } sort(all(abk)); vector<mint> f(1 << K); vector<pii> p; rep(S, 1 << K) { p.clear(); p.emplace_back(0, 0); int T = (1 << K) - 1; rep(i, K) if (S >> i & 1) { int a, b, k; tie(a, b, k) = abk[i]; p.emplace_back(a, b); T ^= 1 << k; } p.emplace_back(H, W); mint res = 1; rep(i, sz(p) - 1) { int d = p[i + 1].first - p[i].first; int r = p[i + 1].second - p[i].second; if (d < 0 || r < 0) { T = -1; break; } res *= comb::C(d + r, d); } if (T >= 0)f[T] = res; } auto g = mobius(f); reverse(all(g)); auto h = zeta(g); reverse(all(h)); each(ans, h) { printf("%d\n", ans.toi()); } }
No.727 仲介人moko - yukicoder
解は Π_{0<=i<N}{H(i*2+1, 2)(N-i)2} / N!
ただし、Πは総乗、H(n, r) = C(n+r-1, r) とする。
これは以下のように得る。残った売り手買い手から1人ずつ選んでペアを作り、既存の順番に挿入するということを繰り返すことを考える。 既存の順番がi個のペアをすでに作っているとする。この時、売り手、買い手の選び方が(N-i)2通り。この2人をどこに挿入するか。既存の列は2i人を含み、その間と端に重複を許して2人を挿入するのでH(2i+1, 2)通り。 あとは挿入順を無視するためにN!で割る。
namespace comb { const int N = 2000006; mint fact[N]; mint rev[N]; void init() { fact[0] = 1; for (int i = 1; i < N; ++i)fact[i] = fact[i - 1] * i; for (int i = 0; i < N; ++i)rev[i] = fact[i].inverse(); } mint C(int n, int r) { if (n < r)return 0; return fact[n] * rev[r] * rev[n - r]; } mint H(int n, int r) { return C(n + r - 1, r); } mint P(int n, int r) { assert(n >= r); return fact[n] * rev[n - r]; } mint catalan(int n) { return fact[2 * n] * rev[n + 1] * rev[n]; } } void solve() { comb::init(); int N; cin >> N; mint re = comb::rev[N]; rep(i, N) re *= comb::H(2 * i + 1, 2) * (N - i)*(N - i); cout << re << endl; }
No.728 ギブ and テイク - yukicoder
i<jとする。 (i, j)が満たしたい条件は A[i]+R[i]>=A[j]かつA[i]>=A[j]-L[j]
jをループで固定する。jを昇順に見ていくならば A[i]+R[i]>=A[j]を満たすiはjが増加するごとに条件がきつくなる。 なのでi<jについて A[i]+R[i]の値を優先順位度付きキューで持っておいて、 A[i']+R[i']<A[j]となるような添え字i'を取り除いていく。
あとはA[i]>=A[j]-L[j]であるが、 取り除いたあとに残っているすべてのi<jとなる添え字iについて A[i]の値をBinary Indexed Treeで管理して条件を満たすものだけ数えればいい。
const int MAX_N = 300005; int N, A[MAX_N], L[MAX_N], R[MAX_N]; void solve() { cin >> N; rep(i, N)cin >> A[i]; rep(i, N)cin >> L[i] >> R[i]; // a+r<=2*10^9<INT_MAX priority_queue<pii, vector<pii>, greater<pii>> Q; BinaryIndexedTree<int> bit(N); ll re = 0; rep(i, N) { while (!Q.empty()) { auto p = Q.top(); if (p.first >= A[i]) { break; } else { bit.add(p.second, -1); Q.pop(); } } int p = lower_bound(A, A + N, A[i] - L[i]) - A; re += bit.sum(p, i); bit.add(i, 1); Q.push(mp(A[i] + R[i], i)); } cout << re << endl; }
D: Median of Medians - AtCoder Regular Contest 101 | AtCoder
中央値がxの場合=>中央値がx以上の場合
f(x) := 「x以上の値が中央値となる連続部分列の個数」とする。 ここで部分列がH(N, 2)個あるので、そのちょうど真ん中になるのが中央値。 つまり f(x) >= ceil(H(N, 2)/2) を満たす最大のxが解。fは単調増加なので二分探索が使える。
x以上の値が中央値となる連続部分列を数える
二分探索で条件を固定することで、入力を単純にとらえられる。 x以上の値とx未満の値かどうかだけをみる。前者が半数以上となるような 連続部分列は中央値がx以上である。 前者を+1, 後者を-1とすると、連続部分列の和が0以上ならば、中央値がx以上となるはず。 この数列をCとする。 とりあえず累積和を求めておく S[i] = Σ_{0<=j<=i}C[j]とすると [l, r)の部分和は S[r]-S[l]であり、中央値の条件は S[r]-S[l]>=0つまり S[r]>=S[l] よって、rを小さいほうから見ていって、Binary Indexed TreeなどでS[l]を数えていけばいい。
const int MAX_N = 100005; int N, A[MAX_N], B[MAX_N]; // sm(C[i]), sorted int S[MAX_N], T[MAX_N]; // 和のインデックス(BITで使う) int g(int y) { return lower_bound(T, T + N + 1, y) - T; }; ll f(int x) { // S[r]-S[l]>=0 // を満たすようなS[l]の数 BinaryIndexedTree<int> bit(N + 1); int b = B[x]; rep(i, N) { int c = A[i] >= b ? 1 : -1; T[i + 1] = S[i + 1] = S[i] + c; } sort(T, T + N + 1); ll cnt = 0; bit.add(g(0), 1); rep(i, N) { int j = g(S[i + 1]); cnt += bit.sum(0, j + 1); bit.add(j, 1); } return cnt; } void solve() { cin >> N; rep(i, N) { cin >> A[i]; B[i] = A[i]; } sort(B, B + N); int M = unique(B, B + N) - B; // ceil(H(N,2)/2) // = ceil(N*(N+1)/4) // オーバーフロー注意!! ll need = (N*(N + 1ll) + 3) / 4; int ok = 0, ng = M; while (ng - ok > 1) { int mid = (ok + ng) / 2; if (f(mid) >= need) { ok = mid; } else { ng = mid; } } cout << B[ok] << endl; }
E. Hash Swapping | soundhound2018-summer-final-open
方針 O(Qsqrt(N))で間に合いそうなので平方分割を試す
クエリは[l, r)で0-indexedとする。
f(x, i) = 106i ord(S[x][i])(0<=i<N) とおくと Σ_{l<=i<r}f(x, i) / (106l) が解。
平方分割の工夫
g(x, k) = Σ_{kR<=i<=(k+1)R}f(x, i)
とおく。
とりあえず[l, r)に含まれるすべての[kR, (k+1)R)について
swap(g(x, k), g(y, k))
はわかる。
このとき、f(x, i)、f(y, i)の更新をどうしたらよいか。
愚直にf(x, i)とf(y, i)を交換すると1クエリにO(N)かかってしまう。
そこでR = ceil(sqrt(N))として
f'(x, floor(i/R), i mod R) = f(x, i)
とする。
ここで
vector
次に[kR, (k+1)R)に収まらないインデックスiについて考える。 この添字の個数はO(sqrt(N))個。 その一通りについて f(x, i)とf(y, i)の値を交換する。(実際には多次元配列Gを使う) その分g(x, floor(i/R))とg(x, floor(i/R))へ足したり引いたりする。O(1)
よって全体でO(Qsqrt(N))
const int MA = 200005, R = 450; int N, M, ord[20][MA], Q; mint smo[20][R]; vector<mint> va[20][R]; mint& f(int x, int i) { RT va[x][i / R][i%R]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); cin >> N >> M; rep(i, M) { rep(j, R) { va[i][j].reserve(R); va[i][j].resize(R); } string s; cin >> s; mint pw = 1; rep(j, N) { ord[i][j] = s[j] - 'a' + 1; f(i, j) = pw * ord[i][j]; smo[i][j / R] += f(i, j); pw *= 1000000; } } cin >> Q; FOR(t, 1, Q + 1) { int typ, x, y, l, r; cin >> typ >> x >> y >> l >> r; --x; --y; --l; if (typ==1) { while (l%R && l<r) { smo[x][l / R] += f(y, l) - f(x, l); smo[y][l / R] += f(x, l) - f(y, l); swap(f(x, l), f(y, l)); l++; } while (r%R && l < r) { r--; smo[x][r / R] += f(y, r) - f(x, r); smo[y][r / R] += f(x, r) - f(y, r); swap(f(x, r), f(y, r)); } for (int i = l; i < r; i += R) { int j = i / R; swap(smo[x][j], smo[y][j]); swap(va[x][j], va[y][j]); } } else { mint re = 0; mint pw = mint(1000000).pow(l); while (l%R && l<r) { re += f(x, l++); } while (r % R && l < r) { re += f(x, --r); } for (int i = l; i < r; i += R) { int j = i / R; re += smo[x][j]; } re /= pw; cout << re << endl; } } }
