Codeforces #740 Div1 : B. Up the Strip

ベストではないが悪くない出来。
https://codeforces.com/contest/1558/problem/B

問題

整数Nが与えられる。
1～NのNマスがある双六を考える。
初期状態でN番のマスにトークンがあり、それを1番に動かすことを考える。

今トークンがX番のマスにあるとき、以下の行動をとれる。

• 1～(X-1)の範囲の整数Yを選び、(X-Y)番のマスにトークンを動かす。
• 2～Xの範囲の整数Yを選び、floor(X/Y)番のマスにトークンを動かす。

移動先のトークンが同じでも、取った行動を異なるときは別々の移動手順とみなす。

N番のマスから1番に動かすのは何通りか。

なおこの問題ではメモリ制限が厳しく、最大128Mバイトしか利用できない。

解法

メモリ容量をO(NlogN)要するデータ構造は、N*logN=80Mエントリ必要な時点で、1エントリ1バイトまでしか利用できず、実質取りえない。
そこで、O(N)で済むデータ構造を考える。

上記行動を逆に考え、1番のマスからより大きい方向に移動することを考える。

dp(n) := 1番のマスから初めて、n番のマスに至る移動順の数

移動順を逆に考えると、以下の遷移を取ることがわかる。

• dp(n+i) (i＞0) にdp(n)を加算する。
• dp(n*m)～dp((n+1)*m-1)の範囲にdp(n)を加算する。

後者はn毎にmをN/nまでループすればよいので、全体でO(NlogN)回程度加算すればよい。
結局区間への加算をO(NlogN)回行いながら、累積和を取りながらdp(n)を小さい順に埋めて行けばよい。

int N;
ll mo;
ll dp[4040404];
ll add[4040404];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	
	dp[1]=1;
	ll sum=0;
	for(i=1;i<=N;i++) {
		(add[i]+=add[i-1])%=mo;
		(dp[i]+=add[i]+sum)%=mo;
		for(j=2;j*i<=N;j++) {
			(add[j*i]+=dp[i])%=mo;
			(add[min(4000001,j*(i+1))]+=mo-dp[i])%=mo;
		}
		(sum+=dp[i])%=mo;
	}
	cout<<dp[N]<<endl;
	
}

まとめ

これ1250ptだけど、1000ptでもよさそう。