日立製作所 社会システム事業部 プログラミングコンテスト2020 : D - Manga Market

こちらは思いついてしまえば簡単。
https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_d

問題

N個の店があり、それぞれパラメータA[i],B[i]がある。
今、自宅から店を回って買い物をする。
自宅と任意の店、および店の間の移動は時間が1かかる。
また、各店の到達時刻がtの時、買い物を終えるまでA[i]*t+B[i]かかる。

任意の順で店を回れる場合、時間T以内最大いくつの店で買い物ができるか。

解法

定番テクとして、2つの店のうちどちらを先に回るとよいか、比較関数を作り、訪問順をソートしよう。
xとyの2つの店を、時刻tから回り始める場合、

• 先にxにいくと(((t+1)*(A[x]+1+B[x])+1)(A[y]+1)+B[y]
• 先にyにいくと(((t+1)*(A[y]+1+B[y])+1)(A[x]+1)+B[x]

となるのでこの大小を取ればよい。

そうすると、A[i]=0の店は後に回した方がよい方がわかる。
まず、A[i]＞0の店を考えよう。
この際、今までいくつ店を回った状態にいたる最小時間を求めることになるが、A[i]＞0の場合、店を1つ回るごとに倍以上の時間がかかるので高々O(logT)個までしか店を回れない。
なのでO(NlogT)かかるDPを行えばよい。

最後に残った時間で、A[i]=0の店をB[i]の小さい順に回れるだけ回ろう。

int N;
ll T;
vector<pair<ll,ll>> A;
vector<ll> B;

ll dp[202020];

bool comp(pair<ll,ll>& L,pair<ll,ll>& R) {
	return (R.first+1)*(L.second+1)+R.second<(L.first+1)*(R.second+1)+L.second;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) {
		cin>>x>>y;
		if(x>0) A.push_back({x,y});
		else B.push_back(y);
	}
	
	FOR(i,N+1) dp[i]=1LL<<60;
	dp[0]=0;
	
	sort(ALL(A),comp);
	FORR(v,A) {
		ll a=v.first;
		ll b=v.second;
		for(i=40;i>=0;i--) if(dp[i]<T) {
			ll nex=(dp[i]+1)+(dp[i]+1)*a+b;
			dp[i+1]=min(dp[i+1],nex);
		}
	}
	
	sort(ALL(B));

	vector<ll> sum;
	sum.push_back(0);
	FORR(b,B) sum.push_back(sum.back()+1+b);
	int ma=0;
	for(i=N;i>=0;i--) if(dp[i]<=T) {
		ma=max(ma,i);
		x=lower_bound(ALL(sum),T-dp[i]+1)-sum.begin()-1;
		ma=max(ma,i+x);
	}
	cout<<ma<<endl;
}

まとめ

最初比較関数に行かず、A[i]降順でやってしまいタイムロス+WAを重ねたのが痛い。