AOJ 2606 : Perm Query
順列はいくつかのサイクルで表記できる。
[l, r)に含まれるサイクルの長さをc[l],...,c[r-1]のように表すと
lcm(c[l], ..., c[r])回だけ、各要素は値が変わる。i番目の要素は
lcm/c[i] 回だけサイクルを回るので、そのサイクルに含まれる数の和をS[i]とすると
i番目の要素についての和は
S[i]*lcm/c[i]
l≦i<rで和を取って
Σ[l≦i<r](S[i]*lcm/c[i])
がクエリ[l, r)に対する解。
問題はlcmの求め方で、lcmは大きい数になりうるのでmod 10^9+7で計算したい。
つまり
[l, r)に含まれるすべてのサイクルの長さについてlcmを計算したい。
[l, r)はO(N)の長さがあって1要素ずつ見ていくと間に合いそうにない。
そこでサイクルの長さごとに見ていく。
サイクルの長さの種類はたかだかO(√N)個しかない。なぜなら、サイクルの長さの和はNなので、
サイクルの長さの種類が最大となるのは
1+2+...+(k-1)+k = N
のような場合であるため。
よって、O(√N)個のすべてのサイクルの長さについて、そのサイクルの出現数を部分和で持っておけば、
各サイクルの長さが[l, r)で出現するかどうかすぐわかる。
事前にサイクルの長さに対して素因数分解しておけば、素因数の数はたかだかO(log(N))個なので
各クエリに対してO(log(N)√N)
全体でO(Qlog(N)√N)
int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, Q; cin >> N >> Q; vi p(N), vis(N); // S[i]/c[i]の部分和 vector<mint> sm(N + 1); // 素因数分解の結果 unordered_map<int, map<int, int> > fa; // lns[i]は長さiのサイクルの出現の部分和 unordered_map<int, vi> lns; rep(i, N)cin >> p[i], p[i]--; rep(i, N)if (!vis[i]) { // 新しいサイクルを見つけた vi a; ll s = 0; int x = i; do { a.push_back(x); vis[x] = 1; // サイクルに含まれる数の和 s += x + 1; x = p[x]; } while (x != i); int len = sz(a); if (!fa.count(len)) { fa[len] = factorize(len); lns[len] = vi(N + 1); } each(y, a) { // S[i]/c[i] sm[y + 1] = mint(s) / len; // 長さlenのサイクルはy番目を含む lns[len][y + 1] = 1; } } // 部分和の計算 rep(i, N)sm[i + 1] += sm[i]; each(q, lns) { vi &v = q.second; // 出現数の部分和 rep(i, N)v[i + 1] += v[i]; } while (Q--) { int l, r; cin >> l >> r; --l; mint s = sm[r] - sm[l], lcm = 1; // 各素因数について、素因数分解したときに最も多く現れたときの指数 unordered_map<int, int> ma; each(q, lns) { int len = q.first; vi &v = q.second; if (v[r] - v[l]) { each(ii, fa[len]) { // ここが最も時間がかかる smax(ma[ii.first], ii.second); } } } // 素因数分解→lcm each(q, ma) while (q.second--)lcm *= q.first; // s=Σ(S[i]/c[i]) cout << s*lcm << endl; } }
AOJ 1169 : 最強の呪文 (The Most Powerful Spell)
接頭辞の長さごとに、辞書順最小となるものを求めるようなダイクストラ法。ゴールへの経路は、もし閉路を含まなければN個以下の頂点からなるはずで、接頭辞の長さの最大値は6*(N-1)
これより長い接頭辞で、辞書順がさらに小さいような経路があれば、その呪文は閉路を含んでいるはずであり、辞書順がより小さい呪文を作れるのでNOを出力。そもそも経路がない場合も。
そうでなければ辞書順最小の呪文を出力。
AOJ 1330 : Never Wait for Weights
int N, M, INF = 10000000, vis[100001], dis[100001], U[100001], V[100001]; vector<pii> G[100001]; void solve() { rep(i, N)G[i].clear(), vis[i] = 0; // Union-Find木 UnionFind uf(N); // クエリの種類 // 0: 返答可能な質問 // INF: 返答不可能な質問 // -INF: 質問ではない vi knd(M); rep(i, M) { int u, v; char s[2]; // 入出力が多そうなのでcin/cout系は使わない scanf("%s%d%d", s, &u, &v); char c = s[0]; --u; --v; /* Union-Find木で2頂点で連結成分を管理。重さwの辺(u, v)と重さ-wの辺(v, u)を張っていく。 閉路ができる場合があるが、無視する。というのは、重さの設定に矛盾がないので、必ずパス(u, v)の間の距離が一定であるため。 つまり、こうして辺を張っていくと幾つかの森ができている。 */ if (c == '!') { int w; scanf("%d", &w); // 連結成分が異なるなら if (uf.find(u) != uf.find(v)) { G[u].emplace_back(v, w); G[v].emplace_back(u, -w); // 同じ連結成分になった uf.unite(u, v); } knd[i] = -INF; } else { /* 連結成分が異なるので、重さの比較ができない。 */ if (uf.find(u) != uf.find(v)) { knd[i] = INF; } else { /* 同じ連結成分に含まれるので、重さの比較ができる。 */ U[i] = u; V[i] = v; } } } /* 今、グラフは森になっている。各連結成分、つまり木を根つき木として考える。 u→vの距離 = (根→vの距離) - (根→uの距離) が成り立つ。 よって、事前に各連結成分について根を定めて根からの距離を求めておけばよい。 */ rep(i, N)if (!vis[i]) { stack<tuple<int, int, int> > stk; stk.push(mt(i, -1, 0)); while (sz(stk)) { int u, p, d; tie(u, p, d) = stk.top(); stk.pop(); vis[u] = 1; dis[u] = d; each(e, G[u])if (e.first != p)stk.push(mt(e.first, u, d + e.second)); } } rep(i, M) { if (knd[i] == INF)puts("UNKNOWN"); else if (knd[i] != -INF)printf("%d\n", dis[V[i]] - dis[U[i]]); } } int main(){ while (scanf("%d%d", &N, &M), N) { solve(); } }
AtCoder AGC 014 B: Unplanned Queries
性質を満たす木が存在する必要十分条件は、すべての頂点についてクエリに現れた回数が偶数であることである。
(1)すべて偶数回の出現だった場合
すべてのクエリについて
辺(a[i], b[i])で2頂点をつなぐ。ただし、a[i], b[i]がすでに同じ連結成分内にある場合はこのクエリを無視。
最終的にできた森から適当に木を作れば、性質を満たしている。
(2)奇数回現れる頂点がある場合
根付き木を考える。
mod 2のもとで
クエリ(u, v)は
(u, root), (v, root)
に分解できる。
奇数回現れる頂点のうち最も深いもの1つを頂点uとする。
頂点uを端点とするパスによってuとその親pをむすぶ辺(u, p)は奇数になっている。辺(u, p)の数を偶数にしたい。
そのために、uの子孫のうちuを除く頂点(その集合をSとする)の出現回数が合計で奇数でなければならない。しかし、そうなると奇数回現れる頂点でuより深いものが存在することになり矛盾する。よって、辺(u, p)の数は奇数になる。
AtCoder AGC 014 C: Closed Rooms
k回目の魔法で部屋を開いた状態にする操作は、k+1回目以降の移動にしか影響しない。
よって、魔法を以下のように捉え直す。
1回目の魔法は移動のみ
2回目の魔法は部屋を開く操作ののち、移動
2回目以降の操作はK個以下の部屋を開き、K個以下のマスを移動できるので、出口へまっすぐ進めばいい。よって1回目の移動でどのマスへ行けるかを探索で調べる。到達できた各マスについて、到達可能なマス(x, y)から外へ通じるマスまでの距離をd(x, y) とした時
min(ceil(d(x, y)/K)+1)
が解。
AtCoder AGC 014 D: Black and White Tree
int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<set<int> > G(N); rep(i, N - 1) { int a, b; cin >> a >> b; --a; --b; G[a].insert(b); G[b].insert(a); } /* 完全マッチングが存在するか判定 木なので、葉は必ずその親とペアになる。葉から貪欲にペアを作っていく。 */ // 頂点vを取り除いた, 頂点vは葉への辺をもつ。 vi rem(N), lev(N); queue<int> q; rep(i, N)if (sz(G[i]) == 1)lev[*G[i].begin()] = 1; rep(i, N)if (lev[i])q.push(i); while (sz(q)) { int u = q.front(), flag=0; q.pop(); // uは葉vと辺(u, v)でつながっている each(v, G[u]) { if (sz(G[v]) == 1 && !flag++) { // vは葉なので黒く塗る rem[v] = 1; } G[v].erase(u); if (sz(G[v]) == 1) { // 辺を減らすことで、頂点vが葉になった。 int w = *G[v].begin(); q.push(w); } } // uを白に塗る rem[u] = 1; } /* 完全マッチングが存在しなかった。 完全マッチングが存在しない木を 根付き木として考えて 最も深い葉で共通の頂点を親として持つものがあるならば、その親を白く塗れば先手の勝ち。(1) そうでない場合は、この2頂点を取り除く。その木にも当然完全マッチングが存在せず、よりサイズの小さい問題になった。 これを繰り返すと(1)に至るかまたは頂点数が1になるって先手の番になる。どちらも先手の勝ち。 */ rep(i, N)if (!rem[i] && sz(G[i]) == 0) { cout << "First" << endl; return 0; } // 完全マッチングが存在した // その場合、先手に対して後手は完全マッチングでペアになる頂点を選べばいい。 cout << "Second" << endl; }
yukicoder #515: 典型LCP
事前に文字列を辞書順にソートしておく。
l番目の文字列とr番目の文字列のLCPをlcp(l, r)のように表すことにする。
|lcp(l, r)| <= |lcp(l+1, r)|
が成り立つから
lcp(l, r)
= lcp(lcp(l, l+1), lcp(l+1, r))
よって、長さx以下のprefixについて、lcp(i, j)を求める問題をlcp(x, i, j)とすると、各クエリは(∞, l, r)のように表せて
(∞, l, r)
= (|lcp(l, l+1)|, l+1, r)
= (min(|lcp(l, l+1)|, |lcp(l+1,l+2)|), l+2, r)
= ...
= (min[l<=i<=r-1](lcp(i, i+1)), r, r)
したがって、事前に隣接する文字列のLCP、lcp(i, i+1)をすべて求めておけば、RMQで解が求まる。