AIM Tech Round 3 (Div. 1) C. Centroids
問題
頂点数 n の木 T 上の点 v が T の centorid であるとは, T から v を取り除いて得られる任意の連結成分が, 全て頂点数 n/2 以下であることを言う。
各頂点について, その頂点が以下の操作を一回以下許したとき centroid になるかどうかを判定せよ。
操作：木のある辺を消して, 好きな辺を加える(ただし新しいグラフも連結でなければならない)。
解法
操作を許さない場合にどうなるかを考えます。この場合はかなり単純です。頂点 v から伸びる辺の頂点から構成される部分木が, 全て n/2 以下の連結成分で構成されているか判定すれば良いです。いちいち頂点 v を根にして木dp しているとまにあわないですが, 0 を頂点にした木のみを考えて, 親方向側の連結成分の個数は n - (v の部分木のサイズ) というようにすれば良いです。
次に操作を許す場合を考えます。頂点 v の部分木でサイズが n/2 より大きいものがあった場合, その部分木の一部を切り取って v に直接つなぎかえるのが最適です。ここで部分木の頂点 ch で 2 通りの場合分けをします。
0 を根とした木でも ch が v の子である場合
この場合は, ch 以下の部分木を単純に調べるだけで良いので, euler_tour とか用意しておいてその中で部分木のサイズが n/2 である最大のものを求めます。ch の部分木のサイズ - この部分木のサイズ が n/2 以下なら操作をして centroid になることになります。
0 を根とした木で ch が v の親である場合
この場合がややこしいです。さらに二通りに分けます。
・つなげる木が v の祖先である場合
この場合, v からつなぎなおす頂点を a とすると, v - ch の木は,
- (a の部分木サイズ) - (v の部分木サイズ) の木
- n - (a の部分木サイズ) の木
に別れることがわかります。 n - (a の部分木サイズ) が n/2 以下で最大のものを覚えておけばこの中で (a の部分木サイズ) - (v の部分木サイズ) が n/2 以下になるものがあるかは, O(1) でわかります。
・つなげる木が v の祖先でない場合(要するに v の祖先の子孫のうち v の部分木以外のやつ)
木dp するとき dfs から抜け出すタイミングで部分木のサイズのメモしていくと, 頂点 v にたどり着いたときにメモされているのは, v 祖先の子孫の部分木のサイズのみになっています(直接の先祖はまだ v が子にあるので dfs から抜けておらず, サイズがメモされていない)。
よって, 部分木のサイズが n/2 以下なら 部分木のサイズをメモする, というようにやれば同じようにできます。
この手法でやるときは一回 dfs した後もう一回グラフを逆順にして再び dfs しなければいけないことに注意です。
// セグメント木(RMQ 対応) // update: k 番目の値を a に変更 // query: [l, r) の区間の最大値を求める template<typename T> struct ST { vector<T> seg; int size; ST(int n) { size = 1; while (size < n) size *= 2; seg.resize(2*size-1, 0); } inline T merge(T x, T y) { return max(x, y); } void update(int k, T a) { k += size-1; seg[k] = a; while (k > 0) { k = (k-1)/2; seg[k] = merge(seg[k*2+1], seg[k*2+2]); } } T query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return seg[k]; T vl = query(a, b, k*2+1, l, (l+r)/2); T vr = query(a, b, k*2+2, (l+r)/2, r); return merge(vl, vr); } T query(int a, int b) { return query(a, b, 0, 0, size); } }; const int MAXN = 400400; vi G[MAXN]; // Euler-Tour const int MAXSIZE = MAXN; int BEGIN[MAXSIZE], END[MAXSIZE]; vector<int> euler_tour; int K; void createEulerTour(int v, int p) { BEGIN[v] = K++; euler_tour.push_back(v); for (int el : G[v]) { if (el == p) continue; createEulerTour(el, v); euler_tour.push_back(v); K++; } END[v] = K; } int subSize[MAXN]; pii maxi[MAXN]; int n; int getSize(int v, int p) { int& ret = subSize[v]; pii& ma = maxi[v]; ma.first = 0, ma.second = -1; for (int ch : G[v]) if (ch != p) { int tmp = getSize(ch, v); if (ma.first < tmp) { ma.first = tmp; ma.second = ch; } ret += tmp; } ret++; int tmp = n - ret; if (ma.first < tmp) { ma.first = tmp; ma.second = p; } return ret; } int ans[MAXN]; int tsize; void dfs(int v, int p, ST<int>& seg, int top) { //cout << v << " " << top << " " << tsize << endl; if (maxi[v].second == p) { if (subSize[top]-subSize[v] <= n/2) ans[v] = 1; else if (n-subSize[v]-tsize <= n/2) ans[v] = 1; } else { int ch = maxi[v].second; int tmp = seg.query(BEGIN[ch]+1, END[ch]); if (maxi[v].first - tmp <= n/2) ans[v] = 1; } if (n - subSize[v] <= n/2) top = v; for (int ch : G[v]) if (ch != p) { dfs(ch, v, seg, top); } if (subSize[v] <= n/2) tsize = max(tsize, subSize[v]); } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for (int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } // 部分木のサイズを求める getSize(0, -1); // euler tour して部分木のサイズをメモ createEulerTour(0, -1); ST<int> seg(euler_tour.size()); for (int i = 0; i < n; i++) { if (subSize[i] > n/2) { seg.update(BEGIN[i], 0); } else { seg.update(BEGIN[i], subSize[i]); } } dfs(0, -1, seg, 0); tsize = 0; for (int i = 0; i < n; i++) reverse(G[i].begin(), G[i].end()); dfs(0, -1, seg, 0); for (int i = 0; i < n; i++) { cout << ans[i] ; if (i < n-1) cout << " "; } cout << endl; return 0; }
AIM Tech Round 3 (Div. 1) B. Recover the String
問題
0, 1 のみから構成される文字列で, 以下を満たすものを作れ。
- 00 の部分文字列が a00 個ある
- 01 の部分文字列が a01 個ある
- 10 の部分文字列が a10 個ある
- 11 の部分文字列が a11 個ある
連続部分文字列ではないことに注意。
解法
0 が n 個あるとすると, 00 の部分文字列は n*(n-1)/2 個あります。これから n がほとんど一意に決められます(n = 0 と n = 1 は区別できない)。
同様に a11 の情報から 1 の個数 m をほとんど一意に決められます。
0, 1 の区別はめんどくさいので, for 文で n+i, m+j を調べることにしましょう。以下では n, m は一意に確定したとします。
01, 10 の部分文字列は合計で n*m 個あります。a01 の個数から考えていくとすると, 0 の後に 1 が m 個続くようなものがいくつあるか, 1 が m-1 個続くようなものがいくつあるか, というように順番に調べていけば必ず所望の文字列が見つかることが分かります。
const string no = "Impossible"; string calc(vi a, int n, int m) { if (n*(n-1)/2 != a[0]) return no; if (m*(m-1)/2 != a[3]) return no; if (a[1] + a[2] != n*m) { return no; } if (n == 0 && m == 0) return "0"; string ret; for (int i = m; i > 0 && a[1] > 0; i--) { int x = a[1] / i; a[1] %= i; for (int j = 0; j < x; j++) { ret += '0'; n--; } ret += '1'; m--; } for (int i = 0; i < m; i++) ret += '1'; for (int i = 0; i < n; i++) ret += '0'; return ret; } string solve() { vi a(4); for (int i = 0; i < 4; i++) cin >> a[i]; int n = 0; while (n*(n-1)/2 < a[0]) n++; int m = 0; while (m*(m-1)/2 < a[3]) m++; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) { string t = calc(a, n+i, m+j); if (t != no) return t; } return no; } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << solve() << endl; return 0; }
AOJ 2439 Hakone
解法
まず, '-' があるところは順位が一意的に決まるので, 無視して良いです。与えられる文字列は 'U' と 'D' しか含まれないものとしましょう。
そしたら dp します。問題では今の中継地点での i 位の人が, 前の中継地点では何位なのかの場合の数を求めれば良いわけですが, 雰囲気としては以下のような戦略を取ります。
- C[i] = 'D' なら, [0, i) に所望のチーム(順位が落ちてきたチーム)がないとおかしいので, ここで C[i] に対応するチームを確定させる
- C[i] = 'U' なら, まだ所望のチームはどこかよくわからないので, 放っておく
具体的には以下のようにやります。
dp[i][j][k] = (i 番目まで見て, j チームはまだどこに割り当てられるか確定しておらず, k チーム割当先が残っているような場合の数) とします。割当先が残っている k チームというのは, C[l] = 'U' だったようなもので, まだどうしようか決めてないやつですね。
dp[0][0][0] = 1 であり, dp[n][0][0] が求めるべき値です。
このとき, dp[i][j][k] からは以下のように遷移します。
- C[i] == 'D' の時,
- 割当先が決まっていない j チームの中から C[i] に割り当てるものを決めるが, i 番目のチームはどこに割り当てるか決めない。
- 割り当て方は, j 通りあるので, dp[i+1][j][k] += dp[i][j][k] * j
- 割当先が決まっていない j チームの中から C[i] に割り当てるものを決め, かつ i 番目のチームを k チームのどれかにする。
- 割り当て方は j * k 通りなので, dp[i+1][j-1][k-1] += dp[i][j][k] * j * k
- 割当先が決まっていない j チームの中から C[i] に割り当てるものを決めるが, i 番目のチームはどこに割り当てるか決めない。
- C[i] == 'U' の時,
- その i 番目はどこにも割り当てない場合 これは dp[i+1][j+1][k+1] += dp[i][j][k]
- i 番目を今までに割り当てられていない k 個のどれかに割り当てる場合, dp[i+1][j][k] += dp[i][j][k] * k
これで解けます。
ただ上の遷移をよく見ると j = k のところ以外は dp[i][j][k] = 0 となることに気付くので, O(N^2) で解けます。
O(N^2)
const int MAXN = 222; const int MOD = 1e9+7; ll dp[MAXN][MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; string s; for (int i = 0; i < N; i++) { char c; cin >> c; if (c != '-') s += c; } N = s.size(); dp[0][0] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) { if (s[i] == 'D') { dp[i+1][j] += dp[i][j] * j % MOD; if (j) dp[i+1][j-1] += dp[i][j] * j * j % MOD; } else { dp[i+1][j+1] += dp[i][j]; dp[i+1][j] += dp[i][j] * j; } } for (int j = 0; j <= i+1; j++) dp[i+1][j] %= MOD; } cout << dp[N][0] << endl; return 0; }
O(N^3)
const int MOD = 1e9+7; ll dp[222][222][222]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; string s; for (int i = 0; i < N; i++) { char c; cin >> c; if (c != '-') s += c; } N = s.size(); dp[0][0][0] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) for (int k = 0; k <= i; k++) { if (s[i] == 'D') { dp[i+1][j][k] += dp[i][j][k] * j % MOD; if (j > 0 && k > 0) dp[i+1][j-1][k-1] += dp[i][j][k] * j * k % MOD; } else { dp[i+1][j+1][k+1] += dp[i][j][k]; dp[i+1][j][k] += dp[i][j][k] * k % MOD; } } for (int j = 0; j <= i+1; j++) for (int k = 0; k <= i+1; k++) { dp[i+1][j][k] %= MOD; } } cout << dp[N][0][0] << endl; return 0; }
Codeforces Round #366 (Div. 2) C. Thor
問題
q 個のクエリが飛んでくる。それぞれのクエリは type, x の二つの整数から構成され,
- type = 1 の時, 種類 x のボールが飛んでくる
- type = 2 の時, 今までに飛んできた種類 x のボールをすべて捨てる
- type = 3 の時, 今まで飛んできたすべてのボールのうち, 最初の x 個のボールを捨てる
それぞれのクエリが投げられた直後, 手元にあるボールの数を求めよ。
解法
D[x]: 種類 x のボールが投げられたタイミングをすべて記録したもの
S[x], T[x]: 種類 x のボールのうち, 手元にあるものの区間([S[x], T[x]) の区間 i について, D[x][i] というボールがある)
memo[i]: i 番目に来たボールはまだ手元にあるか
というようにデータを持っておきます。すると,
- type 1 については, D[x].push_back と T[x]++ でだいたい済む
- type 2 については, [S[x], T[x]) の区間に含まれる i について, memo[D[x][i]] = false にする
- type 3 については, memo[x] までをすべて false にする
ということをやれば良いです。すでに調べたところを二重に調べなければ, これらのクエリはすべて全体として O(Q) で対処可能です。
const int MAXN = 300300; vi D[MAXN]; int S[MAXN], T[MAXN], R[MAXN]; bool memo[MAXN]; int main() { int n, q; scanf("%d %d", &n, &q); int note = 0, ans = 0, last = 0; for (int i = 0; i < q; i++) { int type, x; scanf("%d %d", &type, &x); if (type == 1) { D[x].push_back(note); memo[note] = true; //R[note] = x; note++; ans++; T[x]++; } else if (type == 2) { for (int i = S[x]; i < T[x]; i++) { if (memo[D[x][i]]) { ans--; memo[D[x][i]] = false; } } S[x] = T[x]; } else { for (int i = last; i < x; i++) { if (memo[i]) { ans--; memo[i] = false; //S[R[i]]++; } } last = max(last, x); } printf("%d\n", ans); } return 0; }
これ 2000 人も解けるのね…
AOJ 2397 Three-way Branch
問題
Three-way Branch | Aizu Online Judge
W*H のグリッドが与えられる。これらのうち, N 個のセルは通れなくなっている。あるセル(x, y) からは (x-1, y+1) or (x, y+1) or (x+1, y+1) にのみ行ける場合, (0, 0) から (W-1, H-1) までの経路は何通りあるか。
解法
W がまぁまぁ小さくて H が超でかいので行列累乗な感じがします。
障害物は N 個しかないので,
- 障害物のある行になるまでは行列累乗
- 障害物ある行では 対応するところの場合の数を 0 にする
というようにやれば O(W^3 log H * N) でできます。…結構ギリギリですが。
typedef long long number; typedef vector<number> vec; typedef vector<vec> matrix; const int MOD = 1e9+9; // O( n ) matrix Identity(int n) { matrix A(n, vec(n)); for (int i = 0; i < n; ++i) A[i][i] = 1; return A; } // O( n^3 ) matrix mul(const matrix &A, const matrix &B) { matrix C(A.size(), vec(B[0].size())); for (int i = 0; i < (int)C.size(); ++i) for (int j = 0; j < (int)C[i].size(); ++j) for (int k = 0; k < (int)A[i].size(); ++k) { C[i][j] += A[i][k] * B[k][j]; C[i][j] %= MOD; } return C; } // O( n^3 log e ) matrix pow(const matrix &A, ll e) { if (e == 0) return Identity(A.size()); if (e == 1) return A; if (e % 2 == 0) { matrix tmp = pow(A, e/2); return mul(tmp, tmp); } else { matrix tmp = pow(A, e-1); return mul(A, tmp); } } // O(n) number tr(const matrix &A) { number ans = 0; for (int i = 0; i < (int)A.size(); ++i) ans += A[i][i]; return ans; } // O( n ) number inner_product(const vec &a, const vec &b) { number ans = 0; for (int i = 0; i < (int)a.size(); ++i) ans += a[i] * b[i]; return ans; } // O( n^2 ) vec mul(const matrix &A, const vec &x) { vec y(A.size()); for (int i = 0; i < (int)A.size(); ++i) for (int j = 0; j < (int)A[0].size(); ++j) (y[i] += (A[i][j] * x[j] % MOD)) %= MOD; return y; } const int MAXN = 33; int W, N; ll H; ll solve() { vector<pair<ll, int> > P(N); for (int i = 0; i < N; i++) { cin >> P[i].second >> P[i].first; P[i].first--; P[i].second--; } sort(P.begin(), P.end()); vec v(W); v[0] = 1; ll now = 0; for (int i = 0; i < N; ) { matrix mat(W, vec(W)); for (int j = 0; j < W; j++) { if (j-1 >= 0) mat[j][j-1] = 1; mat[j][j] = 1; if (j+1 < W) mat[j][j+1] = 1; } v = mul(pow(mat, P[i].first-now), v); now = P[i].first; int ni = i; while (ni < N && P[i].first == P[ni].first) ni++; for (int j = i; j < ni; j++) v[P[j].second] = 0; i = ni; } matrix mat(W, vec(W)); for (int i = 0; i < W; i++) { if (i-1 >= 0) mat[i][i-1] = 1; mat[i][i] = 1; if (i+1 < W) mat[i][i+1] = 1; } v = mul(pow(mat, H-1-now), v); return v[W-1]; } int main() { cin.tie(0); ios::sync_with_stdio(false); for (int t = 1; ; t++) { cin >> W >> H >> N; if (W == 0) break; cout << "Case " << t << ": " << solve() << endl; } return 0; }
Educational Codeforces Round 16 D. Two Arithmetic Progressions
解法
k, l の組を一つ求められれば, 後は x が lcm(a1, a2) の周期で解になるので簡単です(実装が楽とは言っていない)。
a1 * k + b1 = a2 * l + b2 を変形すると
a1 * k - a2 * l = b2 - b1 となります。
これの解は, 拡張ユークリッドの互除法を使えば求められます。これを使うと
a1 * x + a2 * y = g (g は a1, a2 の最大公約数) という形の x, y, g を求めることができ, 全体を (b2-b1)/g 倍すれば k = x, -l = y となっている, というわけです。
後はめんどくさいですがゴニョゴニョします。
下のコードでは, この後
- k, l を 0 以上に調整する
- x が L 以上になるように調整する
- L <= x <= R となるものの数を求める
というようにやりました。全部二分探索です。
なんか素直に実装すると 10^18 まわりがめんどくさそうなので python で実装しました。
python ってなんかカッコよくかかないといけない感じがしますが下のコードはダサダサです。
def extgcd(a, b): x, y = 0, 0 d = a; if b != 0: d, y, x = extgcd(b, a%b) y -= (a//b) * x else: x, y = 1, 0 return (d, x, y) def main(): a1, b1, a2, b2, L, R = map(int, input().split()) # とりあえず k, l の候補を出す g, k, l = extgcd(a1, a2); b = b2-b1; if (b%g != 0): print (0) return k *= b//g l *= -b//g # k >= 0, l >= 0 を満たすようにする low = -2**100 high = 2**100 while high-low > 1: med = (low+high)//2 tk = k+med*a2//g tl = l+med*a1//g if (tk >= 0 and tl >= 0): high = med else: low = med k = k+high*a2//g # x >= L を満たすようにする x = a1*k+b1 low = -1 high = 2**100 lcm = a1*a2//g while high - low > 1: med = (low+high)//2 tx = x+med*lcm if tx >= L: high = med else: low = med x = x+high*lcm # x <= R を満たすものの数を求める low = 0 high = 2**100 while high-low > 1: med = (low+high)//2 tx = x+med*lcm if (tx <= R): low = med else: high = med if low == 0 and x > R: print (0) return print (low+1) return if __name__=="__main__": main()
Codeforces Round #369 (Div. 2) E. ZS and The Birthday Paradox
問題
整数 n, k が与えられる。
p = 2^n として, 1 - (p! / p^k * (p-k)!) の分母と分子を求めよ。ただし分母と分子は非常に大きな値になることがあるので, 10^6+3 で割ったあまりを求める。
(本当は p < k の場合は場合分けしないといけない)
解法
上では p! / p^k * (p-k)! と書きましたが, p*(p-1)*...*(p-k+1) / p^k と書く方が考えやすいです。
まず分母のほうから考えましょう。p^k を考えるだけなら簡単に出来ます。ただ, 分子で割られるので, そこがちょっと注意です。p が必ず偶数であることに注意すると, 2 で割られる回数は, p の分の n 回と, (p-1) * ... * (p-k+1) の分(これは k-1 にいくつの 2 の成分が含まれているかで求められる)です。
次に分子です。最終的に 10^6+3 で割ったあまりを求めるわけなので, k > 10^6+3 である場合は, 上記の掛け算の結果は 0 です。そうでない場合は, 直接計算すれば良いでしょう。2^m の成分がありますが上と同じように k-1 に含まれる 2 の成分の数分だけ割り算すれば良いです。
const int MOD = 1e6+3; ll mod_pow(ll x, ll p, ll MOD) { ll a = 1; while (p) { if (p%2) a = a*x%MOD; x = x*x%MOD; p/=2; } return a; } // mod_inverse ll mod_inverse(ll a, ll m) { return mod_pow(a, m-2, m); } int main() { cin.tie(0); ios::sync_with_stdio(false); ll n, k; cin >> n >> k; if (n <= 61 && 1ll<<n < k) { cout << "1 1" << endl; return 0; } // 分母を求める ll mother = 1; // 減らされる分母の数 ll cnt = n; { ll K = k-1; while (K) { cnt += K/2; K /= 2; } mother = mod_pow(2, n, MOD); mother = mod_pow(mother, k, MOD); mother *= mod_pow(mod_inverse(2, MOD), cnt, MOD); mother %= MOD; } // 分子を求める ll child = 1; { if (k >= MOD) child = 0; else { ll first = mod_pow(2, n, MOD); for (int i = 0; i < k; i++) { (child *= first-i) %= MOD; } if (child < MOD) child += MOD; } // 2 で割りまくる作業をする (child *= mod_pow(mod_inverse(2, MOD), cnt, MOD)) %= MOD; } child = (mother-child+MOD)%MOD; cout << child << " " << mother << endl; return 0; }
