第3回 Dwangoからの挑戦状 Finals

えええ....。せっかくの優勝チャンスを逃した。

A	B	C	D	Place
118:47	70:40 (+2)	47:52 (+2)	-	5th

A:
ずっと前から見てて解けないと思ってトイレにいったら後ろからやるだけだった。こういうのが遅いのはダメでしょ

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#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[100];
int dp[60][60][60][2];
int v[60][60][60];
void solve(int a,int b,int c){
	if(v[a][b][c])return ;
	v[a][b][c]=1;
	// +
 
	dp[a][b][c][0]=-mod;
	dp[a][b][c][1]=mod;
	int rem=c;
	if(in[b]!='+')rem--;
	for(int i=a;i<b;i++){
		for(int j=0;j<=rem;j++){
			solve(a,i,j);
			solve(i+1,b-1,rem-j);
			if(dp[a][i][j][0]>-mod&&dp[i+1][b-1][rem-j][0]>-mod){
				dp[a][b][c][0]=max(dp[a][i][j][0]+dp[i+1][b-1][rem-j][0],dp[a][b][c][0]);
				dp[a][b][c][1]=min(dp[a][i][j][1]+dp[i+1][b-1][rem-j][1],dp[a][b][c][1]);	
			}
		}
	}
	// -
	rem=c;
	if(in[b]!='-')rem--;
	for(int i=a;i<b;i++){
		for(int j=0;j<=rem;j++){
			solve(a,i,j);
			solve(i+1,b-1,rem-j);
			if(dp[a][i][j][0]>-mod&&dp[i+1][b-1][rem-j][0]>-mod){
				dp[a][b][c][0]=max(dp[a][i][j][0]-dp[i+1][b-1][rem-j][1],dp[a][b][c][0]);
				dp[a][b][c][1]=min(dp[a][i][j][1]-dp[i+1][b-1][rem-j][0],dp[a][b][c][1]);	
			}
		}
	}
	if(a==b){
		if(c){
			dp[a][b][c][0]=max(dp[a][b][c][0],9);
			dp[a][b][c][1]=min(dp[a][b][c][1],0);
			
		}
		if('0'<=in[a]&&in[a]<='9'){
			dp[a][b][c][0]=max(dp[a][b][c][0],in[a]-'0');
			dp[a][b][c][1]=min(dp[a][b][c][1],in[a]-'0');
		}
	}
}
int main(){
	int a;scanf("%d%s",&a,in);
	int n=strlen(in);
	solve(0,n-1,a);
	if(dp[0][n-1][a][0]==-mod){
		printf("NG\n");return 0;
	}else printf("OK\n%d\n",dp[0][n-1][a][0]);
}

B:
はじめてのMo。速くできるのはわかるけども、速くしなくても定数倍で1/2くらいの割合の人が通るみたいなのは、経験のあるwriterがやるはずないですよね。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#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 si[11000];
 
int v[110000];
vector<pair<int,int> >ss[110000];
long long ret=1;
long long inv[2200000];
long long ans[110000];
int SQ=300;
vector<pair<pair<int,int>,int> > ev[350]; // rm, lm, id
int main(){
 
	int a,b;scanf("%d%d",&a,&b);
	inv[1]=1;
	for(int i=2;i<2200000;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=0;i<a;i++){
		int p;scanf("%d",&p);
		for(int j=2;j*j<=p;j++){
			if(p%j==0){
				int cur=0;
				while(p%j==0){
					p/=j;cur++;
				}
				ss[i].push_back(make_pair(j,cur));
				v[j]=1;
			}
		}
		if(p>1){
			v[p]=1;
			ss[i].push_back(make_pair(p,1));
		}
	}
	int sz=0;
	for(int i=0;i<110000;i++){
		if(v[i])v[i]=sz++;
	}
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;
		ev[p/SQ].push_back(make_pair(make_pair(q,p),i));
	}
	for(int i=0;i<350;i++){
		std::sort(ev[i].begin(),ev[i].end());
	}
	for(int i=0;i<350;i++){
		int l=i*SQ;
		int r=i*SQ;
		for(int j=0;j<sz;j++)si[j]=1;
		ret=1;
		for(int j=0;j<ev[i].size();j++){
			int p=ev[i][j].first.second;
			int q=ev[i][j].first.first;
			int id=ev[i][j].second;
			if(r<q){
				while(r<q){
					for(int k=0;k<ss[r].size();k++){
						int to=ss[r][k].first;
						int am=ss[r][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
					r++;
				}
			}
			if(l>p){
				while(l>p){
					for(int k=0;k<ss[l-1].size();k++){
						int to=ss[l-1][k].first;
						int am=ss[l-1][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
					l--;
				}
			}
			if(r>q){
				while(r>q){
					r--;
					for(int k=0;k<ss[r].size();k++){
						int to=ss[r][k].first;
						int am=-ss[r][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
				}
			}
			if(l<p){
				while(l<p){
					for(int k=0;k<ss[l].size();k++){
						int to=ss[l][k].first;
						int am=-ss[l][k].second;
						ret=(ret*(si[v[to]]+am)%mod*inv[si[v[to]]])%mod;
						si[v[to]]+=am;
					}
					l++;
				}
			}
			ans[id]=ret;
		}
	}
	for(int i=0;i<b;i++)printf("%lld\n",ans[i]);
}

C:
点を含む丸を121回で見つけたら、丸をどのくらい上に動かしても大丈夫か、どのくらい右に動かしても大丈夫かを二分探索で求めて。円の交点のどっちか1つが答え。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#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[110];
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
inline double ABS(double a){return max(a,-a);}
struct Pt {
	double x, y;
	Pt() {}
	Pt(double x, 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 double &k) const { return Pt(x * k, y * k); }
	Pt operator/(const double &k) const { return Pt(x / k, y / k); }
	double ABS() const { return sqrt(x * x + y * y); }
	double abs2() const { return x * x + y * y; }
	double arg() const { return atan2(y, x); }
	double dot(const Pt &a) const { return x * a.x + y * a.y; }
	double det(const Pt &a) const { return x * a.y - y * a.x; }
};
double tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }
pair<Pt,Pt> pCC(Pt a, double r, Pt b, double s) {
	double d = (b - a).ABS();
	double x = (d * d + r * r - s * s) / (d * 2);
	Pt e = (b - a) / d, w = e * Pt(0, 1) * sqrt(max(r * r - x * x, 0.0));
	return make_pair(a + e * x - w, a + e * x + w);
}
Pt c;
int main(){
	bool ok=false;
	for(int i=0;i<=10;i++){
		if(ok)break;
		for(int j=0;j<=10;j++){
			if(ok)break;
			printf("%d %d\n",i*100000,j*100000);fflush(stdout);
			scanf("%s",in);
			if(in[1]=='o')return 0;
			if(in[1]=='l'){
				ok=true;
				c=Pt(i*100000,j*100000);
			}
		}
	}
	double left=0;
	double right=200000;
	for(int i=0;i<35;i++){
		double M=(left+right)/2;
		printf("%.12f %.12f\n",c.x+M,c.y);
		fflush(stdout);
		scanf("%s",in);
		if(in[1]=='o')return 0;
		if(in[1]=='l')left=M;
		else right=M;
	}
	double X=c.x+left;
	left=0;
	right=200000;
	for(int i=0;i<35;i++){
		double M=(left+right)/2;
		printf("%.12f %.12f\n",c.x,c.y+M);
		fflush(stdout);
		scanf("%s",in);
		if(in[1]=='o')return 0;
		if(in[1]=='l')left=M;
		else right=M;
	}
	double Y=c.y+left;
	pair<Pt,Pt> tt=pCC(Pt(X,c.y),100000,Pt(c.x,Y),100000);
	int t1=tt.first.x-0.5;
	int t2=tt.first.y-0.5;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++){
		printf("%d %d\n",t1+i,t2+j);fflush(stdout);scanf("%s",in);
		if(in[1]=='o')return 0;
	}
	t1=tt.second.x-0.5;
	t2=tt.second.y-0.5;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++){
		printf("%d %d\n",t1+i,t2+j);fflush(stdout);scanf("%s",in);
		if(in[1]=='o')return 0;
	}
}

D:
どうみても遅延更新segtreeであることはわかるしだいたいこういうことがしたいというのはわかるけども、能力が至らず解けなかった。こういう負け方(敗因が練習不足であるのがはっきりしてるケース)が一番ダメ。