atcoder CODE FESTIVAL 2017 qual A手速(霧)試合

この試合はとても重要そうに見えますが、(結局大勢の大物が来て誰もqaqに勝てませんでした)
A,B問題は何をしているのか分からない.
C問題(実は何をしているのか分からない)はアルファベットマトリクスをあげて、並べ直して水平軸対称+垂直軸対称にできるかどうかを聞くことです.
1つのマトリクスは最大3つの部分から構成されることが分かった:1.中心点は、1文字必要です.2.中軸線は、2つの同じアルファベットが1対で記入する必要があります.3.残りの部分は、4つの同じアルファベットを1つのグループに記入する必要があります.明らかに3で2を埋めることができ、2で1を埋めることができるので、3->2->1から欲張ればいいと考えています.
MACコードは以下の通りである.

#include
using namespace std;
 
int m,n,num[26]; char s[100009];
int main(){
	scanf("%d%d",&m,&n);
	int s1=(m>>1)*(n>>1),s2=(m&1)*(n>>1)+(m>>1)*(n&1),s3=m&n&1;
	int i,j;
	for (i=1; i<=m; i++){
		scanf("%s",s+1);
		for (j=1; j<=n; j++) num[s[j]-'a']++;
	}
	for (i=0; i<26; i++){
		while (num[i]>=4 && s1){ num[i]-=4; s1--; }
		while (num[i]>=2 && s2){ num[i]-=2; s2--; }
		while (num[i] && s3){ num[i]--; s3--; }
		if (num[i]) break;
	}
	puts(i<26?"No":"Yes");
	return 0;
}

         
D問題から始まってやっと金の量の問題があって、(F問題もそんなに難しくないかも?)、それから私はD問題を開場して、出力フォーマットを見間違えて2発ojを爆発させて、、、ああつらいです
マンハッタンの距離がちょうどdの任意の対の点の色が異なるように、m,n,dを4色に染める案を構築することを要求しています.
まずx+y->x,x-y->yを考えると,(x,y)を中心として,辺心距離dの正方形の輪郭は同色を飲めない(x,y)ことになる.xが存在する行を考慮すると、まずd個を1段とし、1色を変えてからd個を1段とし、元の色d個を1段と変えて染めることができます.これにより2次元に広がり,1つのd*dの正方形を1単位とし,その後4つの色ごとに2つ異なることを考慮すると,条件を満たすことが分かった.
MACコードは以下の通りである.

#include
using namespace std;
 
char ch[2][2]={{'R','B'},{'G','Y'}}; int n,m,k;
char calc(int x,int y){
	int a=x+y,b=x-y;
	a+=2000; b+=2000;
	a/=k; b/=k; a&=1; b&=1;
	return ch[a][b];
}
int main(){
	scanf("%d%d%d",&m,&n,&k);
	int i,j;
	for (i=1; i<=m; i++){
		for (j=1; j<=n; j++) printf("%c",calc(i,j)); puts("");
	}
	return 0;
}

         
E問題は唯一難易度のある問題ではないでしょうか.どうせ私は長い間やったのかもしれません.
E題はあなたにm*nの矩形をあげることを意味して、矩形の周囲に何人かの人がいて、すべての人は向こうに向かってまっすぐ行って、1つの染色された四角い格子まで歩くことを知っています.そして歩いているうちに足元の格子を自分の色に染めます.人によって色が違います.最後の長方形の様子を求めていくつかあります.
まず上下/左右に分けて先に行く場合があります.上下を考えて先に進むと、矩形を左右に分けます.さらに,一番早く歩いたのが上下中のx番目とy番目であれば,x~yの真ん中の人は左右されないことが分かった.だから一番早く歩いたのはx~y個目で、それから左右の人が歩いたと考えることができます.
f[i]をi+1の左側を歩いたシナリオ数、g[i]をi-1の右側を歩いたシナリオ数とすると、答えはΣf[i]*g[j]*2^(s[j]-1-s[i])=Σ(f[i]/2^s[i])*(g[j]*2^s[j-1])のうち、s[i]は1~iのうちいくつかが上下に人がいることを示す.そこで肝心なのはf[i]を求めることであり、同様に左の先がa~bであることを考慮すると、答えはC(a+c,a)*C(b+d,b)であり、そのうちc,dは前のi列の中で上、次の人が何人いるかを表す.C(a+c,a)で表される(0,0)で(a,c)に至るシナリオを考えると、答えは(0,0)から(c+d,t)に至るのと等価であり、c列目で少なくとも一歩上に行かなければならないシナリオ数であり、tは左側に何人かいることを示す.だから答えはC(c+d+t,t)-C(c+d-1+t,t)です.
最後に特判全0の場合に注意
MACコードは以下の通りである.

#include
#define N 400009
#define ll long long
#define mod 998244353
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
using namespace std;
 
int m,n,a[N],b[N],fac[N],inv[N]; char A[N],B[N],C[N],D[N];
int solve(int m,int n,char *A,char *B,char *C,char *D){
	int i,x,y;
	memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
	a[0]=b[n+1]=1;
	for (i=1,y=0; i<=m; i++) if (A[i]=='1') y++;
	for (i=1,x=0; i<=n; i++){
		if (C[i]=='1') x++;
		if (D[i]=='1') x++;
		a[i]=cbn(x+y,x);
		if (x) a[i]=(a[i]-cbn(x+y-1,x-1)+mod)%mod;
		//cout<0) b[i]=(b[i]-cbn(x+y-1,x-1)+mod)%mod;
		//cout<0 && C[i]=='1' && D[i]=='1') tmp=(ll)tmp*(mod+1>>1)%mod;
		a[i]=(ll)a[i]*tmp%mod;
		if (i<=n && C[i+1]=='0' && D[i+1]=='0') a[i]=0;
	}
	for (i=1; i<=n; i++) a[i]=(a[i]+a[i-1])%mod;
	for (i=tmp=1; i<=n+1; i++){
		b[i]=(ll)b[i]*tmp%mod;
		if (i<=n && C[i]=='1' && D[i]=='1') tmp=tmp*2%mod;
		if (i>1 && C[i-1]=='0' && D[i-1]=='0') b[i]=0;
	}
	int ans=0;
	for (i=1; i<=n; i++) ans=(ans+(ll)b[i+1]*a[i-1])%mod;
	//cout<m){
		for (i=1; i<=n; i++) if (C[i]=='1' || D[i]=='1') break;
		if (i>n){ puts("1"); return 0; }
	}
	fac[0]=inv[0]=inv[1]=1;
	for (i=1; i<=(m+n<<1); i++) fac[i]=(ll)fac[i-1]*i%mod;
	for (i=2; i<=(m+n<<1); i++) inv[i]=mod-(ll)inv[mod%i]*(mod/i)%mod;
	for (i=2; i<=(m+n<<1); i++) inv[i]=(ll)inv[i-1]*inv[i]%mod;
	printf("%d
",(solve(m,n,A,B,C,D)+solve(n,m,C,D,A,B))%mod);
	return 0;
}

            
最後のF問題はE問題よりずっと簡単になったようだ.私のAはEを落としてFがすでに1枚過ぎたことを発見して、qaq
Fはいくつかの1の構成が知られているシーケンスであり、その後、毎回2 nの連続数を選択することができ、(1,2)(3,4),...(2 n−1,2 n)のように結合し,最終的なシーケンスを得た.今、最終的なシーケンスを教えて、最低数歩を求めます.
明らかに逆さまにやるべきだ.1回の操作を考えると、連続するいくつかの>1の数を半分に分解し、明らかに均一な2部に分解すべきである.xを分解する過程を考慮すると,各ステップの後は2つの部分からなり,一部はtであり,もう一部はt+1である.
そして原問題を考える.明らかに1は元の問題を2つのサブ問題に分ける.明らかに最小の数が最も早く1を生み出すと,原問題を2つの問題に分けて再帰的に行う.最小の数が1を生成した後に部分2がある可能性があることに気づいて、左か右かを列挙する必要があります.
MACコードは以下の通りである.

#include
#define N 100009
using namespace std;
 
int n,a[N],lg2[N];
struct node{ int x,y; }f[17][N],b[N];
struct matrix{ int p[2][2]; };
bool operator 1; i>>=1){
		b[k].x++;
		if (i&1) flag=1;
	}
	b[k].y=flag;
}
matrix solve(int l,int r,int dep){
	//cout<r){
		matrix x;
		x.p[0][0]=0; x.p[0][1]=x.p[1][0]=x.p[1][1]=1;
		return x;
	}
	int mid=getmin(l,r),i,j,k,x=b[mid].x,y=b[mid].y;
	matrix u=solve(l,mid-1,x),v=solve(mid+1,r,x),z;
	for (i=0; i<2; i++)
		for (j=0; j<2; j++){
			z.p[i][j]=1000000000;
			for (k=0; k<=y; k++) z.p[i][j]=min(z.p[i][j],u.p[i][k]+v.p[y-k][j]);
		}
	//cout<>1]+1;
	for (i=1; i<=n; i++){
		scanf("%d",&a[i]); calc(i);
		//cout<

by lych
2017.9.25