問題
N本のロープがあり、結び目で順に繋がれている。
ロープiの長さはai。
ここで、一繋がりになっているロープのうち、長さがL以上のものを選び、つなぎ目を取る。
この処理を繰り返して、全ての結び目が解けるか。
解けるなら、"Possible"とほどく順番を出力し、解けないなら"Impossible"を出力
2 <= N <= 10^5
1 <= ai <= 10^9
1 <= L <= 10^9
考察
1. 実験する。ひたすら。
2. うまくいかないので、逆から考えてみる(よく使うテク!)
3. 具体的には「解く」のではなく「繋ぐ」ものとして考える(処理の逆を考える)
4. 最後の結び目を解くときは、2本のロープの和がL以上である必要がある
5. 最後の1つ前の結び目を解くときは、そのロープとそれと隣り合うロープをくっつければ処理を満たす
6. その次の結び目も、隣り合うロープをくっつける
7. それを繰り返せばロープ全体を結ぶことができ、その手順を逆転させれば答え
8. つまり、答えがあるのは、隣り合うロープの和がL以上である組があるかどうか
実装
http://agc002.contest.atcoder.jp/submissions/825420
typedef long long ll; #define rrep(i,a,b) for(int i=a;i>=b;i--) int N; ll L; ll a[101010]; //----------------------------------------------------------------- int main() { cin >> N >> L; rep(i, 0, N) scanf("%d", &a[i]); int idx = -1; rep(i, 1, N) { ll sm = a[i] + a[i - 1]; if (L <= sm) { idx = i; break; } } if (idx < 0) { cout << "Impossible" << endl; return 0; } cout << "Possible" << endl; rep(i, 1, idx) printf("%d\n", i); rrep(i, N - 1, idx + 1) printf("%d\n", i); printf("%d\n", idx); }