Mujin Programming Challenge 2017 : A - Robot Racing

ダメダメすぎる…。
http://mujin-pc-2017.contest.atcoder.jp/tasks/mujin_pc_2017_a

問題

1次元の数直線の格子点上にN個のロボットが並んでおり、その座標は順にX[i]である。
今、1つのロボットを選び、1または2だけ座標の小さい場所に動かす、という処理を繰り返す。
原点に到達したロボットは数直線から取り除く。
途中、複数のロボットが同じ位置に存在してはならない。

取り除かれるロボットの順番の組み合わせ総数を求めよ。

解法

各ロボットは、最短何番目に取り除かれるかを考えよう。

以下のF(i)、S(x)を定義する。
F(i) := i番目のロボットを取り除くには、その手前最小何個のロボットが取り除かれていればよいか。
S(x) := 手前にいるロボットのうち、x個以下が取り除かれていれば、自身が次に取り除かれることができる、というロボットの数。すなわちF(i)≦xであるiの数。
こうすると、最初はS(0)個のロボットのうちいずれか、次はS(1)個のロボットのうち、最初に取り除いたものを除くいずれか…と取り除かれていくので、が解となる。

あとはF(i)を求められれば良い。
仮に手前のロボットが2つの格子点に連続して配置されていなければ、すべてを飛び越してi番のロボットが最初に原点に到達できる。
そこで、手前のロボットから順に、それぞれ前のロボットの後ろに詰めていくことを考える。
ただし、可能であればぴったり座標が１ずれた位置ではなく、2ずれた位置まで詰めることにする。

逆に、詰めた後でも2連続ロボットが配置されている箇所があったとすると、そこは2個のうちいずれかがどいてくれないとi番のロボットが原点に到達できないのでF(i)が増加する。
ただ、F(i)はロボットの連続している箇所の数jそのものではなく、F(i)=(j+1)/2となる。
これは、連続しているロボットのうち1個を先に原点に到達されることで、後ろにあるロボットを詰めることでもう1つのロボットの連続を解消できるためである。
こうしてF(i)を求めたら、あとはS(x)を求めればよい。

int N;
int X[101010];
int cnt[101010];
ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	int fail=0,prex=0;
	FOR(i,N) {
		cin>>X[i];
		
		cnt[(fail+1)/2]++;
		if(i==0) {
			X[0]=1;
		}
		else{
			
			if(X[i]>=X[i-1]+2) X[i]=X[i-1]+2;
			if(X[i-1]+1==X[i]) fail++;
		}
	}
	
	ll ret=1;
	ll tot=0;
	FOR(i,N) {
		tot += cnt[i];
		(ret *= tot)%=mo;
		tot--;
	}
	cout<<ret<<endl;
	
}

まとめ

わりと苦労してしまった。