またもいまいち。AGCになってから海外勢の参加分以上に順位が落ちている気がする。
http://agc002.contest.atcoder.jp/tasks/agc002_c
問題
N個のロープが順につながれており、各ロープの長さはA[i]である。
このロープをすべてバラバラにほどきたい。
その際、つながったロープの長さの総和がL以上であるロープについて、1か所つなぎ目をほどく、という作業を繰り返す。
最適な順にロープをほどいたとき、全部の結び目をほどけるか判定せよ。
解法
ハフマン符号っぽいものが思いついて途中まで実装してしまい、大幅にタイムロスした。
つながったものをほどくのではなく、逆順にバラバラなものをつなぐことを考えてみる。
つないだ後の長さがL以上になるロープはつなぐことができる。
とすると、ここでA[i]+A[i+1]≧Lであるような隣接ロープがあったとする。
この2つをつなぐとその時点で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"); }
まとめ
この発想にたどり着くまで時間をかけすぎた…。