天下一プログラマーコンテスト2015 予選B : A - 天下一プログラマーコンテスト1998、B - 天下一リテラル

なんとかTシャツゲット。Dの部分点を早解きしただけともいう。
http://tenka1-2015-qualb.contest.atcoder.jp/tasks/tenka1_2015_qualB_a
http://tenka1-2015-qualb.contest.atcoder.jp/tasks/tenka1_2015_qualB_b

A - 天下一プログラマーコンテスト1998

• A[0] = 100
• A[1] = 100
• A[2] = 200
• A[x] = A[x-1]+A[x-2]+A[x-3] (x≧3)

とする。A[19]を求めよ。

愚直に計算するだけ。
元問題文だと下から20人目の値を求めよとあるが、つられてA[20]を答えないよう注意。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int A[1000];
	A[0]=100;
	A[1]=100;
	A[2]=200;
	for(i=3;i<=20;i++) A[i]=A[i-1]+A[i-2]+A[i-3];
	cout<<A[19]<<endl;
}

B - 天下一リテラル

以下のように定義される構文がある。
文字列が与えられるので、それがDICTかSETかを求めよ。

DICT = "{" , EXPR , ":" , EXPR , { "," , EXPR , ":" , EXPR } , "}" | "{}" ;
SET  = "{" , EXPR , { "," , EXPR } , "}" ;
EXPR = DICT | SET | INTEGER ;

左括弧の後のEXPRの後、コロンが来るか右かっこまたはカンマが来るかでDICTかSETか判定できる。
あとは愚直に構文解析するだけ。
左括弧の直後に右括弧が来る場合はDICTになるので注意。

まじめに全部構文解析せずとも、括弧の深さ1でコロンの有無をチェックするだけという方法もあるようだ。

string S;
int cur;

int dfs() {
	
	if(S[cur]!='{') {
		while(S[cur]>='0' && S[cur]<='9') cur++;
		return 2;
	}
	cur++;
	if(S[cur]=='}') return cur++,0; //dict
	
	dfs();
	if(S[cur]==':') { //dict
		cur++;
		dfs();
		while(S[cur]!='}') cur++, dfs(), cur++, dfs();
		cur++;
		return 0;
	}
	else { //set
		while(S[cur]!='}') cur++, dfs();
		cur++;
		return 1;
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>S;
	
	if(dfs()==0) cout<<"dict"<<endl;
	else cout<<"set"<<endl;
}

まとめ

Bは面倒なだけで面白さは感じないなぁ。