AtCoder Beginner Contest 167 Solution

前言
せっかくak ABC.でもあと10分しか残ってない、かわいそう.手の速さも普及アルゴリズムの熟練度も向上しなければならないだろう...
本題
A A A
stringの基本的な運用を考察する.(こう書くともっと短い)

int main() {
	string s,t;
	cin>>s>>t;
	for(char c='a';c<='z';c++)
		if(s+c==t) puts("Yes"),exit(0);
	puts("No"); 
	return 0;
}

B B B
入門の欲張り

int a,b,c,k,ans;

int main() {
	qr(a); qr(b); qr(c); qr(k);
	if(k<=a) ans=k;
	else {
		ans=a;
		k-=a;
		if(k>b) ans-=k-b;
	}
	pr2(ans);
	return 0;
}

C C C
暴力d f s dfs dfs.

int n,m,t,ans,c[N],a[N][N],b[N];

void dfs(int x,int s) {
	if(s>=ans) return ;
	if(x>n) {
		for(int i=1;i<=m;i++) if(b[i]<t) return ;
		ans=s; 
		return ;
	}
	dfs(x+1,s);
	for(int i=1;i<=m;i++) b[i]+=a[x][i];
	dfs(x+1,s+c[x]);
	for(int i=1;i<=m;i++) b[i]-=a[x][i];
}

int main() {
	qr(n); qr(m); qr(t);
	for(int i=1;i<=n;i++) {
		qr(c[i]);
		for(int j=1;j<=m;j++) qr(a[i][j]),b[j]+=a[i][j];
	}
	for(int j=1;j<=m;j++) if(b[j]<t) puts("-1"),exit(0);
	ans=1e9; memset(b,0,sizeof b); dfs(1,0); pr2(ans);
	return 0;
}

D D D
私は一度穴をあけられた.最初は1番が必ずリングになると思った打法を打った->WA.
実は本題は循環節を探すことです.リングに入る前に特判すればいい.

int n,a[N],v[N],cnt,f[N];
ll k;

int main() {
	qr(n);qr(k);for(int i=1;i<=n;i++) qr(a[i]);
	int x=1;
	do {
		v[x]=1;
		if(cnt==k) pr2(x),exit(0);
		f[cnt++]=x;
		x=a[x];
	} while(!v[x]);
	k-=cnt; cnt=0;
	do {
		v[x]=2;
		f[cnt++]=x;
		x=a[x];
	} while(!(v[x]&2));
	pr2(f[k%cnt]);
	return 0;
}

E E E
数学の裸の問題を組み合わせて、しかしどうして私は先にFのこのような気持ち悪い問題をすることができます.a n s = ∑ i = 0 k m C n − 1 k ∗ ( m − 1 ) n − 1 − k ans=\sum_{i=0}^k mC_{n−1}^k*(m−1)^{n−1−k}ans=Σi=0 k mCn−1 k∗(m−1)n−1−k理解:mは最初の数のスキームであり、iは同じ隣接数の個数を表し、残りのn−1−k個数のスキームはm−1 mが最初の数のスキームであり、iは同じ隣接数の個数を表し、残りのn−1−k個数のスキームはm−1 mが最初の数のスキームであり、iは同じ隣接数の個数を表し、残りのn−1−k個数のスキームはm−1 mが最初の数のスキームであり、iは同じ隣接数の個数を表し,残りのn−1−k個の数のスキームはm−1である.

int n,m,k;
ll jc[N],inv[N],p[N],ans;

ll power(ll a,ll b=mod-2) {
	ll c=1;
	while(b) {
		if(b&1) c=c*a%mod;
		b /= 2; a=a*a%mod;
	}
	return c;
}

ll C(int x,int y) {return jc[x]*inv[y]%mod*inv[x-y]%mod;}


int main() {
	qr(n); qr(m); qr(k);
	jc[0]=1;for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
	inv[n]=power(jc[n]);for(int i=n;i;i--) inv[i-1]=inv[i]*i%mod;
	p[0]=1;for(int i=1;i<=n;i++) p[i]=p[i-1]*(m-1)%mod;
	
	for(int i=0;i<=k;i++)
		(ans += C(n-1,i)*p[n-1-i]) %= mod;
	pr2(ans*m%mod);
	return 0;
}

F F F
試合中に偽のアルゴリズムを打って返したが、ATデータは真心水だった.
コメントエリアの先輩が私の元のコードの誤りを指摘してくれたことに感謝します.
類似テーマ
この問題は上の問題よりもシミュレーションスタックが多いだけです.

#include
#include
using namespace std;
const int N=1e6+10;

struct rec {
	int x,y;
} a[N],b[N];
int la,lb;

bool cmp1(rec a,rec b) {return a.x<b.x;}
bool cmp2(rec a,rec b) {return a.y>b.y;}

int n,s0,s1,m;
char s[N];

int main() {
	scanf("%d",&n);
	for(int i=1,l,r;i<=n;i++) {
		scanf("%s",s+1); l=r=0;
		for(int j=1;s[j];j++)
			if(s[j]=='(') l++;
			else if(l) l--;
			else r++;
		//-r +l
		if(r<l) a[++la]=(rec){r,l};
		else b[++lb]=(rec){r,l};
		s0+=r; s1+=l;
	}
	if(s0^s1) return puts("No"),0;
	sort(a+1,a+la+1,cmp1);
	sort(b+1,b+lb+1,cmp2);
	for(int i=1;i<=la;i++) {
		if(m<a[i].x) return puts("No"),0;
		m-=a[i].x-a[i].y;
	}
	for(int i=1;i<=lb;i++) {
		if(m<b[i].x) return puts("No"),0;
		m-=b[i].x-b[i].y;
	}
	puts("Yes"); return 0;
}