Codeforces #165 div1-C,div2-E Flawed Flow
http://www.codeforces.com/contest/269/problem/C
問題概要
N頂点、M辺のグラフが与えられ、頂点1がソース、Nがシンクである
ソースからシンクへの最大フローを流した時の、辺に流れた流量が辺ごとに与えられる(向きは与えられない)
フローが成り立つようにそれぞれの辺について向きを決めよ
ただし、得られるフローはサイクルを含んではいけない
グラフは連結で、答えは必ず存在する
N,M<=2*10^5
1<=流量<=10^4
方針
サイクルを含まないので、得られるフローのグラフは、トポロジカル順序をつけることが出来る。
ソースは最も順序の早い点で、そこから出る辺はすべてソースと逆向きに流れている
ここで、ソースに隣接する点のうち、どれかはトポロジカル順序がソースの次に小さいはずである
トポロジカル順序がソースの次に小さい頂点をvと置くと、vにはソース以外からフローが流れこまないので、
ソースから向かう辺の流量と、それ以外のつながれた辺の流量が等しいはず
逆に、ソース->vの辺以外はvから流れださなければフローが成立しないので、
ソースの時と同様にvから流す
残った頂点の中でトポロジカル順序が最も早いものが必ず見つかるはずなので、これを繰り返せば答えが求まる。
ソース、シンクの扱いに注意
O(N+M)
using namespace std; static const int INF =500000000; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} typedef long long int lint; typedef pair<int,int> pi; int n,m; vector<pair<pi,pi> > g[200005]; int in[200005],flow[200005]; int vis[200005]; int ans[200005]; int main(){ scanf("%d%d",&n,&m); for(int i=0;i<m;++i){ int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b; g[a].push_back(make_pair(make_pair(b,c),make_pair(0,i))); g[b].push_back(make_pair(make_pair(a,c),make_pair(1,i))); flow[a]+=c; flow[b]+=c; } memset(ans,-1,sizeof(ans)); queue<int> q;q.push(0); while(!q.empty()){ int v=q.front();q.pop(); vis[v]=1; for(int i=0;i<g[v].size();++i){ pair<pi,pi>& e=g[v][i]; if(vis[e.first.first]) continue; in[e.first.first]+=e.first.second; ans[e.second.second]=e.second.first; if(in[e.first.first]==flow[e.first.first]/2 && e.first.first!=n-1) q.push(e.first.first); } } for(int i=0;i<m;++i) printf("%d\n",ans[i]); return 0; }
Codeforces #165 div1-A,div2-C Magical Boxes
http://www.codeforces.com/contest/269/problem/A
問題概要
N種類の大きさの箱がある。
i番目の箱の大きさは2^k(i)で、a(i)個ある。
新しく2^pの大きさの箱を作って、それにすべての元の箱を詰めたい。
ある箱には、それより小さい大きさの箱を、半分の大きさなら4個、1/4の大きさなら16個、というように詰めることができ、入れ子状に詰めることも出来る。
ある箱に、サイズの異なる箱を詰めることも出来る(半分の大きさの箱1つ、1/4の大きさの箱12個 のように)
pの最小値を求めよ
N<=10^5 a,k<=10^9
方針
ある箱が入れ子状に詰められているとしても、
サイズごとに、互いに干渉しない箱を別々に新しい箱に詰めている、とみなすことができる
なので、それぞれのサイズについて、箱を詰めることが出来る最小のサイズを求め、maxを取る。
サイズ2^k(i)のa(i)個の箱が詰まる最小のサイズは、2^(p-k(i))>=a(i)を満たす最小のp
ただし、p>k(i)
O(N*log a)
int n; pair<int,int> box[100005]; int main(){ cin>>n; int res=0; for(int i=0;i<n;++i){ scanf("%d%d",&box[i].first,&box[i].second); if(box[i].second==1) res=max(res,box[i].first+1); else{ while(box[i].second>1){ box[i].second=(box[i].second+3)/4; ++box[i].first; } res=max(res,box[i].first); } } printf("%d\n",res); return 0; }
POJ Solved Graph
PKUのアカウントのsolvedを横軸時間、縦軸solvedのグラフにして表示します。
複数アカウントに対応しています。名前を入れるところに、コロン(',')区切りで空白などを入れずに複数のアカウントを入力してください
ボタンを押すと、その時のウィンドウのサイズに合わせてグラフを作ります
ページ読み込みに結構時間がかかるので、マッタリ待ちましょう。合計solvedが4000とか行くようだと1分弱かかります
同じディレクトリに、page.htmlというファイルを作りますが気にしなくていいです。プログラムを終了したら削除しても問題無いです
サイズを変更すると勝手に大きさを変えてくれます
Windows用です また、.NET Framework 4が必要です
リンク:
https://docs.google.com/open?id=0B4bMtJgy4TSHZzR2RU5BWGNTQzQ
グラフの例:
Last updated:2013/1/9
制作言語はC#です
セグメント木 問題集
https://twitter.com/hogloid/status/284225774142251008
こんなことを言ったので
書きます
問題は、セグメント木を使う解法がおそらく楽で、セグメント木が問題の重要な部分で、JOIとかPCKでない問題、とします(JOIの問題とかみんな知ってる&解いてるだろうし)
あと、明確に悪問と分かる問題は載せません。
解説が欲しい場合は、(一応僕は全部解いたので)僕になにか言ってくれると解説ページを開設すると思います。下のコメント欄とかにどうぞ。
記事を出してからも、ボチボチ更新していく予定です。
☆の数は、主観的な難易度です。
書き終わって気づきましたがかなりグロイ問題ばかりなのでやばいですが頑張ってください
似たような記事 http://d.hatena.ne.jp/tozangezan/20111111/1320993464
(こっちのほうが、おそらく簡単な問題が多いです 問題はかぶってないはずです)
☆
- Sliding Window http://poj.org/problem?id=2823
☆☆
- タコヤキオイシクナール http://arc008.contest.atcoder.jp/tasks/arc008_4
☆☆☆
- Lucky Arrays http://www.codeforces.com/problemset/problem/256/E
- XOR on Segment http://www.codeforces.com/problemset/problem/242/E
- Running Away From the Barn http://www.usaco.org/index.php?page=viewproblem2&cpid=213
- Mars Map http://www.spoj.com/OI/problems/NKMARS/
- Mushroom Gnomes -2 http://www.codeforces.com/problemset/problem/138/C
- Flying Right http://poj.org/problem?id=3038
- Dungeon (I) http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1505
- Thwarting Demonstrations http://www.codeforces.com/problemset/problem/191/E
☆☆☆☆
- Little Elephant And Tree http://www.codeforces.com/problemset/problem/258/E
- TorCoder http://www.codeforces.com/problemset/problem/240/F
- Little Elephant and Inversions http://www.codeforces.com/problemset/problem/220/E
- PrimeCompositeGame http://community.topcoder.com/stat?c=problem_statement&pm=11506
- Team Selection http://www.spoj.com/OI/problems/NKTEAM/
- Cartesian Tree http://poj.org/problem?id=2201
- Quadrant Queries https://www.interviewstreet.com/challenges/dashboard/#problem/4e48b9cb8917f
- Differece is Beautiful http://poj.org/problem?id=3419
- Two Permutations http://www.codeforces.com/problemset/problem/213/E
- Donkey and Stars http://www.codeforces.com/problemset/problem/249/D (Math含む)
- Dividing Kingdom http://www.codeforces.com/contest/260/problem/E(面倒 セグメント木使わなくてもできる)
- Cubes http://www.codeforces.com/contest/243/problem/D
- Camping Groups http://www.codeforces.com/problemset/problem/173/E
☆☆☆☆☆
- Fence http://www.codeforces.com/problemset/problem/232/D (セグメント木分少なめ)
- Alien DNA http://www.codeforces.com/problemset/problem/217/E
- FoxSearchingRuins http://community.topcoder.com/stat?c=problem_statement&pm=11286
- Mountains https://www.spoj.com/OI/problems/NKMOU/
- Do Use Segment Tree http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2450
- Cutting Cake http://poj.org/problem?id=2843
- Two Segments http://www.codeforces.com/contest/193/problem/E
Codeforces #157 div1E Little Elephant and Tree
URL:http://www.codeforces.com/contest/258/problem/E
問題概要
N頂点からなる全域木がある。根は頂点1。
それぞれの頂点はあるリストを持っている。
M回処理をする。i番目の処理は、
頂点uiより下の部分木、頂点viより下の部分木 の頂点すべてのリストに、数iを入れる。
処理が終わったら、それぞれの頂点について、
自分以外の頂点で、リストに一つでも同じ数を含む頂点の数を求めよ。
N<=100000
方針
segtreeで解けます。
ある頂点xとリストに同じ数を含む頂点は、xの子孫とも同じ数を含む、ということに注意。
まず、euler-tourをして、segtreeを建てます。
それぞれの頂点で、処理のui,viのどちらかになっているなら、もう片方の頂点の部分木の範囲に+1します。
また、自分の頂点の部分木にも+1します。
それぞれの頂点で、segtreeの列の上で正の数を持っている要素の数を求めます。
これが、同じ数をもつ頂点に対応します。
ただし、値が正になったら必ず自分を含んでいるので-1します
上の処理は、segtreeがそれぞれのノードで、
「子に伝播させていない変更」「区間の最小値」「区間の最小値を取る要素の数」
を覚えれば、なんとかできます。
O(NlogN)
using namespace std; static const int INF =500000000; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} typedef long long int lint; typedef pair<int,int> pi; struct segtree{ int n,n2; int val[400005],mini[400005],lazy[400005]; void init(int n_){ n2=n_; n=1; while(n<n_) n<<=1; for(int i=0;i<n_;++i){ mini[i+n-1]=0; val[i+n-1]=1; } for(int i=n-2;i>=0;--i){ mini[i]=0; val[i]=val[i*2+1]+val[i*2+2]; } } void add(int a,int b,int i,int l,int r,int v){ if(a<=l && r<=b){ lazy[i]+=v; mini[i]+=v; return; } if(b<=l || r<=a) return; int md=(l+r)>>1; if(lazy[i]){ lazy[i*2+1]+=lazy[i]; mini[i*2+1]+=lazy[i]; lazy[i*2+2]+=lazy[i]; mini[i*2+2]+=lazy[i]; lazy[i]=0; } add(a,b,i*2+1,l,md,v); add(a,b,i*2+2,md,r,v); mini[i]=min(mini[i*2+1],mini[i*2+2]); val[i]=0; if(mini[i]==mini[i*2+1]) val[i]+=val[i*2+1]; if(mini[i]==mini[i*2+2]) val[i]+=val[i*2+2]; } int query(){ if(mini[0]==0) return n2-val[0]; return n2; } }; segtree seg; int n,m,cnt; int begin[100005],end[100005]; vector<int> g[100005]; void dfs(int v,int p){ begin[v]=cnt++; for(int i=0;i<g[v].size();++i){ int to=g[v][i]; if(to==p) continue; dfs(to,v); } end[v]=cnt; } vector<int> connect[100005]; int ans[100005]; void dfs2(int v,int p){ for(int i=0;i<connect[v].size();++i){ int to=connect[v][i]; seg.add(begin[to],end[to],0,0,seg.n,1); } ans[v]=seg.query(); if(ans[v]>0) --ans[v]; for(int i=0;i<g[v].size();++i){ int to=g[v][i]; if(to==p) continue; dfs2(to,v); } for(int i=0;i<connect[v].size();++i){ int to=connect[v][i]; seg.add(begin[to],end[to],0,0,seg.n,-1); } } int main(){ cin>>n>>m; for(int i=0;i<n-1;++i){ int a,b;scanf("%d%d",&a,&b);--a;--b; g[a].push_back(b); g[b].push_back(a); } dfs(0,-1); for(int i=0;i<m;++i){ int a,b;scanf("%d%d",&a,&b);--a;--b; connect[a].push_back(b); connect[b].push_back(a); connect[a].push_back(a); connect[b].push_back(b); } seg.init(n); dfs2(0,-1); for(int i=0;i<n;++i) printf("%d ",ans[i]); putchar('\n'); return 0; }
CFのEでsegtreeが出ておきながら解かないor解けないのさすがにどうにかしたい
Codeforces #152 div1C,div2E Piglet's Birthday
URL http://www.codeforces.com/contest/249/problem/C
問題概要
棚がN個ある。
それぞれの棚には、最初、未開封のハチミツ瓶がa[i]個入っている。
q回イベントがある。
それぞれのイベントでは、棚uからランダムにk個ハチミツ瓶を選び、それらを開けて、棚vに入れる。
それぞれのイベント後、未開封のハチミツ瓶を一つも含んでいない棚の数の期待値 を小数で出力せよ。
N,q<=100000
0<=a[i]<=100
k<=5
u,v<=N
方針
確率dpです
dp[i][j]=棚番号iで 未開封のハチミツ瓶の数がj となる確率
とすると、未開封のハチミツ瓶の数は絶対に増えないのでうまく行きます。
最初に瓶がない棚もあることに注意
using namespace std; static const int INF =500000000; int n; double dp[100005][105]; double tmp[105]; int init[100005],has[100005]; double C[1000005][10]; //コンビネーション int main(){ for(int i=0;i<105;++i) for(int j=0;j<105;++j) dp[i][j]=0; for(int i=0;i<1000005;++i){ C[i][0]=1; for(int j=0;j<min(i,9);++j) C[i][j+1]=C[i-1][j]+C[i-1][j+1]; } //コンビネーションを予め計算 scanf("%d",&n); double cur=0; for(int i=0;i<n;++i){ scanf("%d",&init[i]); has[i]=init[i]; dp[i][init[i]]=1; if(init[i]==0) ++cur; } int q;scanf("%d",&q); while(q--){ int u,v,k;scanf("%d%d%d",&u,&v,&k);--u;--v; cur-=dp[u][0]; for(int j=0;j<105;++j) tmp[j]=0; for(int i=0;i<=init[u];++i) if(dp[u][i]>1e-30){ for(int j=0;j<=k && j<=i;++j){ //j:=いくつ未開封の瓶を選ぶか tmp[i-j]+=dp[u][i]*C[i][j]*C[has[u]-i][k-j]/C[has[u]][k]; //has[u]個からk個選ぶとき、i個の未開封瓶がj個選ばれる確率 } } for(int j=0;j<105;++j) dp[u][j]=tmp[j]; has[u]-=k; has[v]+=k; cur+=dp[u][0]; printf("%.10f\n",cur); } return 0; }
cinはただでさえ遅いですが小数に対してはめちゃくちゃ遅かった。注意
Codeforces#148 div1C,div2E World Eater Brothers
URL:http://www.codeforces.com/contest/238/problem/C
問題概要
有向全域木が与えられる。2つ頂点を選んで、そこからすべての頂点へ辺の向きに従って到達できるように辺の向きを変える。
変えなければいけない辺の数をコストとすると、最小のコストはいくらか。
頂点数<=3000
方針
2つの頂点で到達すればよいので、ある一つの辺で覆う範囲を分割できる。
分割した後は、
まずある頂点を選び、そこを始点としたとき分割したグラフ内で向きを変える辺の数(cost'と呼ぶ)を数える。
ここで、その選んだ頂点と隣接する頂点を始点とする向きを変える辺の数は、
最初に選んだ頂点が隣接する頂点に向いているなら、cost'+1
そうでないなら、cost'-1
となることが簡単に分かる。これはO(N)で実装できる
すべての辺で分割し、上の方針を繰り返す。O(N^2)
小さいケースに注意!
using namespace std; static const int INF =500000000; typedef pair<int,int> pi; int n; vector<pi> g[3005]; pi es[3005]; int dfs(int v,int p){ int res=0; for(int i=0;i<g[v].size();++i){ pi& e=g[v][i]; if(e.first==p) continue; res+=e.second+dfs(e.first,v); } return res; } int move(int v,int p,int val){ int res=val; for(int i=0;i<g[v].size();++i){ pi& e=g[v][i]; if(e.first==p) continue; res=min(res,move(e.first,v,val+1-e.second*2)); } return res; } int main(){ cin>>n; for(int i=0;i<n-1;++i){ int a,b;cin>>a>>b;--a;--b; g[a].push_back(make_pair(b,0)); g[b].push_back(make_pair(a,1)); es[i]=make_pair(a,b); } int ans=INF; if(n<=2) ans=0; for(int i=0;i<n-1;++i){ int A,B; A=es[i].first;B=es[i].second; int sum1=dfs(A,B),sum2=dfs(B,A); ans=min(ans,move(A,B,sum1)+move(B,A,sum2)); } cout<<ans<<endl; return 0; }
こういう回の場合、BよりCを先にやったほうが(解ける人にとっては)いいです