Hatena::Grouptopcoder

hoshi524の日記

2012-04-16

SRM 540 DIV 1

18:24

250pt ImportantSequence

問題

TopCoder Statistics - Problem Statement

考えたこと

正直さっぱりわからなかった。

同様の問題がでても解ける気があまりしないけど、とりあえず解法がなんとなく分かったので書き残す。

最初の数を決めると、あとの数は一意に決まるため全部試すことは簡単だけど数が多くて駄目。

加減しかつかってないため、成立する最初の数が連続になるため、その範囲を求めることで成立するケースの数が求まる。

最初の条件は、例えば

a+b=3 (b>=1)

から、a>=2であることが簡単に分かるが、以降の条件は前の条件を加味していく必要がある。

そこで、例えば入力が

{2,4,3}
"-++"

の時

a-b=2 (b>=1)
b+c=4 (c>=1)
c+d=3 (d>=1)

となり、これを整理すると

a      - (a-2)  = 2 ((a-2) >=1)
(a-2)  + (-a+6) = 4 ((-a+6)>=1)
(-a+6) + (a-3)  = 3 ((a-3) >=1)

となり、条件から

(a-2)  >=1 → a>=3
(-a+6) >=1 → a<=5
(a-3)  >=1 → a>=4

であることが分かり、a=最初の数の範囲が分かる

コード


public class ImportantSequence {
	public int getCount(int[] B, String operators) {
		boolean k=true;
		long b=0,left=1,right=Long.MAX_VALUE,n=B.length;
		for(int i=0;i<n;i++){
			if(operators.charAt(i)=='+'){
				k=!k;
				b=B[i]-b;
			}else{
				b=b-B[i];
			}
			if(k){
				left=Math.max(left, 1-b);
			}else{
				right=Math.min(right, b-1);
			}
		}
		if(left<=right){
			if(right==Long.MAX_VALUE)
				return -1;
			else
				return (int)(right-left+1);
		}else
			return 0;
	}
}