UTPC 2014 : E - 宝くじ

当たった上限は3000円だなぁ。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_e

問題

宝くじの当たりがN通りある。
各当たりでは、宝くじの番号の下何けたかがA[i]と一致するとき、B[i]円を得られる。
各1～i番の宝くじの当たりの情報に対し、1枚の宝くじで得られる最大の賞金を答えよ。

解法

Writer回ではTrieを辿って最大値を求めていくものだそうだ。
自分は別解法で解いた。

A[i]の桁がそろうよう、A[i]のそれぞれに頭に"X"を付与した状態を考える。
A[i]は最大10桁なので、仮にすべて10桁にそろえる。

例えばテストケース１のA[1]="10"はA[1]="XXXXXXXX10"とする。
この文字列を前後反転すると"01XXXXXXXX"となる。
ここから、"0100000000" ≦ x ≦ "0199999999"となる番号xはB[1]円得られることがわかる。

ここまでわかれば、SegTreeを使って各A[i]に対応する範囲にB[i]を足し、その最大値を取得していけば良いことがわかる。
ただ、10^10もの配列を持つSegTreeはメモリに収まらないので先に座標圧縮するとよい。

template<class V,int NV> class SegTree_3 {
public:
	vector<V> val,ma;
	SegTree_3(){val.resize(NV*2,0); ma.resize(NV*2,0);};
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};

int N;
ll A[101000],B[101000],W[101000];
map<ll,int> M;
ll ma;
SegTree_3<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s,t;
	
	cin>>N;
	M[-1]=M[10000000000LL]=0;
	FOR(i,N) {
		cin>>s>>W[i];
		reverse(s.begin(),s.end());
		t=s+"99999999999";
		s=s+"00000000000";
		s=s.substr(0,10);
		t=t.substr(0,10);
		A[i]=atoll(s.c_str());
		B[i]=atoll(t.c_str())+1;
		M[A[i]]=M[B[i]]=0;
	}
	x=0;
	ITR(it,M) it->second=x++;
	FOR(i,N) {
		A[i]=M[A[i]];
		B[i]=M[B[i]];
		st.update(A[i],B[i],W[i]);
		cout<<st.ma[1]<<endl;
	}
}

まとめ

Trie解法もいいけど、SegTree解も結構好き。