yukicoder : No.449 ゆきこーだーの雨と雪 (4)

終わってみるとあっさりなのだが妙に手間取った。
http://yukicoder.me/problems/no/449

問題

N種類の問題があり、i番の問題の難易度はL[i]である。
ある問題を解いたのが先頭からx人目の場合、その人は問題の難易度をdとして50*d + floor*1のスコアを得る。

ここでT個のクエリが与えられる。
各クエリは、人名とその人が解いた問題番号、または問い合わせからなる。
クエリの入力順に与えられた人がその問題を解いていくとする。
問い合わせクエリに対し、その人のその時点の順位を答えよ。

順位は各人の得た総スコアの高い順である。
点数がタイの人が複数いる場合、最後にスコアを得たタイミングが早いほうが順位が高いものとする。

解法

各クエリで問題を解いたとき、その人の(総スコア, 時刻)を考えると、状態は高々(T+1)個(+1は初期状態)しかないことがわかる。
よって一度クエリを順に実行して登場する(総スコア, 時刻)を列挙しておこう。
あとは(総スコア, 時刻)を座標圧縮すれば、BITで自分より(総スコア, 時刻)がよい人の数を高速に数えられる。

int N;
int L[30];
int T;
string S[101010];
int ID[101010],Q[101010];
unordered_map<string,int> U;
ll sc[101010];
int cn[101010];

vector<pair<ll,int>> V;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;
int num[30];

int score(int A) {
	int B=++num[A];
	return (L[A]*50+(50*L[A])*10/(8+2*B));
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i];
	cin>>T;
	FOR(i,T) {
		cin>>S[i]>>s;
		if(s[0]=='?') Q[i]=-1;
		else Q[i]=s[0]-'A';
		
		if(U.count(S[i])==0) U[S[i]]=U.size()-1;
		ID[i]=U[S[i]];
		
		if(Q[i]>=0) {
			sc[ID[i]]+=score(Q[i]);
			V.push_back({sc[ID[i]],-i});
		}
	}
	
	V.push_back({0,0});
	sort(ALL(V));
	
	ZERO(num);
	ZERO(sc);
	bt.add(0,U.size());
	
	FOR(i,T) {
		if(Q[i]>=0) {
			bt.add(cn[ID[i]],-1);
			sc[ID[i]]+=score(Q[i]);
			cn[ID[i]]=lower_bound(ALL(V),make_pair(sc[ID[i]],-i))-V.begin();
			bt.add(cn[ID[i]],1);
		}
		else {
			cout << bt(1<<19)-bt(cn[ID[i]])+1<<endl;
		}
	}
}

まとめ

考え方はシンプルだけど妙に手間取った。なんか今週前半のCSA, CFといい頭が働いていない。

*1:50*d)/(0.8+0.2*x