tozangezan's diary

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

SRM186 Div1 Hard

昔の問題は変な意味で面白い。

プログラミングコンテストの問題の題材としてアイスホッケーが出題されることは少なくありません.しかし,活動時間の全てをオンラインジャッジにつぎ込む生活では,アイスホッケーを想像することができず,問題の理解に困ってしまうこともあるでしょう.一分一秒を争うこの世界では,致命傷となりかねません.

当然この問題の本質は問題文読解なんだけど、まず普通の人が思い浮かべるのは、「好きな方向に打てて何回でも反射できるので最短距離を求める」みたいな感じ。しかしテストケースを見てみても問題の妥当性を考えてみてもこれはおかしいので、徐々に「反射は1回以下なのでは...?」と疑うことになる。
それでもなおうまくいかないので、魔力で反射が0回のケースは考慮してはいけないことと、問題文冒頭の The left-handed Finnish hockey player から左利き選手は右にシュートしやすそうだから右のみ反射なのでは?と考えるに至る。

実は、画像の下の段落にちょろっと反射のルールが書いてあるんだけど、実はここでは「right」としか書いてない上実はこれは反射の法則ではなく、この問題でvalidとみなされる移動の仕方である。知るか。

複数経路があるときの処理も謎でゴールの右端に近いものを採用するんだけど(角度のminではない)、これも実際ゴールを入れる人は端に打ってそうだなあと思うとなんか納得できなくもない感じになる。これらのエスパーによって同点のものがたくさん現れてどれを出力しないといけないか問題も解消できて一件落着。


冒頭みたいな逸話は笑い話のように扱われていますが、この「アイスホッケー」を「物理学」や「機械・パソコンの仕組み」に置き換えてみると、未だに背景知識がないと理解できない系の問題文を書く人がいます。専門的なストーリーにしたいときはちゃんと親切に全部問題文中に記述されているかどうかを念入りに確認しましょう。物体の落下の仕方の式やファイルのURLの表し方に説明がないなんて論外です。

// I like wolves!!
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const double EPS = 1e-13;
const double INF = 1e+10;
const double PI = acos(-1);
vector<Pt>L;
vector<Pt>R;
vector<Pt>hb;
class PuckShot {
	public:
	double caromAngle(int X0, vector <int> X, vector <int> Y) {
		int n=X.size();
		double val=INF;
		double ret=-1.0;
		hb.push_back(Pt(X0,1));
		for(int i=0;i<=1;i++){
			for(int j=0;j<n;j++){
				double tx=X[j];
				double ty=Y[j];
				if(i%2==0)tx+=3000*i;
				else{
					tx=3000-tx;
					tx+=3000*i;
				}
				L.push_back(Pt(tx-25,ty));
				R.push_back(Pt(tx+25,ty));
				hb.push_back(Pt(tx-25-(1e-10),ty));
				hb.push_back(Pt(tx+25+(1e-10),ty));
			}
			if(i==0)continue;
			Pt gl,gr;
			gl=Pt(3000*i+1408.5,1733);
			gr=Pt(3000*i+1591.5,1733);
			if(i%2)swap(gl,gr);
			hb.push_back(gl);
			hb.push_back(gr);
			for(int j=0;j<hb.size();j++){
				bool ok=true;
				for(int k=0;k<L.size();k++){
					if(iLS(Pt(X0,0),hb[j],L[k],R[k])){
						ok=false;break;
					}
				}
				if(!iLS(Pt(X0,0),hb[j],gl,gr))ok=false;
				if(ok){
					Pt p=pLL(Pt(X0,0),hb[j],gl,gr);
					double dist=(p-gr).ABS();
		//			printf("%f %f %f\n",hb[j].x,hb[j].y,dist);
					if(dist<val){
						val=dist;
						ret=(hb[j]-Pt(X0,0)).arg()*180/PI;
					}
				}
			}
		}
		return ret;
	}
};

最大独立集合 速め

696Mediumで書いたもの。38頂点を1000回実行して200ms弱と相当速い。
s[i][j]: 隣接行列
S[i]: 隣接行列を詰め込んだもの
v[i]: 頂点の利用状況
val: 答え
uk: v[i]=0のiを詰め込んだもの
n: 頂点数

int s[40][40];
long long S[40];
int v[40];
int val;
int n;
long long uk=0;
void calc(){
	int nm=0;
	for(int i=0;i<n;i++)if(v[i]==1)nm++;
	val=max(val,nm);
	for(int i=0;i<n;i++){
		if(v[i]==0&&__builtin_popcountll(uk&S[i])<2){
			v[i]=1;
			uk-=1LL<<i;
			long long ch=0;
			for(int j=0;j<n;j++)if(v[j]==0&&s[i][j]){v[j]=2;ch+=1LL<<j;uk-=1LL<<j;}
			calc();
			v[i]=0;
			uk+=1LL<<i;
			for(int j=0;j<n;j++)if(ch&(1LL<<j)){v[j]=0;uk+=1LL<<j;}
			return;
		}
	}
	int dm=1;
	int at=-1;
	for(int i=0;i<n;i++){
		if(v[i]==0&&__builtin_popcountll(uk&S[i])>=dm){
			dm=__builtin_popcountll(uk&S[i]);
			at=i;
		}
	}
	if(at==-1)return;
	v[at]=2;
	uk-=1LL<<at;
	calc();
	v[at]=0;
	uk+=1LL<<at;
	
	v[at]=1;
	uk-=1LL<<at;
	long long ch=0;
	for(int j=0;j<n;j++){
		if(v[j]==0&&s[at][j]){
			v[j]=2;
			uk-=1LL<<j;
			ch+=(1LL<<j);
		}
	}
	calc();
	for(int j=0;j<n;j++){
		if(ch&1LL<<j){v[j]=0;uk+=1LL<<j;}
	}
	v[at]=0;uk+=1LL<<at;
}

698F: Coprime Permutation

素因数→素因数の写像が何通りあるかと、それぞれの素因数内で数の並べ方が何通りあるか掛け算する。
前者は、同じ回数出現する素因数が自由に入れ替えられるので、それぞれの素因数に対して、indexにその素因数をもつ場所のgcdを求めて、対応をつけると自由度がわかので階乗をかける。
後者は、(素因数の集合)ごとに独立で、これも前計算してから同様に自由度を求めて階乗をかける。

でも証明はできていない。

#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 b[1100000];
int pr[1100000];
int st[1100000];
int to[1100000];
int val[1100000];
int wk[1100000];
int tk[1100000];
long long fact[1100000];
long long gcd(long long a,long long b){
	while(a){
		b%=a;swap(a,b);
	}
	return b;
}
int pl[110000];
int dec[1100000];
int used[1100000];
vector<int> pp[1100000];
int main(){
	int a;scanf("%d",&a);
	fact[0]=1;
	for(int i=1;i<1100000;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
	}
	pr[0]=pr[1]=-1;
	for(int i=2;i<1100000;i++){
		if(pr[i]==-1)continue;
		pr[i]=1;
		for(int j=i+i;j<1100000;j+=i)pr[j]=-1;
	}
	st[1]++;
	for(int i=2;i<=a;i++){
		if(pr[i]==1){
			st[a/i]++;
			for(int j=i;j<=a;j+=i)pp[j].push_back(i);
		}
	}
	int ind=0;
	for(int i=2;i<1100000;i++){
		if(pr[i]==1)pl[ind++]=i;
	}
	long long ret=1;
	if(pr[b[0]]==1||b[0]==1){
		used[b[0]]=1;
		dec[1]++;
	}
	for(int i=1;i<=a;i++){
		if(pr[i]==1){
			int now=0;
			for(int j=i;j<=a;j+=i){
				if(!b[j-1])continue;
				now=gcd(now,b[j-1]);
			}
			if(now!=0){
				bool ok=false;
				int ss=-1;
				for(int j=0;j<pp[now].size();j++){
					if(a/pp[now][j]==a/i){
						ss=pp[now][j];
						ok=true;break;
					}
				}
				if(!ok&&a/i==1&&now==1){
					ss=now;
					ok=true;
				}
			//	printf("%d: %d %d\n",i,now,ss);
				if(used[ss]||!ok){

					printf("0\n");return 0;
				}
				used[ss]=1;
				dec[a/i]++;
			}
		}
	}
	for(int i=1;i<=a;i++)ret=ret*fact[st[i]-dec[i]]%mod;
	for(int i=1;i<=a;i++)val[i]=1;
	for(int i=2;i<=a;i++){
		if(pr[i]==1){
			for(int j=i;j<=a;j+=i)val[j]*=i;
		}
	}
	for(int i=1;i<=a;i++)wk[val[i]]++;
	for(int i=0;i<a;i++){
		if(b[i])tk[val[b[i]]]++;
	}
	for(int i=1;i<=a;i++)ret=ret*fact[wk[i]-tk[i]]%mod;
	printf("%I64d\n",ret);
}

Codeforces Round #348 (VK Cup 2016 Round 2, Div. 1 Edition)

何だこのセットは......。難問が誰にも存在しないセットだと、簡単が速いから勝ててしまう。

A B C D E F Place
00:13 00:06 00:34 (+1) 00:48 - - 4th

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;
int p[11000][4];
int mat[110][110];
int main(){
	int a,b,c;scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<c;i++){
		scanf("%d%d",&p[i][0],&p[i][1]);
		p[i][1]--;
		if(p[i][0]==3){
			scanf("%d%d",&p[i][2],&p[i][3]);
			p[i][2]--;
		}
	}
	for(int i=c-1;i>=0;i--){
		if(p[i][0]==3){
			mat[p[i][1]][p[i][2]]=p[i][3];
		}else if(p[i][0]==2){
			int tmp=mat[a-1][p[i][1]];
			for(int j=a-1;j>0;j--){
				mat[j][p[i][1]]=mat[j-1][p[i][1]];
			}
			mat[0][p[i][1]]=tmp;
		}else{
			int tmp=mat[p[i][1]][b-1];
			for(int j=b-1;j>0;j--){
				mat[p[i][1]][j]=mat[p[i][1]][j-1];
			}
			mat[p[i][1]][0]=tmp;
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(j)printf(" ");
			printf("%d",mat[i][j]);
		}
		printf("\n");
	}
}

B:
偶奇ごとに持っておけば、偶数奇数それぞれの中では平行移動してるだけ。

#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 ret[1100000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	int p1=0;
	int p2=1;
	while(b--){
		int c;scanf("%d",&c);
		if(c==1){
			int d;scanf("%d",&d);
			p1+=d;
			p2+=d;
			if(p1<0)p1+=a;
			if(p2<0)p2+=a;
			if(p1>=a)p1-=a;
			if(p2>=a)p2-=a;
			
		}else{
			p1^=1;
			p2^=1;
		}
	}
	for(int i=0;i<a/2;i++){
		ret[(p1+i*2)%a]=i*2+1;
		ret[(p2+i*2)%a]=i*2+2;
	}
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%d",ret[i]);
	}
	printf("\n");
}

C:
手元で二次方程式を解く・sqrtの中身を負にしないように

#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;
double A[110000];
double B[110000];

double x[110000];
double y[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%lf",A+i);
	for(int i=0;i<a;i++)scanf("%lf",B+i);
	double p1=0;
	double p2=0;
	for(int i=0;i<a;i++)p2+=B[i];
	for(int i=0;i<a-1;i++){
		p1+=A[i];
		p2-=B[i];
		y[i]=0.5*((p1-p2+1)+sqrt(max(0.0,(p1-p2+1)*(p1-p2+1)-4.0*p1)));
		x[i]=0.5*((p1-p2+1)-sqrt(max(0.0,(p1-p2+1)*(p1-p2+1)-4.0*p1)));
	}
	x[a-1]=y[a-1]=1;
	for(int i=a-1;i>0;i--){
		x[i]-=x[i-1];
		y[i]-=y[i-1];
	}
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%.12f",x[i]);
	}
	printf("\n");
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%.12f",y[i]);
	}
	printf("\n");
	
}

D:
追加する数ごとに独立で、内部でも座標圧縮してBITするだけ...。残り2問と比べてあまりにも簡単すぎる。

#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 x[110000];
int b[110000];
int t[110000];
int z[110000];
vector<int>q[110000];
int bit[110000];
int sz;
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<sz;a|=a+1)bit[a]+=b;
}
int z2[110000];
int ans[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d%d",b+i,t+i,x+i);
		z[i]=x[i];
	}
	std::sort(z,z+a);
	for(int i=0;i<a;i++){
		int at=lower_bound(z,z+a,x[i])-z;
		q[at].push_back(i);
	}
	for(int i=0;i<a;i++){
		if(q[i].size()){
			sz=q[i].size();
			for(int j=0;j<q[i].size();j++){
				z2[j]=t[q[i][j]];
			}
			std::sort(z2,z2+sz);
			for(int j=0;j<q[i].size();j++){
				int ind=lower_bound(z2,z2+sz,t[q[i][j]])-z2;
				if(b[q[i][j]]==1){
					add(ind,1);
				}else if(b[q[i][j]]==2){
					add(ind,-1);
				}else{
					ans[q[i][j]]=sum(0,ind);
				}
			}
			for(int j=0;j<sz;j++)bit[j]=0;
		}
	}
	for(int i=0;i<a;i++){
		if(b[i]!=3)continue;
		printf("%d\n",ans[i]);
	}
}

F:
虚無。
Black box linear algebraを勉強する(これも虚無)か、虚無を実装するか。木分解でもうまくいきそうに見えるけどどうなんだこれ。

第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であることはわかるしだいたいこういうことがしたいというのはわかるけども、能力が至らず解けなかった。こういう負け方(敗因が練習不足であるのがはっきりしてるケース)が一番ダメ。

Codeforces Round #349 (Div. 1)

いつもと同じ死に方。成長が見られない。相変わらず注意力が灰底辺。

A B C D E Place
00:48 (+1) 00:35 (+4) 01:59 (+1) - - 59th

A:
メモ化再帰するだけ。メモ化し忘れて1TLE。

#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[11000];
int dp[11000][3];
set<string>S;
char tmp[4];
int n;
int solve(int a,int b){
	if(~dp[a][b])return dp[a][b];
	if(a==n)return dp[a][b]=1;
	int t=0;
	if(a<=n-2){
		if(b!=0||in[a]!=in[a-2]||in[a+1]!=in[a-1]){
			int res=solve(a+2,0);
			if(res){
				t=res;
				tmp[2]=0;tmp[0]=in[a];tmp[1]=in[a+1];string tt=tmp;S.insert(tt);
			}
		}	
	}
	if(a<=n-3){
		if(b!=1||in[a]!=in[a-3]||in[a+1]!=in[a-2]||in[a+2]!=in[a-1]){
			int res=solve(a+3,1);
			if(res){
				t=res;
				tmp[3]=0;tmp[0]=in[a];tmp[1]=in[a+1];tmp[2]=in[a+2];string tt=tmp;S.insert(tt);
			}
		}	
	}
	return dp[a][b]=t;
}
int main(){
	scanf("%s",in);
	n=strlen(in);
	for(int i=0;i<11000;i++)for(int j=0;j<3;j++)
		dp[i][j]=-1;
	for(int i=5;i<=n;i++){
		solve(i,2);
	}
	printf("%d\n",(int)(S.size()));
	for(set<string>::iterator it=S.begin();it!=S.end();it++)printf("%s\n",(*it).c_str());
}

B:
なにも変な要素がないのにひたすらWA。頭が悪すぎる。

#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[3100];
int dist[3100][3100];
int L[3100][3];
int R[3100][3];
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);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++)dist[i][j]=-1;
		queue<int>Q;
		Q.push(i);
		dist[i][i]=0;
		while(Q.size()){
			int at=Q.front();Q.pop();
			for(int j=0;j<g[at].size();j++){
				int to=g[at][j];
				if(dist[i][to]==-1){
					dist[i][to]=dist[i][at]+1;
					Q.push(to);
				}
			}
		}
	}
	for(int i=0;i<a;i++){
		L[i][0]=L[i][1]=L[i][2]=-1;
		for(int j=0;j<a;j++){
			if(i==j)continue;
			if(dist[j][i]==-1)continue;
			if(L[i][0]==-1||dist[j][i]>dist[L[i][0]][i]){
				L[i][2]=L[i][1];
				L[i][1]=L[i][0];
				L[i][0]=j;
			}else if(L[i][1]==-1||dist[j][i]>dist[L[i][1]][i]){
				L[i][2]=L[i][1];
				L[i][1]=j;
			}else if(L[i][2]==-1||dist[j][i]>dist[L[i][2]][i]){
				L[i][2]=j;
			}
		}
	}
	for(int i=0;i<a;i++){
		R[i][0]=R[i][1]=R[i][2]=-1;
		for(int j=0;j<a;j++){
			if(i==j)continue;
			if(dist[i][j]==-1)continue;
			if(R[i][0]==-1||dist[i][j]>dist[i][R[i][0]]){
				R[i][2]=R[i][1];
				R[i][1]=R[i][0];
				R[i][0]=j;
			}else if(R[i][1]==-1||dist[i][j]>dist[i][R[i][1]]){
				R[i][2]=R[i][1];
				R[i][1]=j;
			}else if(R[i][2]==-1||dist[i][j]>dist[i][R[i][2]]){
				R[i][2]=j;
			}
		}
	}
	int A,B,C,D;
	int bs=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			for(int k=0;k<3;k++)for(int l=0;l<3;l++){
				if(L[i][k]==-1||R[j][l]==-1||dist[i][j]==-1)continue;
				if(i==j||i==R[j][l]||j==L[i][k]||L[i][k]==R[j][l])continue;
				if(bs<dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]]){
					bs=dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]];
					A=L[i][k];B=i;C=j;D=R[j][l];
				}
			}
		}
	}
	set<int>S;
	S.insert(A);
	S.insert(B);
	S.insert(C);
	S.insert(D);
	if(S.size()!=4){
		while(1);
	}
	printf("%d %d %d %d\n",A+1,B+1,C+1,D+1);
}

C:
nCkテーブルをsqrt(N)段ごとに作っておいて一行ずつ下がるやつに係数をつけただけ。一箇所-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[110000];
int n;
int sz=0;
pair<pair<int,int>,int>p[110000];
int ans[110000];
int SQ=300;
long long fact[110000];
long long inv[110000];
long long finv[110000];
long long C(int a,int b){
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
long long val[110000];
long long sum[110000];
long long p26[110000];
long long p25[110000];
int main(){
	fact[0]=finv[0]=1;
	p26[0]=1;
	p25[0]=1;
	inv[1]=1;
	for(int i=2;i<110000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<110000;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
		p26[i]=p26[i-1]*26%mod;
		p25[i]=p25[i-1]*25%mod;
	}
	int a;scanf("%d",&a);
	scanf("%s",in);
	n=strlen(in);
	while(a--){
		int t;scanf("%d",&t);
		if(t==1){
			scanf("%s",in);
			n=strlen(in);
		}else{
			int b;scanf("%d",&b);
			p[sz]=make_pair(make_pair(b,n),sz);
			sz++;
		}
	}
	std::sort(p,p+sz);
	int at=0;
	for(int i=0;i<340;i++){
		long long ks=1;
		for(int j=i*SQ;j>=0;j--){
			val[j]=C(i*SQ,j)*ks;
			ks=ks*25%mod;
		}
		for(int j=0;j<=i*SQ;j++){
			sum[j]=val[j];
			if(j)sum[j]=(sum[j]+sum[j-1])%mod;
		}
		while(at<sz&&p[at].first.first<(i+1)*SQ){

			if(p[at].first.first<p[at].first.second){
				at++;continue;
			}
			long long now=sum[min(i*SQ,p[at].first.second-1)];

			int r=min(i*SQ,p[at].first.second-1);
			for(int j=0;j<p[at].first.first%SQ;j++){
				if(r==p[at].first.second-1){
					now=now*26%mod;
					now=(now+mod-C(i*SQ+j,r)*p25[i*SQ+j-r]%mod)%mod;
				}else{
					now=now*26%mod;
					r++;
				}
			}

			ans[p[at].second]=(p26[p[at].first.first]+mod-now)%mod;
			at++;
		}
	}
	for(int i=0;i<sz;i++)printf("%d\n",ans[i]);
}

Codeforces Round #352 (Div. 1)

心が折れた。
灰コーダー並みの注意力だったのも悪いけど、サンプルも弱いし罠も多すぎだと思う。

A B C D E Place
00:28 (+1) 00:14 (+2) -5 - - 105th

A:
嫌なケースが多すぎる。returnを忘れた。

#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=1000010007;
const long long inf=mod*mod;
double x[3];
double y[3];
double X[110000];
double Y[110000];
double dist(double dx,double dy){
	return sqrt(dx*dx+dy*dy);
}
pair<double,int> ta[110000];
pair<double,int> tb[110000];
int main(){
	for(int i=0;i<3;i++){
		scanf("%lf%lf",x+i,y+i);
	}
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%lf%lf",X+i,Y+i);
	}
	if(a==1){
		printf("%.12f\n",min(dist(X[0]-x[0],Y[0]-y[0]),dist(X[0]-x[1],Y[0]-y[1]))+dist(X[0]-x[2],Y[0]-y[2]));
		return 0;
	}
	double ret=0;
	for(int i=0;i<a;i++){
		ret+=dist(X[i]-x[2],Y[i]-y[2])*2;
		ta[i]=make_pair(dist(X[i]-x[0],Y[i]-y[0])-dist(X[i]-x[2],Y[i]-y[2]),i);
		tb[i]=make_pair(dist(X[i]-x[1],Y[i]-y[1])-dist(X[i]-x[2],Y[i]-y[2]),i);
	}
	double ad=99999999999999.9;
	std::sort(ta,ta+a);
	std::sort(tb,tb+a);
	for(int i=0;i<2;i++)for(int j=0;j<2;j++){
		if(ta[i].second==tb[j].second)continue;
		ad=min(ta[i].first+tb[j].first,ad);
	}
	ad=min(ad,min(ta[0].first,tb[0].first));
	printf("%.12f\n",ret+ad);
}

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=1000010007;
const long long inf=mod*mod;
int c[510000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	long long sum=0;
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
		sum+=c[i];
	}
	std::sort(c,c+a);
	int left=0;
	int right=mod;
	while(left+1<right){
		int M=(left+right)/2;
		long long cur=0;
		for(int i=0;i<a;i++){
			if(c[i]<M)cur+=M-c[i];
		}
		if(b<cur){
			right=M;
		}else left=M;
	}
	int q1=left;
	left=0;
	right=mod;
	while(left+1<right){
		int M=(left+right)/2;
		long long cur=0;
		for(int i=0;i<a;i++){
			if(c[i]>M)cur+=c[i]-M;
		}
		if(b<cur){
			left=M;
		}else right=M;
	}
	int q2=right;
	if(q1>q2)q1=q2;
	if(q2-q1==0&&sum%a)q2++;
	printf("%d\n",q2-q1);
}

C:
二重に誤読していた。が解けるものには見えない。