コンテストサイト : UVa Online Judge
解いたのはA,E,Hだけ。他は一部読んだけど分からなくて、半分くらいは読んでないかも。そもそもAだけ解いて消えるつもりだったのでよいかなと思いました。
でも、要求される知識としては、ＪＯＩ的にも良い感じのコンテストだと思います。
Problem A - Answering Queries on a Tree
頂点N(1<=N<=10^5)の木が与えられます。最初に全ての頂点には10ある色のうちの1つのどれか色がついています。以下のクエリを処理しなさい。
- 頂点uの色をcに変える。
- 頂点対(u,v)の間に存在するユニークなパス(木なので)で最も出てきた色の数を答える。
動画見ながらダラダラ書いたのに1時間半くらいでFirstAcceptanceだったらしいウケる。
解法
反転↓
LCAとBITを用いた。
LCAで得られる共通祖先をpとでもすると、
- (u,v)に含まれる色の数 = (p,u)に含まれる色の数 + (p,v)に含まれる色の数. ただし親の色重複カウントには気をつける。
そして、pの子xに対し、(p,x)間に含まれる色の数は木を列として処理することで、O(log n)で処理できるようにする。
どんな列かというと、行きのときに加算し、帰るときに減算するみたいな感じで、木を列として構築し、それを色の数(高々10)だけBITを作っておいてやる。
書き換えるとき、BITの弄る位置は高々2つで、まあO(log n)で処理できる。
Problem E – Enemy At The Gates
- 頂点数Nと辺の数M(制約では違うけど、N-1 <= M <= N*(N-1)/2らしい)が与えられる。
- その制約を満たした上で、橋(その辺を除くとグラフが分断されるような辺)の数を最大化するようなグラフにおいての橋の最大数を答える問題。重複辺とかは禁止。
Mも10^5以下だと思ってオーバーフローしてた。悔しい。
解法
反転↓
戦略を考えてみると、
- まずN-1本使って木を作る。
- 余っていたらどこかにループができるが、ループに属した辺は橋となりえなくなるので出来るだけループは小さくしたいので小さく繋ぐ。
- そう考えていくと、一部の頂点だけ使って完全グラフ作る感じで消費したらよさそう。
- とりあえず小さいやつからループでいくつの頂点使って完全グラフ作るか決定する。ある頂点数で完全グラフ作ったときのできる辺の数で余った辺をカバーできたら抜け出し。
O(N)。二分探索すればO(log N)かな。
Problem H – Happy 10/9 Day
- n,b,d,M (2≦b≦100 , 1≦n,M≦10^12 , d＜b) が与えられる。
- b進数で、dがn桁連続した数を考え、それをMで割った余りを答える。
解法
- 明らかに、dがn桁連続した数 = d * Σb^i(i=0..n-1)なので、Σb^i(1111....11みたいな数)だけ考えてやればよい。
- b-1と互いに素の時、Σb^i(i=0..n-1) = (b^N-1)/(b-1)なので、b-1の逆元が求めれる。逆元を求めるのに拡張ユークリッドの互助法を用いて、このケースに対しては高速に処理できる(φ関数使うと√Nなので遅いヨ)。が、しかし互いに素じゃないとき面倒くさい、ので別の方法を考える(デデドン)。
- ダブリング使おうダブリング！！ b = 10のときを考えてみると、
11 = 1 * 10 + 1
1111 = 11 * 100 + 11
11111111 = 1111 * 10000 + 1111
....
- とやっていくと、1が2^k個連続した数の表があれば、それを掛け合わせることによって上手くいきそう。
- あとは実装・・・なんだけど、(10^12)^2ってlong longから溢れるので、掛け算を半分ずつに分解しながら余りとりつつO(log n)で計算してやる。遅い。
ソース
A
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; vector<int> tree[100000]; int parent[20][100000]; int depth[100000]; int color[100000]; int bit[11][200010]; vector<int> e,v; int appear[100000]; int last[100000]; int N,M,T; int add(int bit[],int x,int v){ while(x <= 200010){ bit[x] += v; x += x & -x; } } int get(int bit[],int x){ int ans=0; while(x){ ans+=bit[x]; x-=x&-x; } return ans; } int f(int pos,int prev,int dep){ e.push_back(pos); v.push_back(color[pos]); depth[pos] = dep; parent[0][pos] = prev; for(int i = 0 ; i < tree[pos].size() ; ++i){ int next = tree[pos][i]; if(prev != next){ f(next,pos,dep+1); } } v.push_back(-color[pos]); e.push_back(pos); } int genLCA(){ for(int i = 1 ; i < 20 ; i++){ for(int j = 0 ; j < N ; j++) if(parent[i-1][j] != -1) parent[i][j] = parent[i-1][parent[i-1][j]]; } } int getLCA(int x,int y){ if(depth[x] > depth[y]) swap(x,y); for(int i = 19 ; i >= 0 ; i--) if( (depth[y] - depth[x]) >> i & 1 ) y = parent[i][y]; if(x==y) return x; for(int i = 19 ; i >= 0 ; i--){ if(parent[i][x] != parent[i][y] ){ x = parent[i][x]; y = parent[i][y]; } } return parent[0][x]; } int costGet(int p,int x,int col){ return get(bit[col],appear[x]) - get(bit[col],appear[p]); } int main(){ scanf("%d",&T); while(T--){ memset(parent,-1,sizeof(parent)); memset(appear,-1,sizeof(appear)); memset(bit,0,sizeof(bit)); for(int i = 0 ; i < 100000 ; i++) tree[i].clear(); e.clear(); v.clear(); v.push_back(0); e.push_back(0); scanf("%d%d",&N,&M); for(int i = 0 ; i < N ; i++){ scanf("%d",&color[i]); } for(int i = 0 ; i < N-1 ; i++){ int a,b; scanf("%d%d",&a,&b); --a,--b; tree[a].push_back(b); tree[b].push_back(a); } // gen f(0,-1,0); for(int i = 1 ; i < e.size() ; i++){ int num = abs(v[i]) , cc = v[i] < 0 ? -1 : 1; add(bit[num],i,cc); if(appear[e[i]]==-1) appear[e[i]] = i; else last[e[i]] = i; } genLCA(); for(int i = 0 ; i < M ; i++){ int t,a,b; scanf("%d%d%d",&t,&a,&b); if(!t){ a--; add(bit[color[a]],appear[a],-1); add(bit[color[a]],last[a],+1); add(bit[b],appear[a],+1); add(bit[b],last[a],-1); color[a] = b; }else{ --a,--b; int p = getLCA(a,b) , s = 0; for(int j = 1 ; j <= 10 ; j++){ s = max(s,costGet(p,a,j)+costGet(p,b,j)+(color[p]==j)); } printf("%d\n",s); } } } }
E
#include <iostream> #include <cassert> using namespace std; int main(){ int T; cin >> T; while(T--){ long long n,m; cin >> n >> m; long long good = n-1; assert(m >= n-1); assert( (long long)n*(n-1)/2 >= m); m -= (n-1); if(m > 0){ for(long long i = 3 ; i <= n ; i++){ if(i * (i-1) / 2 - (i-1) >= m){ good -= i-1; break; } } } cout << good << endl; } }
H
#include <iostream> #include <cstdio> using namespace std; typedef long long ll; ll mult(ll a,ll b,ll M){ return b ? (mult(a*2%M,b/2,M) + (b%2?a:0))%M : 0; } ll b_pow(ll x,ll n,ll M){ return n ? mult(b_pow(mult(x,x,M)%M,n/2,M),(n%2?x:1),M) : 1ll; } int main(){ int T,t=1; cin >> T; while(T--){ long long N,M,B,D; scanf("%lld%lld%lld%lld",&N,&B,&D,&M); long long c = 0; long long w = D; long long bbpow = B; for(int i = 0 ; i < 62 ; i++){ if(N>>i&1){ c = mult(c,bbpow,M) + w; c %= M; } w = mult(w,bbpow,M) + w; w %= M; bbpow = mult(bbpow,bbpow,M); bbpow %= M; } cout << "Case " << t << ": "<< c << endl; t++; } }
