AtCoder ARC #033 : A - 隠れた言葉、B - メタ構文変数

ARC033に参加。
yukicoderで覚えたラグランジュ補間が良い具合に適用出来て、そこそこの時間でD回答。
http://arc033.contest.atcoder.jp/tasks/arc033_1
http://arc033.contest.atcoder.jp/tasks/arc033_2

A - 隠れた言葉

異なる文字で構成されるN文字の文字列がある。
部分文字列は何通りあるか。

N*(N+1)/2を答えるだけ。
本番は問題をよく読まずに解いてFirst Acceptでした。

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cout<<N*(N+1)/2<<endl;
}

B - メタ構文変数

Na個の数値の集合と、Nb個の数値の集合がある。
積集合と和集合の要素数の比率を答えよ。

和集合はsetで、積集合は尺取法でカウントした。
でもSTLならset_unionとset_intersectでもあっさり解けるね。

int NA,NB;
ll A[101000],B[101000];
set<ll> S,S2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>NA>>NB;
	FOR(i,NA) cin>>A[i],S.insert(A[i]);
	FOR(i,NB) cin>>B[i],S.insert(B[i]);
	sort(A,A+NA);
	sort(B,B+NB);
	
	int tot=0;
	for(x=0,y=0;x<NA && y<NB;) {
		if(A[x]==B[y]) {
			tot++;
			x++;
			y++;
		}
		else if(A[x]<B[y]) x++;
		else y++;
	}
	
	_P("%.12lf\n",1.0*tot/S.size());
}

まとめ

いつものARCより簡単目。