dwangoプログラミングコンテスト予選 2016 : B - 積み鉛筆

ちょっと解く速度が遅いけど、今の自分に解ける問題は解ききったのでこんなもんか…。
http://dwango2016-prelims.contest.atcoder.jp/tasks/dwango2016qual_b

問題

N要素の整数列L[0...(N-1)]に対し、R[i]=max(L[i],L[i+1])で構成される(N-1)要素の整数列R[0...(N-2)]を考える。
Rが与えられたとき、考えられるLの例を構築せよ。

解法

Rの最大値は端にあるか、途中２つ以上連続している。
その場合、端、または２つ以上連続している箇所の間のLは確定できる。
後は確定した位置に隣接する要素は一意に決まるので順次決めていけば良い。

…というのは１つの考え方で、結果的にもっと簡単にLを構築できる。

• L[0]=R[0]
• L[N-1]=R[N-2]
• L[i]=min(R[i],R[i+1]) (0＜i＜N-1)

でよい。

int N;
int K[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	N--;
	FOR(i,N) cin>>K[i];
	_P("%d",K[0]);
	FOR(i,N-1) _P(" %d",min(K[i],K[i+1]));
	_P(" %d\n",K[N-1]);
}

まとめ

dwangoっていつもカタカナが頭に浮かぶせいかdowangoってスペルミスする。