AtCoder AGC #002 : C - Knot Puzzle

またもいまいち。AGCになってから海外勢の参加分以上に順位が落ちている気がする。
http://agc002.contest.atcoder.jp/tasks/agc002_c

問題

N個のロープが順につながれており、各ロープの長さはA[i]である。

このロープをすべてバラバラにほどきたい。
その際、つながったロープの長さの総和がL以上であるロープについて、１か所つなぎ目をほどく、という作業を繰り返す。
最適な順にロープをほどいたとき、全部の結び目をほどけるか判定せよ。

解法

ハフマン符号っぽいものが思いついて途中まで実装してしまい、大幅にタイムロスした。

つながったものをほどくのではなく、逆順にバラバラなものをつなぐことを考えてみる。
つないだ後の長さがL以上になるロープはつなぐことができる。

とすると、ここでA[i]+A[i+1]≧Lであるような隣接ロープがあったとする。
この２つをつなぐとその時点でL以上の長さのロープができるので、後は両サイドを適当にこのロープに順につなげていけば良い。
あとはつないだ順を反転すればほどく順が答えられる。

int N,L;
ll A[101010];

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

まとめ

この発想にたどり着くまで時間をかけすぎた…。