Codeforces #166 Div2. A. Beautiful Year、B. Prime Matrix

最近ちょくちょくCodeforcesも出ています。
Div1とDiv2の間をうろちょろして、ギリギリDiv1維持中。
Codeforcesの方がTopCoderより若干レートがいいのは、Pretestの強度が強く実質的に再投稿がしやすいためか。

とはいえこの#166の時はDiv2で参加。
何とか４問解いたのでDiv1に返り咲きました。では順に復習。

http://codeforces.com/contest/271/problem/A
http://codeforces.com/contest/271/problem/B

A. Beautiful Year

４ケタの年号が与えられる。
その年より多く、各桁の数値が異なっている最小の年を答えよ。

2013年は1987年以来の各桁の数値が異なっている年ということで、この問題が出たんでしょう。
回答としては、１ずつ足して条件を満たす数値を探すだけ。
各桁の数値が異なることは、かなり大雑把な方法で探している…。

int N;

int dist(int A) {
	int a1=A/1000;
	int a2=(A/100)%10;
	int a3=(A/10)%10;
	int a4=A%10;
	
	if(a1==a2) return 0;
	if(a1==a3) return 0;
	if(a1==a4) return 0;
	if(a2==a3) return 0;
	if(a2==a4) return 0;
	if(a3==a4) return 0;
	return 1;
}

void solve() {
	N=GETi()+1;
	
	while(dist(N)==0) N++;
	_P("%d\n",N);
	return;
}

B. Prime Matrix

自然数で構成された行列が与えられる。
ここで、コスト１を払うと行列の１要素の数値を１増やすことができる。
この処理を何度か繰り返し、どこかの１列または１行の構成要素が素数だけになるようにするとき、最小コストを答える。

まず、題意通りに行列の各要素に対し、最寄の素数にするためのコストを計算する。
そしてそのコストを列または行で総和を取り、その最小値を求めればよい。

int np;
const int prime_max = 100100;
char p[prime_max];
int dist[prime_max];

void cprime() {
	int i,j;
	
	np=0;
	ZERO(p);
	p[1]=1;
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		for(j=i*2;j<prime_max;j+=i) p[j]=1;
	}
}

int cdist(int V) {
	if(dist[V]>=0) return dist[V];
	if(p[V]==0) return dist[V]=0;
	
	int V3=V;
	while(p[V3]==1) V3++;
	dist[V]=V3-V;
	
	return dist[V];
}

int H,W;
int mat[501][501];
void solve() {
	int f,r,i,j,k,l,x,y;
	
	MINUS(dist);
	
	cprime();
	GET2(&H,&W);
	FOR(y,H) FOR(x,W) {
		mat[y][x]=cdist(GETi());
	}
	
	ll mi=1e9;
	FOR(y,H) {
		ll t=0;
		FOR(x,W) t+=mat[y][x];
		mi=min(mi,t);
	}
	FOR(x,W) {
		ll t=0;
		FOR(y,H) t+=mat[y][x];
		mi=min(mi,t);
	}
	
	_P("%d\n",(int)mi);
	return;
}

まとめ

さすがにDiv2ということでA,Bはラク。