TopCoder SRM 832 : Div1 Easy Div2 Hard CastleGuard

うーん、3完したい問題セットだった。
https://community.topcoder.com/stat?c=problem_statement&pm=17667

問題

0～(N-1)番のN個のマスが時計回りで円周状に並んでいる。
ここでコマンド列と、コマンド列の繰り返し回数Rが与えられる。

初期状態でコマを0番のマスに置く。
各コマンドは正または負の数で表現される。
正の数ならその数だけコマを時計回りに移動させ、負の数ならその絶対値の数だけコマを時計回りに移動させる。
このコマンド列全体を、R回繰り返す。
コマが各マスに到達する回数を求めよ。

まずコマンド列1周分を処理しよう。
もし1つのコマンドの絶対値がN以上だと、同じマスを複数回通ることになるので、それらは一括してカウントすることで、1コマンドあたりO(N)で各マスの経由回数をカウントしよう。

次にこれをR回繰り返すわけだが、1回コマンド列を実行し終わると、コマの位置が少しずれることがある。
そこで、R回の繰り返しのうち、それぞれどこのマスでコマンド列を開始するかをカウントしよう。これはO(R)かけても良いしO(N)かけても良い。
あとは各マスでコマンド列を開始した場合の、各マスの到達回数をまとめて計上すればO(N^2)で数え上げることができる。

ll C[101010];
ll D[505];
class CastleGuard {
	public:
	vector<long long> walk(int N, int R, vector <int> commands) {
		ZERO(C);
		ZERO(D);
		int cur=0;
		int i,j;
		FORR(c,commands) {
			ll a=abs(c)/N;
			ll b=abs(c)%N;
			FOR(i,N) C[i]+=a;
			FOR(i,b) {
				if(c<0) {
					cur=(cur+N-1)%N;
				}
				else {
					cur=(cur+1)%N;
				}
				C[cur]++;
			}
		}
		int d=0;
		
		FOR(i,R) {
			D[d]++;
			(d+=cur)%=N;
		}
		
		vector<ll> ret(N);
		FOR(i,N) {
			FOR(j,N) ret[(i+j)%N]+=1LL*D[i]*C[j];
		}
		ret[0]++;
		
		return ret;
	}
}

まとめ

O(R)が通らないぐらいRを大きくしても良いのにね。