Croc Champ 2013 - Qualification Round : C. Network Mask, D. Parallel Programming

さてCとD。この予選ラウンドは普段のCF Div2相当かな。
まだそこまで難しくない。
http://codeforces.com/contest/291/problem/C
http://codeforces.com/contest/291/problem/D

C. Network Mask

いくつかのIPv4のアドレスと、数Kが与えられる。
これらのIPアドレスをK個に分けるようなnetmaskを答える。

これは実際に32通りのnetmaskを順に作って試してみればよい。

int K,N;
vector<ll> addr;

void solve() {
	int f,r,i,j,k,l,x,y;
	ll ip[4];
	GET2(&N,&K);
	FOR(i,N) {
		scanf("%lld.%lld.%lld.%lld",ip,ip+1,ip+2,ip+3);
		addr.push_back((ip[0]<<24) | (ip[1]<<16) | (ip[2]<<8) | ip[3]);
	}
	sort(addr.begin(),addr.end());
	
	for(i=1;i<=32;i++) {
		ll mask=((-1LL) << (32-i)) & 0xFFFFFFFFLL;
		ll pre=1LL<<40;
		x=0;
		
		FOR(j,N) {
			if((addr[j]&mask) != pre) {
				pre = addr[j]&mask;
				x++;
			}
		}
		if(x==K) {
			_P("%lld.%lld.%lld.%lld\n",(mask>>24),(mask>>16)&255,(mask>>8)&255,mask&255);
			return;
		}
	}
	
	_P("-1\n");
	return;
}

D. Parallel Programming

N個のメモリ領域があり、初期値は1～(N-1)番目は1、N番目は0が入っている。
そこにN個のCPUがあり、１回並列処理を行うと、A番目のCPUは1～N番のいずれかのメモリの内容をA番に加算する。
K回並列計算を行ったとき、メモリの内容が(N-1),(N-2),...2,1,0となるようにするCPUのメモリ領域の選び方を答える。

各ステップで1,2,4,8...と倍々の数字を作ることができるので、各要素はi回目の処理ではそのメモリが最終的に格納する数字に1<<(i-1)のビットが立っているなら、1<<(i-1)が入っているメモリを足しこめばよい。

int N,K;
int A[21][10001];

void solve() {
	int f,r,i,j,k,l,x,y;
	int ma=0;
	
	GET2(&N,&K);
	FOR(i,N) A[0][i]=1;
	A[0][N-1]=0;
	
	FOR(i,K) {
		FOR(x,N-1) {
			r=N-2-x;
			if(r & (1<<i)) {
				_P("%d ",N-(1<<i));
				A[i+1][x]=A[i][x]+A[i][N-1-(1<<i)];
			}
			else {
				_P("%d ",N);
				A[i+1][x]=A[i][x];
			}
		}
		_P("%d\n",N);
		A[i+1][N-1]=A[i][N-1];
	}
	
	return;
}

まとめ

この２問は１発正解できた。
Dは面白いアイデアの問題でいいな。