kmjp's blog

競技プログラミング参加記です

AtCoder ARC #045 : A - スペース高橋君、B - ドキドキデート大作戦高橋君

Cまでは良かった。
http://arc045.contest.atcoder.jp/tasks/arc045_a
http://arc045.contest.atcoder.jp/tasks/arc045_b

A - スペース高橋君

Left,Right,AtCoderの3つの文字列がスペース区切りで与えられるので、'<','>','A'に置換せよ。

色んなやり方があるが、自分はcinで文字列を1個読み込んで対応する文字列を出力した。

void solve() {
	int i,j,k,l,r,x,y; string s;
	int first=0;
	
	while(cin>>s) {
		if(first++) _P(" ");
		if(s=="Left") _P("<");
		if(s=="Right") _P(">");
		if(s=="AtCoder") _P("A");
	}
	_P("\n");
}

B - ドキドキデート大作戦高橋君

N個の教室があり、M人で掃除を行う。
i番目の人の担当箇所は、S[i]~T[i]番の連続した教室である。
1人が掃除を行わなくても全部屋最低1人が掃除を行ってくれるような担当の番号を列挙せよ。

まずimos法の要領で各部屋を何人が掃除対象としているかを求める。
2人以上が掃除対象としている部屋は、1人が掃除を行わなくても誰かが掃除をしてくれる。

各担当について、担当範囲の部屋が上記条件を満たしているなら、その担当は掃除を行わなくても良い。
これはSegTreeで解いても良いし、各部屋「2人以上が掃除対象としている」なら1、そうでないなら0として、その累積和を求めておくと、ある区間内がすべて条件を満たしているかO(1)で求められるのでそれで求めても良い。

int N,M;
int S[303030],T[303030];
int ok[303030];
int ok2[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>S[i]>>T[i];
		ok[S[i]]++;
		ok[T[i]+1]--;
	}
	for(i=1;i<=N;i++) {
		ok[i]+=ok[i-1];
		ok2[i]=ok2[i-1]+(ok[i]>1);
	}
	vector<int> R;
	FOR(i,M) {
		if(ok2[T[i]]-ok2[S[i]-1]==T[i]-(S[i]-1)) R.push_back(i+1);
	}
	_P("%d\n",R.size());
	FORR(r,R) _P("%d\n",r);
}

まとめ

Bがいつもより若干複雑か。