Codeforces #170 Div2. A. Circle Line, B. New Problem

CF#170はDiv1で参加。残念ながら１問しか解けず…。
まずはDiv2から復習。
http://codeforces.com/contest/278/problem/A
http://codeforces.com/contest/278/problem/B

A. Circle Line

円周上に駅が並んでおり、駅同士の距離が与えられる。
スタートとゴールの駅が与えられたとき、移動距離を答える。
順回りと逆回りのうち小さい方の距離を取ればよい。

int N;
int D[101];

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	
	j=0;
	N=GETi();
	FOR(i,N) j+=(D[i]=GETi());
	
	x=GETi()-1;
	y=GETi()-1;
	if(x>y) swap(x,y);
	
	k=0;
	for(;x<y;x++) k+=D[x];
	_P("%d\n",min(k,j-k));
	
	return;
}

B. New Problem

最大でL文字(<=20)の文字列がN個(<=30)与えられる。
これらの文字列に含まれない辞書順最小の文字列を答える。

単純に文字列を１文字ずつ生成して、元の文字列群に含まれないか答える。
部分文字列の種類はO(N*L^2)だけど、LもNも小さいので計算量はさほど心配しなくても終わる。

int N;
char S[40][30];
string SS[40];
set<string> SSS;

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	FOR(i,N) GETs(S[i]);
	FOR(i,N) {
		l=strlen(S[i]);
		for(j=1;j<=l;j++) {
			for(x=0;x<=l-j;x++) SSS.insert(string(S[i]+x,j));
		}
	}
	
	string s = "a";
	while(SSS.find(s)!=SSS.end()) {
		int l=s.size();
		int nz=0,i;
		FOR(i,l) if(s[i]=='z') nz++;
		if(nz==l) {
			char hoge[]="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
			hoge[l+1]=0;
			s=string(hoge);
		}
		else {
			i=l-1;
			while(1) {
				if(s[i]=='z') {
					s[i]='a';
					i--;
				}
				else {
					s[i]++;
					break;
				}
			}
		}
	}
	
	cout << s << endl;
	return;
}

まとめ

まだここらへんは簡単だね。