Google Code Jam 2013 Round 2 : A. Ticket Swapping

今年もTシャツ+Round3進出をめざしGCJ R2に参加。
残念ながらA-Largeでlong long型のオーバーフローやらかしてA-Largeを落としてしまった。
B-Largeを当てたものの４年ぶりのRound2敗退。Tシャツはゲットできたけど残念…。
Bを解けたのは成長を実感したんだけどなぁ。
Cは元々必要なテクを知らなかったので、現時点で解けないのはしょうがない。

ではAから復習。
https://code.google.com/codejam/contest/2442487/dashboard#s=p0

問題

0～(N-1)までのN個の駅が一直線に並んでいる。
ここに何人もの人が乗る。ただし乗るのは駅の番号が増える方向のみ。

ここで、運賃は以下の様に決まる。

• 乗客は乗車時にその駅のカードを取る。
• 降りるときにカードと合わせて運賃を支払う。
• 乗車した駅から、最初の１駅は運賃N、次の１駅は(N-1)、次は(N-2)…と１駅の運賃は1ずつ低下していく。乗車駅のカードから降りる駅まで運賃を足したものがその乗客の運賃

ここで、一部重複する区間を利用する乗客同士がカードを交換する場合、乗客から得られる総運賃が減少する可能性がある。

駅の数Nと、ある駅の区間と、その乗降者数の配列が与えられる。
総運賃の減少量の最大値のmod 1000002013を取った値を求めよ。

解法

乗車駅から遠くなるほど１駅の運賃は下がる。
よって、問題文中にある例からもわかるように、乗客はできるだけ降車駅より遠いカードを手に入れると、総運賃は下がる。
乗車駅が近いカードは１駅の運賃が高いため、降車駅が近い人と交換してさっさと使い切るのが良い。

これらから、以下の戦略が取れる。

• 駅の区間と乗降者数の配列を、降車駅番号の順にソートする
• 各駅の区間(O,E)と乗降者数Pのペアについて、それと重複する区間のうち乗車駅がEに近いところのチケットを使って運賃を支払う。チケットが足りなければ、次に乗車駅がEに近いところのチケットを順々に使う。

この手法では、区間と乗降者数配列の要素数Mに対しO(M^2)で処理できる。

ll N,M;
ll O[1001],E[1001],P[1001];
pair<pair<ll,ll>,ll> hoge[1001];
vector<pair<ll,int> > EV;

ll cost(ll s,ll e) {
	return ((e-s)*(e-s-1)/2)%1000002013;
}

void solve(int _loop) {
	int i,j,x,y,z,ne=0;
	
	EV.clear();
	
	cin >> N>>M;
	ll tot=0;
	FOR(i,M) {
		cin>>O[i]>>E[i]>>P[i];
		hoge[i].first.first=O[i];
		hoge[i].first.second=E[i];
		hoge[i].second=P[i];
		tot = (tot+P[i]*cost(O[i],E[i]))%1000002013;
	}
	sort(hoge,hoge+M);
	FOR(i,M) {
		P[i]=hoge[i].second;
		EV.push_back(make_pair(hoge[i].first.second,i));
	}
	
	sort(EV.begin(),EV.end());
	ll tt2=0;
	ITR(eit,EV) {
		ll rr=hoge[eit->second].second;
		
		for(y=M-1;y>=0;y--) {
			if(rr==0) break;
			if(hoge[y].first.first > eit->first) continue;
			ll red=min(rr,P[y]);
			tt2=(tt2+red*cost(hoge[y].first.first,eit->first))%1000002013;
			rr-=red;
			P[y]-=red;
		}
	}
	
	
	_PE("Case #%d: %lld\n",_loop,(((tt2-tot)%1000002013)+1000002013)%1000002013);
}

まとめ

本番、mod 1000002013を入れずにLargeを一旦submit。
答えに負の値があることに気づいて、急遽modの条件を知り、慌てて挿入。
しかしred*costの処理が最大10^9*10^9*10^9位の値になるのにmodを入れ忘れ、そこでlong longをオーバーフロー。
うーん、アプローチもあっていたのにこれは勿体ない。

正直、この問題に余り関係ないパラメータなのにNやPの値大きすぎだよな…。