はまやんはまやんはまやん

hamayanhamayan's blog

Knot Puzzle [AGC 002 : C]

問題

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);
}