CF #259 - sigma425のブログ

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;
}

#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;
}

#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;
}