読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Coder-Strike 2014 - Qualification Round

良くわからないコンテストの予選。
Round2は出られないの確定的だけど、予選とRound1まで出る予定。
http://codeforces.com/contest/411

A. Password Check

文字列が与えられるので、以下の条件を全て満たすか答えよ。

  • 5文字以上
  • 数値を含む
  • 小文字を含む
  • 大文字を含む

地道に判定するだけ。

void solve() {
	int f,i,j,k,l,x,y;
	string S;
	int ok=0;
	
	cin>>S;
	if(S.size()>=5) ok |= 1;
	ITR(it,S) {
		if(isdigit(*it)) ok |= 2;
		if('a' <= *it && *it <= 'z') ok |= 4;
		if('A' <= *it && *it <= 'Z') ok |= 8;
	}
	
	if(ok==15) _P("Correct\n");
	else _P("Too weak\n");
}

B. Multi-core Processor

N個のプロセッサがM個の処理を時間順に行う。
プロセッサpは時刻qにメモリX[p][q]をロックする。

同じメモリを2つ以上がロックしようとすると、各プロセッサはデッドロックで以降の動作をやめる。
また、以後そのメモリを触ったプロセッサも同様にそれ以降の動作をやめる。
各プロセッサはいつまで動き続けることができるか。

素直に上記動作を実装するだけ。

int N,M,K;
int X[101][101];
int LP[101],LM[101],TL[101];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M>>K;
	FOR(i,N) FOR(j,M) cin>>X[i][j];
	
	FOR(i,M) {
		ZERO(TL);
		FOR(x,N) if(LP[x]==0 && X[x][i]) TL[X[x][i]]++;
		FOR(x,K+1) if(TL[x]>1) LM[x]++;
		FOR(x,N) if(LP[x]==0 && X[x][i] && LM[X[x][i]]) LP[x]=i+1;
	}
	FOR(i,N) _P("%d\n",LP[i]);
	
}

C. Kicker

2チームそれぞれ2人ずつ選手がおり、各人の攻撃力と守備力が与えられる。
両チームそれぞれどちらかの選手を攻撃担当、もう一人を守備担当とできる。
チームの勝利条件は自チームの攻撃担当の攻撃力が相手の守備担当の守備力より高く、かつ自チームの守備担当の守備力が相手の攻撃担当の攻撃力より高いことである。

チーム1が先に攻撃担当・守備担当を定め、その後チーム2が担当を決めるとする。
両チームが最適手を取ると勝利するチームはどちらか。


選手の選び方は4通りしかないので、各ケースの勝ち負けを先に求めておく。
先にチーム1の選択により4通りを2通りに絞ることができ、その後チーム2が2通りから1通りに絞ることになる。
よってチーム2がどちらを選んでもチーム1がより有利となるよう、チーム1が最初の絞り込みを行えばよい。
Min-max法そのまんまだね。

int A[4],B[4];
int W[4];

void solve() {
	int f,i,j,k,l,x,y;
	
	FOR(i,4) cin>>A[i]>>B[i];
	
	if((B[0]>A[3])+(A[1]>B[2])==2) W[0]=1;
	if((B[0]<A[3])+(A[1]<B[2])==2) W[0]=-1;
	if((B[0]>A[2])+(A[1]>B[3])==2) W[1]=1;
	if((B[0]<A[2])+(A[1]<B[3])==2) W[1]=-1;
	if((B[1]>A[3])+(A[0]>B[2])==2) W[2]=1;
	if((B[1]<A[3])+(A[0]<B[2])==2) W[2]=-1;
	if((B[1]>A[2])+(A[0]>B[3])==2) W[3]=1;
	if((B[1]<A[2])+(A[0]<B[3])==2) W[3]=-1;
	
	x = max(min(W[0],W[1]),min(W[2],W[3]));
	if(x==1) _P("Team 1\n");
	if(x==-1) _P("Team 2\n");
	if(x==0) _P("Draw\n");
	
	
}

まとめ

Google Code Jamよりは簡単。

広告を非表示にする