TTPC2015 解答
とりあえずP以外解けたので(自分の解答なので想定かどうかは知らない)
A:やるだけ
B:貪欲
C:実装
D:実装
E:特殊マスが関係ないのに右に2つ伸ばす みたいなのは意味が無い(左右に1ずつのばす とかは意味がある) ので2^K * 4^2 全部試せばOK
F:0と9以外では揃わない.0がおいてあるところでcarryがなければ0をあわせる,9がおいてあるところでcarryがあれば9をあわせる.それ以外だとそこで合わせるのは不可能で,そして次にcarry出来るか選べるのでそう持っておく.これで下の桁から貪欲で行ける(いけるのにスルーしても次の一個が増えるだけなので(09090みたいなのだと1個おきになる)).
G:逆から見る.hceまでは貪欲,次にtが来たら,iの前のtの方を優先する(どうせ完成はさせれるのでiの受け入れが増えるように)
H:多角形を三角形に分割すればより面積が小さくなるので基本的に三角形だけ.しかし全ての対角線が原点を通る場合はこれが出来ない.四角形の場合だけこれがあるので四角形まで見ればOK.キツネみたいな凹四角形に注意.
I:右端を正しくするには右端を選び続ければOK.(右端をNとすると,Nが来ないかぎり右端を選び続けられる.同じ数xが二回出てくるとするとxが送られた場所から呼び戻すのにxが必要なのでxが二つあることになりおかしい.よってNが出てきて終了する)
J:dp[i][j]=残りi人で長さj以下のサイクルを使った.長さjのサイクルをいくつ使うか全部試して遷移.N/jくらいしか試さなくていいので全体では調和級数っぽくなってO(N^2logN).
K:i人が参加している試合の数 を上位i人の合計が超えるとアウト.証明は知らない.
L:まず赤だけでフロー.この時点の残余グラフでs,tとつながってるとこをそれぞれ覚えて,そこが繋がらないようにカットすればいいのでこれもフロー.S,Tからさっきの所にinfをはやし,残余グラフでまだ存在する辺もinfに変える(ここは切っちゃいけないので).
M:奇数頂点のとこだけが関係するNimです.(奇数頂点からいくつか動かされた場合,Nimと同様のことをする.偶数頂点からなんか動かされた場合はそいつをそのまま次へ送る.)
N:明らかににぶたんできる形で,T固定するとただの牛ゲーになる.負閉路ができると式が成り立たなくなりアウトなので検出して終わり.
O:LIS+LDS.ある点を共有するしかない場合-1になる.LISの総数*LDSの総数 は簡単にわかる.
それぞれの点を共有するLIS,LDSの数もわかる.
完全に左右に分裂してることはありえないことが簡単にわかるので,この両方の値を求めて一致してれば共有しない奴がない(つまり-1)で,そうでなければ引かなくていい.値はでかいのでmodで求めればだいたい(mod-1)/modの確率で正しい答えになる.
P:ワカリマセン
F
int main(){ string s; cin>>s; int N=s.size(); reverse(all(s)); int on=0; // both->2 int a=0; rep(i,N){ if(s[i]=='0'&&on!=1){ a++; on=0; }else if(s[i]=='9'&&on!=0){ a++; on=1; }else{ on=2; } } cout<<a<<endl; }
G
int main(){ string s; cin>>s; int N=s.size(); if(N%6){ puts("No"); return 0; } reverse(all(s)); int x[6]={}; rep(i,N){ if(s[i]=='h'){ x[0]++; }else if(s[i]=='c'){ if(x[0]==0){ puts("No"); return 0; } x[0]--; x[1]++; }else if(s[i]=='e'){ if(x[1]==0){ puts("No"); return 0; } x[1]--; x[2]++; }else if(s[i]=='t'){ if(x[2]==0){ if(x[4]==0){ puts("No"); return 0; } x[4]--; x[5]++; }else{ x[2]--; x[3]++; } }else if(s[i]=='i'){ if(x[3]==0){ puts("No"); return 0; } x[3]--,x[4]++; }else{ puts("No"); return 0; } } if(x[5]==N/6) puts("Yes"); else puts("No"); }
L
struct edge {int to,cap,rev,X,id;}; const int MAX_V=102,INF=1e8; vector<edge> G[MAX_V]; bool used[MAX_V]; void init(){ rep(i,MAX_V) G[i].clear(); rep(i,MAX_V) used[i]=0; } void add_edge(int from, int to, int cap,int id){ //directed edge e1={to,cap,G[to].size(),1,id}; edge e2={from,0,G[from].size(),0,id}; G[from].push_back(e1); G[to].push_back(e2); } int dfs(int v,int t,int f){ if(v==t) return f; used[v]=true; for(int i=0;i<G[v].size();i++){ edge &e=G[v][i]; if(!used[e.to] && e.cap>0){ int d=dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; while(true){ memset(used,0,sizeof(used)); int f=dfs(s,t,INF); if(f==0) return flow; flow+=f; } } bool vis[MAX_V],vit[MAX_V]; void dfss(int v){ vis[v]=1; for(edge e:G[v]){ if(e.X!=1) continue; if(e.cap>0&&!vis[e.to]) dfss(e.to); } } void dfst(int v){ vit[v]=1; for(edge e:G[v]){ if(e.X!=0) continue; edge e2=G[e.to][e.rev]; if(e2.cap>0&&!vit[e.to]) dfst(e.to); } } bool use[400]; int x[400],y[400]; int main(){ int N,A,B; cin>>N>>A>>B; rep(i,A+B) cin>>x[i]>>y[i],x[i]--,y[i]--; rep(i,A){ add_edge(x[i],y[i],1,i); } int f=max_flow(0,N-1); dfss(0); dfst(N-1); int S=N+1,T=N+2; // init(); rep(i,N){ for(edge e:G[i]){ if(e.X==1){ if(e.cap>0) use[e.id]=1; } } } init(); rep(i,A) if(use[i]){ add_edge(x[i],y[i],INF,1); } rep(i,B){ add_edge(x[i+A],y[i+A],1,1); } rep(i,N) if(vis[i]) add_edge(S,i,INF,1); rep(i,N) if(vit[i]) add_edge(i,T,INF,1); /* cout<<"vis "; rep(i,N) if(vis[i]) cout<<i<<" "; cout<<"\nvit "; rep(i,N) if(vit[i]) cout<<i<<" "; puts(""); */ int F=max_flow(S,T); cout<<A+B-F<<endl; }
N:
typedef pair<int,double> P; double inf=1e15,eps=1e-9; vector<P> G[2001]; int N,M,K; bool can(double T){ double d[2001]={}; bool update; rep(i,N+1){ update=0; rep(v,N+1){ for(P p:G[v]){ int u=p.fs; double c=p.sc; if(v>0&&u>0) c+=T; if(d[u]>d[v]+c+eps){ update=1; d[u]=d[v]+c; // printf("d[%d]=d[%d]+c (%f)\n",u,v,d[v]+c); } } } if(!update) break; } return !update; } int main(){ cin>>N>>M>>K; rep(i,K){ int v,x; cin>>v>>x; G[v].pb(P(0,-x)); G[0].pb(P(v,x)); } rep(i,M){ int v,u,c; cin>>v>>u>>c; G[u].pb(P(v,-c)); } double ub=inf,lb=-inf; rep(tt,100){ double T=(ub+lb)/2; if(can(T)) ub=T; else lb=T; } if(ub<-inf/2) puts("#"); else printf("%.12f",ub); }
O:
using namespace std; int N,a[100000]; typedef long long ll; ll mod=1e9+7; void add(ll &x,ll y){ x+=y; x%=mod; } const ll p2=1<<17; ll lu[100000],ru[100000],ld[100000],rd[100000]; ll LU[100000],RU[100000],LD[100000],RD[100000]; vector<int> vc[100001]; int bit[100001]; ll bit2[100001]; typedef pair<int,ll> P; P getmax(int i){ int s=0; ll sum=0; while(i>0){ if(s<bit[i]){ s=bit[i]; sum=bit2[i]; }else if(s==bit[i]){ add(sum,bit2[i]); } i=(i&(i-1)); } return P(s,sum); } void change(int i,int x,ll s){ while(i<=N){ if(bit[i]<x){ bit[i]=x; bit2[i]=s; }else if(bit[i]==x){ add(bit2[i],s); } i+=(i&-i); } } int I; ll sum=1; int LIS,LDS; void calc(ll *dp,ll *DP){ rep(i,N+1) bit[i]=0,bit2[i]=0; rep(i,N+1) vc[i].clear(); int M=0; rep(i,N){ P p=getmax(a[i]); int x=p.fs; if(x){ dp[i]=p.sc; }else dp[i]=1; change(a[i]+1,x+1,dp[i]); vc[x+1].pb(i); chmax(M,x+1); DP[i]=x; } if(I<=1){ ll al=0; for(int x:vc[M]) add(al,dp[x]); sum=sum*al%mod; } if(I==0) LIS=M; if(I==1) LDS=M; } int main(){ cin>>N; rep(i,N) cin>>a[i],a[i]--; calc(lu,LU),I++; rep(i,N) a[i]=N-1-a[i]; calc(ld,LD),I++; rep(i,N) a[i]=N-1-a[i]; reverse(a,a+N); calc(rd,RD),I++; rep(i,N) a[i]=N-1-a[i]; calc(ru,RU); ll x=0; rep(i,N){ if(LU[i]+RU[N-1-i]!=LIS-1) continue; if(LD[i]+RD[N-1-i]!=LDS-1) continue; ll tmp=lu[i]*ru[N-1-i]%mod*ld[i]%mod*rd[N-1-i]%mod; add(x,tmp); } cout<<LIS+LDS-(x==sum)<<endl; }