AtCoder ARC #028 : A - 小石を取るゲーム、B - 特別賞

ARC028に参加。Aで凡ミスしたもののB,Cは普通に解き、Dはいつも通り部分点で終了。
最近D解けてないな…。
http://arc028.contest.atcoder.jp/tasks/arc028_1
http://arc028.contest.atcoder.jp/tasks/arc028_2

A - 小石を取るゲーム

N個の小石が袋に入っている。
AntさんがA個、BugさんがB個ずつ小石を袋から取り除く時、袋を空にするのはどちらの手番か。
単純に繰り返すだけ。

void solve() {
	int i,j,k,l,r,x,y; string s;
	int N,A,B;
	
	cin>>N>>A>>B;
	while(N>0) {
		N-=A;
		if(N<=0) return _P("Ant\n");
		N-=B;
		if(N<=0) return _P("Bug\n");
	}
}

B - 特別賞

問題文は意訳。
1～NのPermutationとなっている数列X[i]が与えられる。
i>=(K-1)な各iにおいて、X[0]～X[i]のうちK番目に小さな値を答えよ。

想定解はpriority_queueだが、自分はlower_bound付BITでK番目の番号を求めてしまった。

int N,K,X[100020],R[1000020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	int lower_bound(V val) {
		V tv=0;int i,ent=0;
		FOR(i,ME) if(tv+bit[ent+(1<<(ME-1-i))-1]<val) tv+=bit[ent+(1<<(ME-1-i))-1], ent += (1<<(ME-1-i));
		return ent;
	}
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<int,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>X[i],R[X[i]]=i+1;
	FOR(i,N) {
		bt.update(X[i],1);
		if(i>=K-1) cout << R[bt.lower_bound(K)] << endl;
	}
	
}

まとめ

まぁARCとはいえBでBITの探索なんてないよなぁ…。