tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

Codeforces Round #360 (Div. 1)

初全完。全完ゲーはHack上乗せ勝負なのでVirtual Participation勢には不利。

A B C D E Place
00:07 00:17 (+1) 00:27 00:50 01:39 16th

A:
よくある二色塗りのUFを書いたら他の人に取り残されたんだけど、簡単な解法があるのかな。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int UF[210000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
vector<int>A;
vector<int>B;
int v[210000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a*2;i++)UF[i]=-1;
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		UNION(p,q+a);
		UNION(q,p+a);
	}
	for(int i=0;i<a;i++){
		if(FIND(i)==FIND(i+a)){
			printf("-1\n");return 0;
		}
	}
	for(int i=0;i<a;i++){
		if(v[FIND(i)]==0&&v[FIND(i+a)]==0){
			v[FIND(i)]=1;
			v[FIND(i+a)]=-1;
			A.push_back(i);
		}else{
			if(v[FIND(i)]==1||v[FIND(i+a)]==-1){
				v[FIND(i)]=1;
				v[FIND(i+a)]=-1;
				A.push_back(i);
			}else{
				v[FIND(i)]=-1;
				v[FIND(i+a)]=1;
				B.push_back(i);
			}
		}
	}
	printf("%d\n",(int)A.size());
	for(int i=0;i<A.size();i++){
		if(i)printf(" ");printf("%d",A[i]+1);
	}
	printf("\n");
	printf("%d\n",(int)B.size());
	for(int i=0;i<B.size();i++){
		if(i)printf(" ");printf("%d",B[i]+1);
	}
	printf("\n");
}

B:
素因数が足りてるか。素数でないものを見てしまい1WA。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int c[1100000];
long long gcd(long long a,long long b){
	while(a){
		b%=a;swap(a,b);
	}
	return b;
}
long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}
vector<pair<int,int> > v;
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	for(int i=2;i<=b;i++){
		if(b%i)continue;
		int e=0;
		while(b%i==0){
			e++;
			b/=i;
		}
		v.push_back(make_pair(i,e));
	}
	bool ok=true;
	for(int i=0;i<v.size();i++){
		bool OK=false;
		for(int j=0;j<a;j++){
			int tmp=c[j];
			int cur=0;
			while(tmp%v[i].first==0){
				tmp/=v[i].first;
				cur++;
			}
			if(cur>=v[i].second){
				OK=true;break;
			}
		}
		if(!OK){ok=false;break;}
	}
	if(ok)printf("Yes\n");
	else printf("No\n");
}

C:
合計をKにする用としなくてもいい用の2つの要素があればよい。これも上位勢は速すぎ

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int dp[510][510];
int c[510];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	vector<int>ans;
	dp[0][0]=1;
	for(int i=0;i<a;i++){
		for(int j=b;j>=0;j--){
			for(int k=b;k>=0;k--){
				if(dp[j][k]){
					if(j+c[i]<=b){
						dp[j+c[i]][k+c[i]]=1;
						dp[j+c[i]][k]=1;
					}
				}
			}
		}
	}
	for(int i=0;i<=b;i++)if(dp[b][i])ans.push_back(i);
	printf("%d\n",(int)ans.size());
	for(int i=0;i<ans.size();i++){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}
	printf("\n");
}

D:
強引にunion findの自明解を送ったら5974ms/6000msで通ってしまった...。非再帰Union-Findにすればもっと速くなるのではないかと考えると、Time Limitが雑すぎる。
どうせ想定解も変なsqrtテクか永続あたりを使ってオーダー落とすUnion-Findなんでしょ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int dp[510][510];
int c[510];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	vector<int>ans;
	dp[0][0]=1;
	for(int i=0;i<a;i++){
		for(int j=b;j>=0;j--){
			for(int k=b;k>=0;k--){
				if(dp[j][k]){
					if(j+c[i]<=b){
						dp[j+c[i]][k+c[i]]=1;
						dp[j+c[i]][k]=1;
					}
				}
			}
		}
	}
	for(int i=0;i<=b;i++)if(dp[b][i])ans.push_back(i);
	printf("%d\n",(int)ans.size());
	for(int i=0;i<ans.size();i++){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}
	printf("\n");
}

E:
それぞれの頂点からスタートして自分に戻るループの最小長を求めて置いて、短いものから逆にたどっていくgreedy。強連結成分分解のライブラリは作りましょう......

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;

vector<int>g[5100];
vector<int>rev[5100];
int v[5100];
int num[5100];
int conv[5100];
int scc[5100];
int fi[5100];
int ss[5100];
int cur;
void dfs(int a){
	for(int i=0;i<g[a].size();i++){
		if(v[g[a][i]])continue;
		v[g[a][i]]=1;
		dfs(g[a][i]);
	}
	conv[a]=cur;
	num[cur++]=a;
}
void dfs2(int a){
	scc[a]=cur;
	ss[cur]++;
	for(int i=0;i<rev[a].size();i++){
		if(v[rev[a][i]])continue;
		v[rev[a][i]]=1;
		dfs2(rev[a][i]);
	}
}
int len[5100];
int dp[2][5100];
int st;
void dfs3(int a,int b){
	v[a]=1;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==st){
			if(len[st]==-1)len[st]=b+1;
			else if(len[st]>b+1)len[st]=b+1;
		}
		if(v[g[a][i]])continue;
		dfs3(g[a][i],b+1);
	}
}
vector<int>G[5100];
int g2[5100][5100];
int used[5100];
pair<pair<int,int>,int> q[5100];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
		rev[q].push_back(p);
	}
	for(int i=0;i<a;i++){
		if(v[i])continue;
		v[i]=1;
		dfs(i);
	}
	cur=0;
	for(int i=0;i<a;i++)v[i]=0;
	for(int i=a-1;i>=0;i--){
		if(v[num[i]])continue;
		v[num[i]]=1;
		fi[cur]=num[i];
		dfs2(num[i]);
		cur++;
	}
	for(int i=0;i<a;i++){
		len[i]=-1;
		st=i;
		for(int j=0;j<a;j++)v[j]=0;

		dfs3(i,0);
	//printf("%d: %d\n",i,len[i]);
		q[i]=make_pair(make_pair(len[i],conv[i]),i);
	}
	std::sort(q,q+a);
	for(int i=0;i<a;i++){
		for(int j=0;j<rev[i].size();j++){
			if(scc[i]!=scc[rev[i][j]]){
				g2[scc[i]][scc[rev[i][j]]]=1;
			}
		}
	}
	for(int i=0;i<cur;i++){
		for(int j=0;j<cur;j++){
			if(g2[i][j])G[i].push_back(j);
		}
	}
	int ret=0;
	for(int i=0;i<a;i++){
		int at=q[i].second;
		int cost=q[i].first.first;
		if(used[scc[at]])continue;
		if(cost!=-1){
			ret+=998*cost+1;
		}
		used[scc[at]]=1;
		queue<int>Q;
		Q.push(scc[at]);
		while(Q.size()){
			int now=Q.front();Q.pop();
			ret+=ss[now];
			for(int j=0;j<G[now].size();j++){
				if(used[G[now][j]])continue;
				used[G[now][j]]=1;
				Q.push(G[now][j]);
			}
		}
	}
	printf("%d\n",ret);
}

Codeforces Round #362 (Div. 1)

解けたのに虚しくなる意味不明なセット。面白くはない。

A B C D E F Place
00:10 (+1) 00:17 00:38 01:14 - - 37th

A:
辺を全部mapで更新する。何も考えずにやったらオーバーフローした。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
map<long long,long long> m;
long long u[110];
long long v[110];
int main(){
	int a;scanf("%d",&a);
	while(a--){
		int t;scanf("%d",&t);
		if(t==1){
			long long p,q,r;scanf("%I64d%I64d%I64d",&p,&q,&r);
			int sa=0;
			int sb=0;
			while(p){
				u[sa++]=p;
				p/=2;
			}
			while(q){
				v[sb++]=q;
				q/=2;
			}
			int sl=0;
			for(int i=0;i<min(sa,sb);i++){
				if(u[sa-1-i]==v[sb-1-i])sl++;
				else break;
			}
			for(int i=0;i<sa-sl;i++){
				m[u[i]]+=r;
			}
			for(int i=0;i<sb-sl;i++){
				m[v[i]]+=r;
			}
		}else{
			long long p,q;scanf("%I64d%I64d",&p,&q);
			int sa=0;
			int sb=0;
			while(p){
				u[sa++]=p;
				p/=2;
			}
			while(q){
				v[sb++]=q;
				q/=2;
			}
			int sl=0;
			long long ret=0;
			for(int i=0;i<min(sa,sb);i++){
				if(u[sa-1-i]==v[sb-1-i])sl++;
				else break;
			}
			for(int i=0;i<sa-sl;i++){
				if(m.count(u[i]))ret+=m[u[i]];
			}
			for(int i=0;i<sb-sl;i++){
				if(m.count(v[i]))ret+=m[v[i]];
			}
			printf("%I64d\n",ret);
		}
	}
}

B:
いい加減こういうの見飽きた。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<int>g[110000];
int sz[110000];
double dp[110000];
void dfs(int a){
	sz[a]=1;
	for(int i=0;i<g[a].size();i++){
		dfs(g[a][i]);
		sz[a]+=sz[g[a][i]];
	}
}
void calc(int a,double b){
	dp[a]=b;
	for(int i=0;i<g[a].size();i++){
		calc(g[a][i],b+1+(sz[a]-1-sz[g[a][i]])*0.5);
	}
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		int p;scanf("%d",&p);p--;
		g[p].push_back(i+1);
	}
	dfs(0);
	calc(0,0);
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%.12f",dp[i]+1);
	}
	printf("\n");
}

C:
手で数学をするだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
long long b[110000];
long long d3=(mod+1)/3;
long long d2=(mod+1)/2;
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		b/=2;
		a=a*a%mod;
	}
	return ret;
}
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%I64d",b+i);
	bool gu=false;
	for(int i=0;i<a;i++)if(b[i]%2==0)gu=true;
	long long tmp=pw(2,b[0]);
	for(int i=1;i<a;i++)tmp=pw(tmp,b[i]);
	tmp=tmp*d2%mod;
	long long bs;
	if(gu)bs=(tmp+1)%mod;
	else bs=(tmp+mod-1)%mod;
	bs=bs*d3%mod;
	printf("%d/%d\n",(int)bs,(int)tmp);
}

D:
Trie上でCow Relaysするだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int c[210];
char in[210][210];
int len[210];
struct Trie{
	int chi[26];
	int sc;
	Trie(){for(int i=0;i<26;i++)chi[i]=-1;sc=0;}
};
Trie pool[210];
char st[210];
int n;
int to[210][26];
void dfs(int a,int b){
	for(int i=0;i<26;i++){
		if(pool[a].chi[i]==-1)continue;
		st[b]='a'+i;
		dfs(pool[a].chi[i],b+1);
	}
	for(int i=0;i<n;i++){
		if(len[i]>b)continue;
		bool ok=true;
		for(int j=0;j<len[i];j++){
			if(in[i][len[i]-1-j]!=st[b-1-j]){ok=false;break;}
		}
		if(ok)pool[a].sc+=c[i];
	}
	for(int i=0;i<26;i++){
		st[b]=i+'a';
		bool ok=false;
		for(int j=0;j<=b;j++){
			int now=0;
			for(int k=j;k<=b;k++){
				if(pool[now].chi[st[k]-'a']==-1){now=-1;break;}
				now=pool[now].chi[st[k]-'a'];
			}
			if(now!=-1){
				ok=true;to[a][i]=now;break;
			}
		}
		if(!ok)to[a][i]=0;
	}
}
long long dp[210][210][210];
long long val[210][410];
long long las[210][210];
int main(){
	int a;
	long long b;
	scanf("%d%I64d",&a,&b);
	n=a;
	for(int i=0;i<a;i++)scanf("%d",c+i);
	for(int i=0;i<a;i++){
		scanf("%s",in[i]);
		len[i]=strlen(in[i]);
	}
	int sz=1;
	for(int i=0;i<a;i++){
		int at=0;
		for(int j=0;in[i][j];j++){
			if(pool[at].chi[in[i][j]-'a']==-1){
				pool[at].chi[in[i][j]-'a']=sz++;
				at=sz-1;
			}else at=pool[at].chi[in[i][j]-'a'];
		}
	}
	dfs(0,0);
	for(int i=0;i<sz;i++){
		for(int j=0;j<210;j++)for(int k=0;k<210;k++)dp[i][j][k]=-mod;
		dp[i][0][i]=0;
		for(int j=0;j<sz;j++){
			for(int k=0;k<sz;k++){
				for(int l=0;l<26;l++){
					dp[i][j+1][to[k][l]]=max(dp[i][j+1][to[k][l]],dp[i][j][k]+pool[to[k][l]].sc);
				}
			}
		}
	}
	long long ret=0;
	for(int i=0;i<sz;i++){
		for(int j=0;j<410;j++){
			val[i][j]=-inf;
			if(b-j<0)continue;
			for(int k=1;k<=sz;k++){
				if(dp[i][k][i]<0)continue;
				val[i][j]=max(val[i][j],(b-j)/k*dp[i][k][i]);
			}
		}
	}
	if(b<sz){
		for(int i=0;i<sz;i++)ret=max(ret,dp[0][b][i]);
		printf("%I64d\n",ret);
		return 0;
	}
	for(int i=0;i<sz;i++){
		for(int j=0;j<sz;j++){
			las[i][j]=-inf;
			for(int k=0;k<sz;k++)las[i][j]=max(las[i][j],dp[i][j][k]);
		}
	}
	for(int i=0;i<sz;i++){
		for(int j=0;j<sz;j++)for(int k=0;k<sz;k++){
			ret=max(ret,dp[0][j][i]+val[i][j+k]+las[i][k]);
		}
	}
	printf("%I64d\n",ret);
}

F:
二分探索で、中でそれぞれの辺から中に伸ばすとどの範囲なら対応可能かというのを求めておけば、ある辺からスタートするとどこまでいけるかというのがわかり、判断可能でO(N^2 log X)なんだろうけど、実装量も多すぎるし、JAGの幾何と同様全く面白くない。

Codeforces Round #363 (Div. 1)

一体何をやっているんですかね......

A B C D E F Place
00:031 00:21 00:39 (+3) 02:07 (+7) - - 26th

A:
Div1...?

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[110];
int dp[110][3];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	for(int i=0;i<110;i++)for(int j=0;j<3;j++)dp[i][j]=mod;
	dp[0][0]=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<3;j++){
			if(b[i]/2&&j!=1){
				dp[i+1][1]=min(dp[i+1][1],dp[i][j]);
			}
			if(b[i]%2&&j!=2){
				dp[i+1][2]=min(dp[i+1][2],dp[i][j]);
			}
			dp[i+1][0]=min(dp[i+1][0],dp[i][j]+1);
		}
	}
	int ret=mod;
	for(int i=0;i<3;i++)ret=min(ret,dp[a][i]);
		printf("%d\n",ret);
}

B:
大きさ1のサイクルが1つあるのが理想。大きさ1のサイクルが複数あるとき、大きさ2以上のサイクルしかないとき等を考えればよい。
visを1と2で埋めていくサイクル探しはトポロジカルソートでもおなじみ(なのか?)。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int p[210000];
int v[210000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);p[i]--;
	}
	int ret=0;
	int par=-1;
	int sec=-1;
	for(int i=0;i<a;i++){
		if(v[i])continue;
		int at=i;
		vector<int>vis;
		v[at]=2;
		vis.push_back(at);
		while(1){
			int to=p[at];
			if(v[to]==1)break;
			if(v[to]==2){
				if(to!=at){
					ret++;
					p[at]=-1;
					sec=at;
				}else{
					if(!~par){
						par=at;
					}else{
						ret++;
						p[at]=par;
					}
				}
				break;
			}
			v[to]=2;
			at=to;
			vis.push_back(to);
		}
		for(int j=0;j<vis.size();j++){
			v[vis[j]]=1;
		}
	}
	for(int i=0;i<a;i++){
		if(p[i]==-1){
			if(~par)p[i]=par;
			else p[i]=sec;
		}
	}
	printf("%d\n",ret);
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%d",p[i]+1);
	}
	printf("\n");
}

C:
普通にbitDPやるだけなのに、なぜかp=0のケースが存在していてHackし放題になっている。
設定として不自然だと思うんだけどなあ...

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
double dp[1<<20];
double p[22];
double q[22];
double ret[22];
int ind[22];
double EPS=1e-9;
int main(){
	int n,b;scanf("%d%d",&n,&b);
	for(int i=0;i<n;i++){
		scanf("%lf",q+i);
	}
	int a=0;
	for(int i=0;i<n;i++){
		if(q[i]>EPS){
			p[a++]=q[i];
			ind[a-1]=i;
		}
	}
	b=min(b,a);
	dp[0]=1;
	for(int i=0;i<(1<<a)-1;i++){
		double tot=1;
		for(int j=0;j<a;j++){
			if(i&(1<<j))tot-=p[j];
		}
		if(tot<EPS)continue;
		for(int j=0;j<a;j++){
			if(i&(1<<j))continue;
			dp[i+(1<<j)]+=dp[i]*p[j]/tot;
		}
	}
	for(int i=0;i<(1<<a);i++){
		if(__builtin_popcount(i)!=b)continue;
		for(int j=0;j<a;j++)if(i&(1<<j))ret[ind[j]]+=dp[i];
	}
	for(int j=0;j<n;j++){
		if(j)printf(" ");
		printf("%.12f",ret[j]);
	}
	printf("\n");
}

D:
各獲物から各ワープ地点まで辺を張ったときに、辺上に来るものを全部持っておく(ただし、k個以上が邪魔しているときは、絶対到達不可能なので無視する)。
ゴールから(到達したい頂点集合,残り使えるワープ先の集合)を頂点にdfsしていくと、意外とこれは速くて間に合う。(行きたい頂点の集合は一瞬で増えるか一瞬で消えるのではなかろうか)

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long double EPS = 1e-20;
const long double INF = 1e+20;
const long double PI = acos(-1);
int sig(long double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
inline long double ABS(long double a){return max(a,-a);}
struct Pt {
	long double x, y;
	Pt() {}
	Pt(long double x, long double y) : x(x), y(y) {}
	Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
	Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
	Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
	Pt operator-() const { return Pt(-x, -y); }
	Pt operator*(const long double &k) const { return Pt(x * k, y * k); }
	Pt operator/(const long double &k) const { return Pt(x / k, y / k); }
	long double ABS() const { return sqrt(x * x + y * y); }
	long double abs2() const { return x * x + y * y; }
	long double arg() const { return atan2(y, x); }
	long double dot(const Pt &a) const { return x * a.x + y * a.y; }
	long double det(const Pt &a) const { return x * a.y - y * a.x; }
};
long double tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }

int iSP(Pt a, Pt b, Pt c) {
	int s = sig((b - a).det(c - a));
	if (s) return s;
	if (sig((b - a).dot(c - a)) < 0) return -2; // c-a-b
	if (sig((a - b).dot(c - b)) < 0) return +2; // a-b-c
	return 0;
}
int iLL(Pt a, Pt b, Pt c, Pt d) {
	if (sig((b - a).det(d - c))) return 1; // intersect
	if (sig((b - a).det(c - a))) return 0; // parallel
	return -1; // correspond
}
bool iLS(Pt a, Pt b, Pt c, Pt d) {
	return (sig(tri(a, b, c)) * sig(tri(a, b, d)) <= 0);
}
bool iSS(Pt a, Pt b, Pt c, Pt d) {
	return (iSP(a, b, c) * iSP(a, b, d) <= 0 && iSP(c, d, a) * iSP(c, d, b) <= 0);
}
bool iSSstrict(Pt a, Pt b, Pt c, Pt d) {
	return (sig(tri(a, b, c)) * sig(tri(a, b, d)) < 0 && sig(tri(c, d, a)) * sig(tri(c, d, b)) < 0);
}
Pt p[10];
Pt q[1100];
int num[1100][7][7];
pair<long double,int> tmp[1100];
int m;
int solve(set<int>a,int b){
	if(a.size()>__builtin_popcount(b))return 0;
	if(a.size()==0)return 1;
//	for(set<int>::iterator it=a.begin();it!=a.end();it++)printf("%d ",*it);
//	printf(": %d\n",b);
	for(set<int>::iterator it=a.begin();it!=a.end();it++){

		int at=*it;
		for(int i=0;i<m;i++){
			if(b&(1<<i)){
				if(num[at][i][0]==-2)continue;
				int tb=b-(1<<i);
				set<int>to=a;
				to.erase(at);
				for(int j=0;j<m;j++){
					if(num[at][i][j]==-1){
						break;
					}
					to.insert(num[at][i][j]);
				}
				if(solve(to,tb))return 1;
			}
		}
	}
	return 0;
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	m=a;
	for(int i=0;i<a;i++){
		int X,Y;scanf("%d%d",&X,&Y);
		p[i]=Pt(X,Y);
	}
	for(int i=0;i<b;i++){
		int X,Y;scanf("%d%d",&X,&Y);
		q[i]=Pt(X,Y);
	}

	for(int i=0;i<b;i++)for(int j=0;j<a;j++)for(int k=0;k<a;k++)num[i][j][k]=-1;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			int sz=0;
			for(int k=0;k<b;k++){
				if(j==k)continue;
				if(iSP(p[i],q[k],q[j])==2){
		//			printf("%d %d %d\n",i,j,k);
				//	if(num[j][i][0]==-1||iSP(q[j],q[k],q[num[j][i][0]])==2){
//
//						num[j][i][0]=k;
//					}
					tmp[sz++]=make_pair((q[j]-q[k]).abs2(),k);
				}
			}
			if(sz>=a){
				num[j][i][0]=-2;
			}else{
				for(int k=0;k<sz;k++){
					num[j][i][k]=tmp[k].second;
				}
			}
	//		printf("%d %d: %d\n",j,i,num[j][i][0]);
		}
	}
	int ret=0;
	for(int i=0;i<b;i++){
		set<int>st;
		st.insert(i);
		if(solve(st,(1<<a)-1))ret++;
	//	printf("\n");
	}
	printf("%d\n",ret);
}

E:
OpenCupでも結構あるけど、「見た目は面倒なだけの実装問題だが、実は細かいところがやけに難しい問題」なのではなかろうか。

F:
あとでやろう。

Codeforces Round #364 (Div. 1)

遅いのとA,B逆なことを除けばうまくいった?

A B C D E Place
00:26 00:33 01:28 - - 20th

A:
全然わかりませんでした(オイ
バス乗車時間を二分探索。式もなんだか難しい。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int main(){
	int a,b,c,d,e;
	scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
	double left=0;
	double right=(double)b/d;
	int r=(a+e-1)/e;
	for(int i=0;i<100;i++){
		double M=(left+right)/2;
		double at=0;
		double t=0;
		double x=0;
		for(int j=0;j<r;j++){
			t+=M;
			at+=M*d;
			if(j==r-1)break;
			x=t*c;
			double t2=(at-x)/(c+d);
			x+=t2*c;
			at=x;
			t+=t2;
		}
	//	printf("%f: %f %f\n",M,t,at);
		if(at<b){
			left=M;
		}else right=M;
	}
	//printf("%f\n",left);
	printf("%.12f\n",left+((double)b-left*d)/c);
}

B:
辺ごとに両端の少ない方だけ人が移動する。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int v[210000];
vector<int>g[221000];
long long ret=0;
int sz[221000];
int M;
void dfs(int a,int b){
	for(int i=0;i<g[a].size();i++){
		if(b==g[a][i])continue;
		dfs(g[a][i],a);
		sz[a]+=sz[g[a][i]];
		ret+=min(sz[g[a][i]],M-sz[g[a][i]]);
	}
	if(v[a])sz[a]++;

}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	M=b*2;
	for(int i=0;i<b*2;i++){
		int p;scanf("%d",&p);p--;v[p]++;
	}
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	dfs(0,-1);
	printf("%I64d\n",ret);
}

C:
まずDinic (計算量的にも問題なし)。流量0のときと3以上のときは自明。
流量が1,2いずれのときも1つの辺はフローで流れた辺を使う。2のときは残った辺もフローで流れた辺。
フローで使った辺を1つ選び、残りでs->tの移動中必ず通る辺(dfs情報のアレでチェック可能)を全部試せばよい。1のときはフローで使った辺を消したあとBFSしてs->tいけるかどうかも判断する。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const int D_MAX_V=1002;
const int D_v_size=1002;
struct D_wolf{
	int t,c,r;
	int u,w;
	D_wolf(){t=c=r=u=w=0;}
	D_wolf(int t1,int c1,int r1,int u1,int w1){
		t=t1;c=c1;r=r1;u=u1;w=w1;
	}
};
vector<D_wolf>D_G[D_MAX_V];
int D_level[D_MAX_V];
int D_iter[D_MAX_V];

void add_edge(int from,int to,int cap,int id){
	D_G[from].push_back(D_wolf(to,cap,D_G[to].size(),1,id));
	D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1,0,id));
}
void D_bfs(int s){
	for(int i=0;i<D_v_size;i++)D_level[i]=-1;
	queue<int> Q;
	D_level[s]=0;
	Q.push(s);
	while(Q.size()){
		int v=Q.front();
		Q.pop();
		for(int i=0;i<D_G[v].size();i++){
			if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){
				D_level[D_G[v][i].t]=D_level[v]+1;
				Q.push(D_G[v][i].t);
			}
		}
	}
}
int D_dfs(int v,int t,int f){
	if(v==t)return f;
	for(;D_iter[v]<D_G[v].size();D_iter[v]++){
		int i=D_iter[v];
		if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){
			int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c));
			if(d>0){
				D_G[v][i].c-=d;
				D_G[D_G[v][i].t][D_G[v][i].r].c+=d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int flow=0;
	for(;;){
		D_bfs(s);
		if(D_level[t]<0)return flow;
		for(int i=0;i<D_v_size;i++)D_iter[i]=0;
		int f;
		while((f=D_dfs(s,t,99999999))>0){flow+=f;}
	}
	return 0;
}
const int MAXN=1100;
const int MAXM=61000;
int zeit, dis[MAXN], fin[MAXN], low[MAXN], par[MAXN], dep[MAXN];
int kodat[MAXN], koptr[MAXN + 1];
int zu[MAXM];
int ptr[MAXN];
int nxt[MAXM];
int n;
void dfsInfo(int u, int oy, int d) {
	dis[u] = low[u] = zeit++; par[u] = oy; dep[u] = d;
	int i, v;
	for (i = ptr[u]; ~i; i = nxt[i]) if ((v = zu[i]) != oy) {
		if (!~dis[v]) {
			dfsInfo(v, u, d + 1);
			low[u] = min(low[u], low[v]);
		} else {
			low[u] = min(low[u], dis[v]);
		}
	}
	fin[u] = zeit++;
}
void dfsInfos() {
	memset(dis, ~0, n * 4); zeit = 0;
	for (int u = 0; u < n; ++u) if (!~dis[u]) dfsInfo(u, -1, 0);
	for (int u = 0; u < n; ++u) {
		int &j = koptr[u + 1] = koptr[u];
		for (int i = ptr[u]; ~i; i = nxt[i]) if (u == par[zu[i]]) kodat[j++] = zu[i];
	}
}
bool produce(int u, int v) {
	return (dis[u] <= dis[v] && fin[u] >= fin[v]);
}
int related(int u, int v) {
	int s = koptr[u], e = koptr[u + 1], h;
	for (; s + 1 < e; ) {
		h = (s + e) >> 1;
		(dis[kodat[h]] <= dis[v]) ? s = h : e = h;
	}
	return kodat[s];
}
bool isBridge(int u, int v) {
	if (dis[u] > dis[v]) swap(u, v);
	return (u == par[v] && dis[v] <= low[v]);
}
bool isFatalEdge(int u, int v, int a, int b) {
	if (dis[u] > dis[v]) swap(u, v);
	return (u == par[v] && dis[v] <= low[v] && produce(v, a) != produce(v, b));
}
bool isFatalPoint(int u, int a, int b) {
	bool ua = produce(u, a), ub = produce(u, b);
	if (!ua && !ub) {
		return 0;
	} else if (ua && ub) {
		int ra = related(u, a), rb = related(u, b);
		return (ra != rb && (dis[u] <= low[ra] || dis[u] <= low[rb]));
	} else {
		if (ub) swap(a, b);
		return (dis[u] <= low[related(u, a)]);
	}
}
int vis[1100];
int x[31000];
int y[31000];
int z[31000];
int f[1100][1100];
vector<pair<int,int> > G[1100];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int s,t;scanf("%d%d",&s,&t);
	s--;t--;

	for(int i=0;i<b;i++){
		int p,q,r;scanf("%d%d%d",&p,&q,&r);p--;q--;
		f[p][q]++;
		f[q][p]++;
		x[i]=p;y[i]=q;z[i]=r;
		if(p==q)continue;
		add_edge(p,q,1,i);
		add_edge(q,p,1,i);
	}
	int ans=max_flow(s,t);
	if(ans>2){
		printf("-1\n");return 0;
	}
	if(ans==0){
		printf("0\n0\n");return 0;
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<D_G[i].size();j++){
			if(D_G[i][j].u&&D_G[i][j].c==0){
				G[i].push_back(make_pair(D_G[i][j].t,D_G[i][j].w));
			}
		}
	}
	int ret=mod*2;
	int L=-1;
	int R=-1;
	for(int i=0;i<a;i++)for(int j=0;j<G[i].size();j++){
		for(int k=0;k<b;k++){
			zu[k]=nxt[k]=-1;
		}
		for(int k=0;k<=a;k++){
			dis[k]=fin[k]=low[k]=par[k]=dep[k]=kodat[k]=koptr[k]=0;
			ptr[k]=-1;
		}
		int cur=z[G[i][j].second];
		zeit=0;
		int sz=0;
		for(int k=0;k<b;k++){
			if(x[k]==y[k])continue;
			if(G[i][j].second==k)continue;
			zu[sz]=y[k];
			nxt[sz]=ptr[x[k]];
			ptr[x[k]]=sz++;
			zu[sz]=x[k];
			nxt[sz]=ptr[y[k]];
			ptr[y[k]]=sz++;
		}
		n=a;
		if(ans==1&&ret>cur){
			for(int k=0;k<a;k++)vis[k]=0;
			queue<int>Q;
			Q.push(s);
			vis[s]=1;
			while(Q.size()){
				int at=Q.front();Q.pop();
				for(int k=ptr[at];~k;k=nxt[k]){
					if(!vis[zu[k]]){
						vis[zu[k]]=1;
						Q.push(zu[k]);
					}
				}
			}
			if(vis[t]==0){
				ret=cur;
				L=G[i][j].second;
				R=-1;
			}
		}
		dfsInfos();
		for(int k=0;k<b;k++){
			if(x[k]==y[k])continue;
			if(G[i][j].second==k)continue;
			if(ret>cur+z[k]&&isFatalEdge(x[k],y[k],s,t)&&(f[x[k]][y[k]]==1||(f[x[k]][y[k]]==2&&((i==x[k]&&G[i][j].first==y[k])||(i==y[k]&&G[i][j].first==x[k]))))){
				ret=cur+z[k];
				L=G[i][j].second;
				R=k;
			}
		}
	}
	if(~R){
		printf("%d\n2\n%d %d\n",ret,L+1,R+1);
	}else printf("%d\n1\n%d\n",ret,L+1);
}

D:
人間が解ける問題には見えない。Mo+ハフマン木の回転、とかではないなら結構面白いのかも。

Codeforces Round #366 (Div. 1)

コンテストのバランスを全く考えていない難問セットなのですが、一つ一つはICPCの大変な問題(しかもサンプルも弱い)のような存在で、ただ実装が辛いだけでした。
ちなみにMARVELはヴェノム派です。

A B C D E Place
00:16 (+1) 00:53 (+3) - - - 33rd

A:
なんて事はないやるだけ問題なのですが、iとnumを1箇所間違えました。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int p[310000];
int at[310000];
vector<int>v[310000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	int cnt=0;
	int ind=0;
	int num=0;
	for(int i=0;i<b;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==1){
			cnt++;
			v[y].push_back(num++);
		}else if(x==2){
			while(at[y]<v[y].size()){
				if(!p[v[y][at[y]]])cnt--;
				p[v[y][at[y]]]=1;
				at[y]++;
			}
		}else{
			while(ind<y){
				if(!p[ind])cnt--;
				p[ind]=1;
				ind++;
			}
		}
		printf("%d\n",cnt);
	}
}

B:
類題はもう何個もあると思います。生きている辺が1本のときの場合分けとかが厄介ですが、サンプルには入っていません。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int x[5100];
long long dp[2][10100];
int A[5100];
int B[5100];
int C[5100];
int D[5100];

int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	b--;c--;
	for(int i=0;i<a;i++)scanf("%d",x+i);
	x[a]=mod;
	for(int i=0;i<a;i++)scanf("%d",A+i);
	for(int i=0;i<a;i++)scanf("%d",B+i);
	for(int i=0;i<a;i++)scanf("%d",C+i);
	for(int i=0;i<a;i++)scanf("%d",D+i);
	for(int i=0;i<2;i++)for(int j=0;j<10100;j++)dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=0;i<a;i++){
		int t=i%2;
		for(int j=0;j<10100;j++)dp[!t][j]=inf;
		for(int j=0;j<a*2;j++){
			if(dp[t][j]==inf)continue;
			if(i==b){
				if(j>1||(j==1&&i==a-1))dp[!t][j-1]=min(dp[!t][j-1],dp[t][j]+(long long)(j-1)*(x[i+1]-x[i])+C[i]);
				dp[!t][j+1]=min(dp[!t][j+1],dp[t][j]+(long long)(j+1)*(x[i+1]-x[i])+D[i]);
			}else if(i==c){
				if(j>1||(j==1&&i==a-1))dp[!t][j-1]=min(dp[!t][j-1],dp[t][j]+(long long)(j-1)*(x[i+1]-x[i])+A[i]);
				dp[!t][j+1]=min(dp[!t][j+1],dp[t][j]+(long long)(j+1)*(x[i+1]-x[i])+B[i]);
			}else{
				dp[!t][j+2]=min(dp[!t][j+2],dp[t][j]+(long long)(j+2)*(x[i+1]-x[i])+B[i]+D[i]);
				if(j>1)dp[!t][j]=min(dp[!t][j],dp[t][j]+(long long)j*(x[i+1]-x[i])+min(B[i]+C[i],A[i]+D[i]));
				else if(j==1){
					if(b<i)dp[!t][j]=min(dp[!t][j],dp[t][j]+(long long)j*(x[i+1]-x[i])+A[i]+D[i]);
					else dp[!t][j]=min(dp[!t][j],dp[t][j]+(long long)j*(x[i+1]-x[i])+C[i]+B[i]);
				}
				if(j>2||(j==2&&i==a-1))dp[!t][j-2]=min(dp[!t][j-2],dp[t][j]+(long long)(j-2)*(x[i+1]-x[i])+A[i]+C[i]);
			}
		}
	}
	printf("%I64d\n",dp[a%2][0]);
}

C:
¬とかを無視すれば輪と直線しかないので、一次元にできてあとはありがちなDPをするだけですが、結構実装量が多いです。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int L[110000];
int R[110000];
vector<int>g[110000];
int ABS(int a){
	return max(a,-a);
}
int num=1;
int ord[110000];
int lm[110000];
int v[110000];
pair<int,int> p[110000];
long long dp[110000][2][2][2];
vector<int>q[110000];
int main(){
	int a,b;scanf("%d%d",&b,&a);
	for(int i=0;i<b;i++){
		int x;scanf("%d",&x);
		if(x==1){
			scanf("%d",L+i);
		}else{
			scanf("%d%d",L+i,R+i);
		//	if(ABS(L[i])<ABS(R[i]))swap(L[i],R[i]);
			if(ABS(L[i])!=ABS(R[i])){
				g[ABS(L[i])].push_back(ABS(R[i]));
				g[ABS(R[i])].push_back(ABS(L[i]));
			}
		}
	}
	for(int i=1;i<=a;i++)v[i]=-1;
	for(int i=1;i<=a;i++)p[i]=make_pair(g[i].size(),i);
	std::sort(p+1,p+a+1);
	for(int i=1;i<=a;i++){
		int at=p[i].second;
		if(~v[at])continue;
		int id=at;
		int tl=num;
		if(p[i].first!=2)tl=-1;

		while(1){
			bool ok=false;
			ord[num]=id;
			v[id]=num++;
			lm[id]=tl;
			for(int j=0;j<g[id].size();j++){
				if(~v[g[id][j]])continue;
				ok=true;
				id=g[id][j];
				break;
			}
			if(!ok)break;
		}
	}
	for(int i=0;i<b;i++){
		q[max(v[ABS(L[i])],v[ABS(R[i])])].push_back(i);
	}
//	for(int i=1;i<=a;i++)printf("%d ",v[i]);
//	printf("\n");
	dp[0][0][0][0]=1;
	for(int i=0;i<a;i++){
		for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<2;l++){
			if(!dp[i][j][k][l])continue;
			for(int m=0;m<2;m++){
				int tl=l;
				int tk=m;
				int tj=j;
				if(lm[ord[i+1]]==i+1)tj=m;

				for(int t=0;t<q[i+1].size();t++){
					int ql=L[q[i+1][t]];
					int qr=R[q[i+1][t]];
					if(ABS(ql)==ord[i+1]){
						if(qr==0){
							if(ql>0&&m)tl^=1;
							if(ql<0&&!m)tl^=1;
						}else if(ABS(qr)==ord[i+1]){
							if(((ql<0)^m)||((qr<0)^m))tl^=1;
						}else if(ABS(qr)==ord[i]){
							if(((ql<0)^m)||((qr<0)^k))tl^=1;
						}else{
							if(((ql<0)^m)||((qr<0)^j))tl^=1;
						}
					}else{
						if(ABS(ql)==ord[i]){
							if(((qr<0)^m)||((ql<0)^k))tl^=1;
						}else{
							if(((qr<0)^m)||((ql<0)^j))tl^=1;
						}
					}
				}
				dp[i+1][tj][tk][tl]=(dp[i+1][tj][tk][tl]+dp[i][j][k][l])%mod;
			}
		}
	}
	long long ret=0;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++)ret+=dp[a][i][j][1];
	ret%=mod;
	printf("%d\n",(int)ret);
}

AIM Tech Round 3 (Div. 1)

Virtual Participationはオンラインジャッジではありませんが......
他の参加者全員が知っている典型を知らないとどうしようもなくなる好例。しっかりと典型を強くしておくことが求められるセット。AとかBとかかなりいやらしいけど。

A B C D E Place
00:02 00:24 (+3) 01:36 (+5) - - 165th

A:
a以外を探してaが出るまで変える。全部aのときがコーナーケース。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[110000];
int main(){
	scanf("%s",in);
	int n=strlen(in);
	bool ok=false;
	for(int i=0;i<n;i++){
		if(in[i]!='a'){
			ok=true;
			for(int j=i;j<n;j++){
				if(in[j]!='a')in[j]--;
				else break;
			}
			break;
		}
	}
	if(!ok){
		in[n-1]='z';
	}
	printf("%s\n",in);
}

B:
0,1の個数が簡単にわかるのであとは少しずつずらして構成。ずらしに失敗しやすいケースがいくつもある。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
long long a[4];
char out[1010000];
int main(){
	for(int i=0;i<4;i++)scanf("%I64d",a+i);
	long long t=0;
	for(int i=0;i<4;i++)t+=a[i];
	if(t==0){
		printf("1\n");return 0;
	}
	int sz=0;
	while((long long)sz*(sz-1)/2<t)sz++;
	if((long long)sz*(sz-1)/2!=t){
		printf("Impossible\n");return 0;
	}
	for(int i=0;i<=sz;i++){
		long long B=(long long)i*(i-1)/2;
		long long W=(long long)(sz-i)*(sz-i-1)/2;
		if(a[0]==B&&a[3]==W){
			if(a[1]+a[2]!=(long long)i*(sz-i)){
				printf("Impossible\n");return 0;
			}
			if(i==0){
				for(int j=0;j<sz;j++)printf("1");printf("\n");return 0;
			}else if(i==sz){
				for(int j=0;j<sz;j++)printf("0");printf("\n");return 0;
			}

			int ind=0;
			for(int j=0;j<a[2]/i;j++)out[ind++]='1';
			for(int j=0;j<i-a[2]%i;j++)out[ind++]='0';
			out[ind++]='1';
			for(int j=0;j<a[2]%i;j++)out[ind++]='0';
			for(int j=0;j<sz-i-a[2]/i-1;j++)out[ind++]='1';
				out[sz]=0;
			printf("%s\n",out);
			return 0;
		}
	}
	printf("Impossible\n");
}

C:
初めて全方位木DPというものに触れた。O(次数^2)かかると落ちるから名前がついているというのも全然知らなかったので勝手にTLEを出しまくっていた。
感覚的には、根のない木で木DPする感じ?

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<int>g[410000];
pair<int,int> z[820000];
int L[820000];
int R[820000];
int dp[820000][2];
int v[820000];
int num;
void dfs(int a,int b){
	for(int i=0;i<g[a].size();i++){
		L[num]=a;R[num]=g[a][i];
		z[num++]=make_pair(a,g[a][i]);
	}
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		dfs(g[a][i],a);
	}
}
int n;
int vis[410000];
int ans[410000];
int un[410000];
int fin(int a,int b){
	return lower_bound(z,z+num,make_pair(a,b))-z;
}
pair<int,int> ef[410000][2];
pair<int,int> tm[410000][2];
pair<int,int> calc(int a,int b){
	int at=lower_bound(z,z+num,make_pair(a,b))-z;
	if(v[at])return make_pair(dp[at][0],dp[at][1]);
	v[at]=1;
	if(!vis[a]){
		vis[a]=1;

		for(int i=0;i<g[a].size();i++){
			if(g[a][i]==b){
				un[a]=i;
				continue;
			}
			pair<int,int> tmp=calc(g[a][i],a);
			dp[at][0]+=tmp.first;
			if(ef[a][0].first<tmp.first-tmp.second){
				ef[a][1]=ef[a][0];ef[a][0]=make_pair(tmp.first-tmp.second,g[a][i]);
			}else if(ef[a][1].first<tmp.first-tmp.second){
				ef[a][1]=make_pair(tmp.first-tmp.second,g[a][i]);
			}
			if(tm[a][0].first<tmp.first){
				tm[a][1]=tm[a][0];tm[a][0]=make_pair(tmp.first,g[a][i]);
			}else if(tm[a][1].first<tmp.first){
				tm[a][1]=make_pair(tmp.first,g[a][i]);
			}
		}
		dp[at][0]++;
	}else{
		if(un[a]!=-1){
			int ind=un[a];
			un[a]=-1;
			pair<int,int> tmp=calc(g[a][ind],a);
			if(ef[a][0].first<tmp.first-tmp.second){
				ef[a][1]=ef[a][0];ef[a][0]=make_pair(tmp.first-tmp.second,g[a][ind]);
			}else if(ef[a][1].first<tmp.first-tmp.second){
				ef[a][1]=make_pair(tmp.first-tmp.second,g[a][ind]);
			}
			if(tm[a][0].first<tmp.first){
				tm[a][1]=tm[a][0];tm[a][0]=make_pair(tmp.first,g[a][ind]);
			}else if(tm[a][1].first<tmp.first){
				tm[a][1]=make_pair(tmp.first,g[a][ind]);
			}
		}
		dp[at][0]=n-dp[fin(b,a)][0];
	}
	int ef1,tm1;
	if(ef[a][0].second!=b)ef1=ef[a][0].first;
	else ef1=ef[a][1].first;
	if(tm[a][0].second!=b)tm1=tm[a][0].first;
	else tm1=tm[a][1].first;
	dp[at][1]=dp[at][0]-ef1;
	if(tm1<=n/2)dp[at][1]=min(dp[at][1],dp[at][0]-tm1);
	
	//printf("%d %d: %d %d\n",a,b,dp[at][0],dp[at][1]);
	return make_pair(dp[at][0],dp[at][1]);
}
int main(){
	int a;scanf("%d",&a);
	n=a;
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);
		p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	dfs(0,-1);
	std::sort(z,z+num);
	for(int i=0;i<num;i++){
		L[i]=z[i].first;R[i]=z[i].second;
	}
	for(int i=0;i<num;i++){
		if(v[i])continue;
		calc(L[i],R[i]);
	}
	for(int i=0;i<a;i++){
		bool ok=true;
		for(int j=0;j<g[i].size();j++){
			int at=lower_bound(z,z+num,make_pair(g[i][j],i))-z;
			if(dp[at][1]>a/2)ok=false;
		}
		if(ok)ans[i]=1;
	}
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}
	printf("\n");
}

D:
線形計画の式にはできたけどこれの双対が良い性質なのかどうかはわからないので、とりあえず線形計画の式だけ書いておくことにする。
そもそも双対の取り方がいまいちよくわからない。将来的に困るからちゃんとこういうの高校で授業して。
[条件]

  • f_{e1}>=0
  • f_{e2}>=0
  • d_{e}>=0
  • sum(in)(f_{e0}+f_{e1}-f_{e2})-sum(out)(f_{e0}+f_{e1}-f_{e2}) = 0
  • c_{e}+d_{e} >= f_{e0}+f_{e1}-f_{e2} >= 0

minimize sum d_{e} + sum f_{e1} + sum f_{e2}

Codeforces Round #371 (Div. 1)

ク ソ コ ン テ ス ト

A B C D E Place
00:04 00:37 00:20 01:36 - 7th

A:
もちろんmultisetなぞ必要なく、偶奇の組み合わせごとに何個あるか持っておけばよい。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[20];
int c[1<<18];
int main(){
	int a;scanf("%d",&a);
	while(a--){
		scanf("%s",in);
		long long b;
		scanf("%I64d",&b);
		if(in[0]=='+'){
			int now=0;
			for(int i=0;i<18;i++){
				if(b%2)now+=(1<<i);
				b/=10;
			}
			c[now]++;
		}else if(in[0]=='-'){
			int now=0;
			for(int i=0;i<18;i++){
				if(b%2)now+=(1<<i);
				b/=10;
			}
			c[now]--;
		}else{
			int now=0;
			for(int i=0;i<18;i++){
				if(b%2)now+=(1<<i);
				b/=10;
			}
			printf("%d\n",c[now]);
		}
	}
}

B:
二分探索でどこに上下左右の辺があるかがわかる。あとはどの辺がどの長方形に対応しているのかを全部試せばよい。結構実装がトリッキー。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int chk(int a,int b,int c,int d){
	if(a>c||b>d)return 0;
	printf("? %d %d %d %d\n",a,b,c,d);
	fflush(stdout);
	int ret;scanf("%d",&ret);
	return ret;
}
int val[4][2];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<4;i++){
		for(int j=0;j<2;j++){
			int left=0;
			int right=a+1;
			while(left+1<right){
				int M=(left+right)/2;
				int T,B,L,R;
				if(i==0){
					T=1;B=M;L=1;R=a;
				}else if(i==1){
					T=M;B=a;L=1;R=a;
				}else if(i==2){
					T=1;B=a;L=1;R=M;
				}else{
					T=1;B=a;L=M;R=a;
				}
				int val=chk(T,L,B,R);
				if(val>j){
					if(i%2==0){
						right=M;
					}else{
						left=M;
					}
				}else{
					if(i%2==0){
						left=M;
					}else right=M;
				}
			}
			if(i%2==0){
				val[i][j]=right;
			}else val[i][j]=left;
		}
	}
	for(int i=0;i<8;i++){
		if(chk(val[1][0],val[3][i/4],val[0][i%4/2],val[2][i%2])&&chk(val[1][1],val[3][!(i/4)],val[0][!(i%4/2)],val[2][!(i%2)])){
			printf("! %d %d %d %d %d %d %d %d\n",val[1][0],val[3][i/4],val[0][i%4/2],val[2][i%2],val[1][1],val[3][!(i/4)],val[0][!(i%4/2)],val[2][!(i%2)]);fflush(stdout);
			return 0;
		}
	}
}

C:
何度同じ問題が出れば気が済むんだ...

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[3100];
long long dp[3100][3100];
int z[3100];
long long ABS(long long a){
	return max(a,-a);
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	for(int i=0;i<a;i++)b[i]-=i;
	for(int i=0;i<a;i++)z[i]=b[i];
		std::sort(z,z+a);
	for(int i=0;i<3100;i++)for(int j=0;j<3100;j++)dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=1;i<=a;i++){
		long long tmp=inf;
		for(int j=0;j<a;j++){
			tmp=min(tmp,dp[i-1][j]);
			dp[i][j]=tmp+ABS(b[i-1]-z[j]);
		}
	}
	long long ret=inf;
	for(int i=0;i<a;i++)ret=min(ret,dp[a][i]);
	printf("%I64d\n",ret);
}

D:
そういや最大長方形忘れてたなと思ってググった。
クエリの中で二分探索をすると、答えがk以上かどうか判断するのは、長方形内の値の最大値がわかれば容易。
計算量が中途半端にきつく、そのままsegtreeとかにしてしまうと落ちる。1Dでも2Dでもいいのでsparse tableにしておけば、オーダーがわずかに落ちて間に合う。(いかにも強引に通してしまった別解のような解法だが、実際解説にはこれが書かれています......)

スパソを貼ったらポインタの代入がわからないので適当に配列に書き換えた。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;

int segtree[2048][11000];
void buildRMQ(int *a, int n,int to) {
  int logn = 1;
  for (int k = 1; k < n; k *= 2) ++logn;
  int *r = new int[n * logn];
  int *b = r; copy(a, a+n, b);
  for (int k = 1; k < n; k *= 2) {
    copy(b, b+n, b+n); b += n;
    for(int i=0;i< n-k;i++) b[i] = min(b[i], b[i+k]);
  }
for(int j=0;j<n*logn;j++)segtree[to][j]=r[j];
}
int minimum(int x, int y, int *rmq, int n) {
  int z = y - x, k = 0, e = 1, s; // y - x >= e = 2^k なる最大 k
  s = ( (z & 0xffff0000) != 0 ) << 4; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x0000ff00) != 0 ) << 3; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x000000f0) != 0 ) << 2; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x0000000c) != 0 ) << 1; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x00000002) != 0 ) << 0; z >>= s; e <<= s; k |= s;
  return min( rmq[x+n*k], rmq[y+n*k-e+1] );
}
int dp[1010][1010];
int f[2048][1100];
int c[1010][1010];
int L,R;
int m;
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 0;
	if(c<=a&&b<=d){
	//	printf("%d %d %d %d\n",a,b,L,R);fflush(stdout);
		int ret=minimum(L,R,segtree[e],m);
		return ret;
	}
	return min(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	m=b;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++)scanf("%d",&c[i][j]);
	}
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		if(!c[i][j])continue;
		int tmp=mod;
		if(i==0||j==0)tmp=0;
		else tmp=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
		dp[i][j]=tmp+1;
	}

	for(int i=0;i<a;i++)for(int j=0;j<b;j++)
		f[i+1024][j]=-dp[i][j];
	for(int i=2047;i>0;i--){
		for(int j=0;j<b;j++){
			f[i/2][j]=min(f[i/2][j],f[i][j]);
		}
		buildRMQ(f[i],b,i);
	//	segtree[i]=buildRMQ(f[i],b);
	}
	int T;scanf("%d",&T);
	while(T--){
		int p,q,r,s;
		scanf("%d%d%d%d",&p,&q,&r,&s);
		p--;q--;r--;s--;
		int left=0;
		int right=min(r-p+1,s-q+1)+1;
		while(left+1<right){
			int M=(left+right)/2;
			int t1=p+M-1;
			int t2=q+M-1;
			R=s;L=t2;
			//printf("%d %d\n",l,r);
			if(query(0,1023,t1,r,1)<=-M){
				left=M;
			}else{
				right=M;
			}
		}
		printf("%d\n",left);
	}
}