CF #259
http://codeforces.com/contest/453
A:やるだけ STLのpow使うという発想が無かった(雑魚)
B:bitDP.dp[i][j]=i番目までで2~53の16個の素数を素因数に持つものを既に使った時のそこまでのsumの最小
計算量的に辛いため先にseni[i][j]=bit状態iから数字jを選んだ時に遷移するbit状態(選べないなら-1)を持っといた
あとaをsortしてはじめn-16個くらいは1にしてもいいことを使えるんだけど、使わなくてもTLEしなかったようだ
C:やるだけ
01がうまく合うように行き来するdfsを書くだけ。disjointな1たちがあればやばい。
D,E:読んでない
反省:
Bのバグ取りに時間をかけすぎ(1時間位かけている).printf debugは有効だが、たまにはコードをベタ読みすることも必要.あと"全ての問題文を読む,数分考察をする"を先にやったほうが良さそう,standingは当てにならない.
コード
A
#include <iostream> #include <cstdio> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define rep1(i,n) for(int i=1;i<=n;++i) #define all(c) (c).begin(),(c).end() int main(){ int m,n; scanf("%d%d",&m,&n); double ans=m; rep1(i,m-1){ double fr=(double)i/m,now=1; for(int j=0;(n>>j)!=0;j++){ if(n>>j & 1) now*=fr; fr=fr*fr; } ans-=now; } printf("%.6lf\n",ans); return 0; }
B
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define rep1(i,n) for(int i=1;i<=n;++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second typedef pair<int,int> P; int p[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; int dp[101][1<<16],sen[1<<16][54],mm[101][1<<16],memo[101][1<<16]; int main(){ int n; P a[100]; scanf("%d",&n); rep(i,n){ scanf("%d",&a[i].fs); a[i].sc=i; } sort(a,a+n); rep(i,n-16) a[i].fs=1; rep(i,1<<16){ int d[16]={}; rep(j,16) d[j]=(i>>j)&1; rep1(j,53){ bool ok=1; rep(k,16){ if(j%p[k]==0){ if(d[k]==1){ ok=0; break; }else{ sen[i][j]+=(1<<k); } } } if(!ok) sen[i][j]=-1; else sen[i][j]+=i; } } /* while(true){ int x,y; cin >> x >> y; if(x==-1) break; cout << sen[x][y] << endl; }*/ int inf=1e8; rep(i,101) rep(j,1<<16) dp[i][j]=inf; int now=max(0,n-16); dp[now][0]=0; for(int i=now;i<n;i++){ rep(j,1<<16){ if(i==now && j>0) break; int d[16]={}; rep(k,16) d[k]=(j>>k)&1; rep1(k,53){ if(sen[j][k]==-1) continue; if(dp[i+1][sen[j][k]]>dp[i][j]+abs(a[i].fs-k) ){ memo[i+1][sen[j][k]]=j; mm[i+1][sen[j][k]]=k; dp[i+1][sen[j][k]]=dp[i][j]+abs(a[i].fs-k); } } } } int ans=inf; rep(i,1<<16) ans=min(ans,dp[n][i]); rep(i,1<<16){ if(dp[n][i]==ans){ int yy=i; for(int j=n;j>now;j--){ a[j-1].fs=mm[j][yy]; yy=memo[j][yy]; } break; } } int ansa[100]; rep(i,n) ansa[a[i].sc]=a[i].fs; rep(i,n) printf("%d ",ansa[i]); return 0; }
C
#include <iostream> #include <cstdio> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define rep1(i,n) for(int i=1;i<=n;++i) #define all(c) (c).begin(),(c).end() #define pb push_back vector<int> G[100010]; bool now[100010]; int ans[400010]; bool visited[100010]; int cnt=0; void ins(int v){ ans[cnt]=v; cnt++; now[v]=!now[v]; } void dfs(int v,int p){ visited[v]=true; ins(v); rep(i,G[v].size()){ if(visited[G[v][i]]) continue; dfs(G[v][i],v); ins(v); } if(now[v]){ if(p==-1){ if(G[v].size()==0) return; ins(G[v][0]); ins(v); ins(G[v][0]); }else{ ins(p); ins(v); } } } int main(){ int n,m; scanf("%d%d",&n,&m); rep(i,m){ int u,v; scanf("%d%d",&u,&v); u--,v--; G[u].pb(v); G[v].pb(u); } int s=-1; rep(i,n){ scanf("%d",&now[i]); if(now[i]) s=i; } if(s==-1){ rep(i,n){ if(now[i]==1){ printf("-1\n"); return 0; } } printf("0\n"); return 0; } dfs(s,-1); rep(i,n){ if(now[i]){ printf("-1\n"); return 0; } } printf("%d\n",cnt); rep(i,cnt) printf("%d ",ans[i]+1); return 0; }