KUPC2016 : I - ティッシュ配り / Handing out leaflets

こっからは本番まともに時間もかけられていない。
http://kupc2016.contest.atcoder.jp/tasks/kupc2016_i

問題

1世代目のEliさんはN秒かけてできるだけ多くのティッシュを配りたい。
Eliさんが取れる行動は以下のいずれかである。(Eliさんが複数いる場合、それぞれ異なる行動をとってもよい)

• 1秒かけて1つティッシュを配る。
• i世代目の場合、i*Cの時間をかけて(i+1)世代目のEliさんを追加生成する。

(N,C)の対がクエリとして与えられる。
それぞれ最適な行動をとると最大何個ティッシュを配れるか求めよ。

解法

C=1と固定し、以下を考える。
f(i, n) := i世代目のEliさんが残りn秒で配れる最大ティッシュ数。
g(i, n) := i世代目のEliさんが残りn秒で配れる最大ティッシュ数を再現するとき、最終的なEliさんの人数。
この時f(1,N)が求めたい答えである。

世代数の最大値はO(√N/C)なので、C=1と固定するとfはO(N×√N)通り程度考えればよく、fをDPで列挙することは可能である。
問題は、この問題はクエリが複数あり、Cが1固定ではないことである。

ただ、Cが大きいときは、全体の時間を1/Cに圧縮して考えると、1秒でC個ティッシュが配れると考えてf(1,N/C)*Cとおける。
ただ単純にNをCで割るとN%Cの分時間が余るので、その分はg(1,N/C)*(N%C)を加算しよう。

int Q,N,C;
ll mo=1000000007;

int from[101010];
int to[101010];
int from2[101010];
int to2[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>Q;
	
	for(i=450;i>=1;i--) {
		if(100000-i*(i-1)/2<0) continue;
		for(x=0;x<=100000-i*(i-1)/2;x++) {
			if(x>2*(x-i)) {
				to[x]=x;
				to2[x]=1;
			}
			else {
				to[x]=to[x-i]+from[x-i];
				to2[x]=to2[x-i]+from2[x-i];
				if(to[x]>=mo) to[x]-=mo;
				if(to2[x]>=mo) to2[x]-=mo;
			}
		}
		swap(from,to);
		swap(from2,to2);
	}
	
	while(Q--) {
		cin>>N>>C;
		cout<<(1LL*from[N/C]*C+1LL*from2[N/C]*(N%C))%mo<<endl;
	}
	
}

まとめ

C=1の時の値をC=1でないときにも用いるってのがさっと出てこなかった。