AtCoder ARC #036 : A - ぐっすり、B - 山のデータ

ARC#036に参加。
Dがグダグダで微妙な順位。A,BはFirst Accept取れました。
http://arc036.contest.atcoder.jp/tasks/arc036_a
http://arc036.contest.atcoder.jp/tasks/arc036_b

A - ぐっすり

N日間の睡眠時間T[i]が与えられる。
連続する３日の合計睡眠時間がK未満だと、３日目は睡眠不足となる。
睡眠不足となる日数を求めよ。

T[i-2]+T[i-1]+T[i]＜Kなら睡眠不足が1回発生するので、それを求めていく。

int N,K;
int T[101000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>T[i];
	for(i=2;i<N;i++) {
		if(T[i]+T[i-1]+T[i-2]<K) return _P("%d\n",i+1);
	}
	_P("-1\n");
}

B - 山のデータ

西から東に向けて順にN箇所で測定した高さはH[i]である。
整数組(s,t,u)が山であるとは、H[s..t]が真に単調増加でH[t..u]が真に単調減少であることを示す。
この時、山の大きさはu-s+1とする。
最大の山の大きさを求めよ。

左右から連続した単調増加数を求める方法と、1回だけDPを行う方法がある。自分は後者。
i番目の地点が、直前に連続何個増加しているかをL[i]、連続何個減少しているかをR[i]とする。
L[i],R[i]は以下のように計算できる。

• H[i-1]＜H[i]ならL[i]=L[i-1]+1、そうでないならL[i]=1
• H[i-1]＞H[i]ならR[i]=R[i-1]+1、そうでないならR[i]=L[i] (ここから減少を始めると考える)

あとはR[i]の最大値を求めればよい。

まとめ

ここまでは順調でした…。