Hatena::Grouptopcoder

kuuso1の日記

2017-01-24

AtCoder Grand Contest 009 C - Division into Two

| 02:16 | AtCoder Grand Contest 009 C - Division into Two - kuuso1の日記 を含むブックマーク はてなブックマーク - AtCoder Grand Contest 009 C - Division into Two - kuuso1の日記

http://agc009.contest.atcoder.jp/tasks/agc009_c

  • 相異なるN 個 整数からなる上昇列 {S_i} と,整数 A, B が与えられる.
  • {S_i} を2つの集合 X,Y に分けることを考える.この時

  Xの任意の相異なる2点は絶対値の差がA 以上

  Yの任意の相異なる2点は絶対値の差がB 以上 を満たさなければならない.

  • このような分け方の個数を求めよ ( mod 1000000007 )

(制約)1 ≤ N ≤ 100000,1 ≤ A,B ≤ 10^18, 0 ≤ S_i ≤ 10^18,

・S_iを,S_(i-1)までに作ることができている組み合わせ{(X,Y)}のXに入れるかYに入れるかを順次考える.

・各組み合わせにおいて,Xの最大値とYの最大値を代表値として覚えておけば,そこに次のS_iを追加できるかはその値で判定できる.

・(Xmax,Ymax)の組み合わせは(N+1)^2あるように見えるが,S_iを追加したときには Xmax=S_iとなるか Ymax=S_iとなっているので,実際に各iのタイミングでは相手のMaxだけを覚えておけばよいので,X側とY側で高々 N+1 個覚えておけばよい.

・この2つをdpで更新していく.素直には下の図のような更新になる.

f:id:kuuso1:20170125020210p:image

・この更新はO(N)なので,トータルO(N^2)となり制約の条件ではTLEしてしまう.

・推移をよく見ると以下の2点にきづく.

 1)横方向の推移(X/Yから続けてX/Yに割り振る)はS_jとS_(j+1)の差がA/Bを超えるか否かで決まり,推移できるならそのまま,推移できないならその先はずっと0である

 2)X/YからY/Xに乗り移る推移は,S_(j+1)よりB/Aだけ小さい最大値を持つものすべてが移ることができる.

・これらから,累積和と,どこまで0でクリアされてしまったかを考慮することで,各推移をO(1)で行うことができ,全体でO(N)で計算できる.

class Sol{
	public void Solve(){
		
		if(N == 1){
			Console.WriteLine(2);
			return;
		}
		
		long mod = (long)1e9 + 7;
		
		long[] dpA = new long[N+1];
		long[] dpB = new long[N+1];
		long[] sumA = new long[N+2];
		long[] sumB = new long[N+2];
		
		dpA[0] = 1;
		sumA[1] = 1;
		dpB[0] = 1;
		sumB[1] = 1;
		
		int clA = 0;// [0,clA) を0にするフラグ (S[clA-1] ≦ S[clA] - A が成り立たない)
		int clB = 0;
		
		int okA = 0;// [0,okA) を足す事が出来る(S[i]-A ≧ S[okA] となる最大のインデックス + 1
		int okB = 0;
		
		for(int i=1;i<N;i++){
			while(S[okA] <= S[i+1] - A && okA < i) okA++;
			while(S[okB] <= S[i+1] - B && okB < i) okB++;
			
			// dpB[*]は [0,okA) からdpA[i] に配れるが,[0,clB)は 0 になっている
			// → 実際に行けるのは [clB,okA)  
			if(okA >= clB) dpA[i] = sumB[okA] - sumB[clB] + mod; if(dpA[i] >= mod) dpA[i] -= mod;
			if(okB >= clA) dpB[i] = sumA[okB] - sumA[clA] + mod; if(dpB[i] >= mod) dpB[i] -= mod;
			
			// dpA[*] [0,i) は S[i+1] >= S[i] + A なら そのまま dpA[*] に残る
			// → そうでないなら dpA[*] [0,i)は すべて 0 になる 
			if(S[i+1] - A < S[i]) clA = i;
			if(S[i+1] - B < S[i]) clB = i;
			
			sumA[i+1] = sumA[i] + dpA[i]; if(sumA[i+1] >= mod) sumA[i+1] -= mod;
			sumB[i+1] = sumB[i] + dpB[i]; if(sumB[i+1] >= mod) sumB[i+1] -= mod;
		}
		
		long ans = sumA[N] + sumB[N] +(-sumA[clA] + mod) + (-sumB[clB] + mod);
		ans %= mod;
		
		Console.WriteLine(ans);
		
	}
	int N;
	long A,B;
	long[] S;
	public Sol(){
		var d = rla();
		N = (int) d[0]; A = d[1]; B = d[2];
		S = new long[N+1];
		S[0] = -(long)3e18;	// -INF を追加しておく
		for(int i=0;i<N;i++) S[i+1] = rl();
	}

	static long rl(){return long.Parse(Console.ReadLine());}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
}

・本番は0でクリアするのと累積和の部分を遅延セグ木でやろうとしてバグった.

・配点1100点だったので,よく考えれば解けたのは嬉しい.