AGC002 C問題 Knot Puzzle

問題

agc002.contest.atcoder.jp

解説

この問題は結び目に注目して考察すれば解くことができます。 最後にほどくのは必ず左右のロープの長さの和がL以上の結び目でなければなりません。したがってそのような結び目が存在しなければほどくことはできません。 しかし、存在すれば必ずほどくことができます。それは長さL以上のロープが常に存在することになるからです。

ここで
(x,y)=(左端から結び目までの長さ, 右端から結び目までの長さ)
左右のロープの長さの和がL以上の結び目をM, 長さをLm
とします
その他の結び目に関して、Mの左側に存在すれば(x, y+Lm), 右側に存在すれば(x+Lm, y) となり、 全ての結び目に関して左右の総和がLを超えることになります。したがってMの結び目が存在するロープと切り離される結び目を作らないように解いていきます。 つまり、Mの左側に存在する結び目に関しては左から順番に、右側に存在する結び目に関しては右から順番に、最後にMを解けば全ての結び目をほどくことができます。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int ,int> P;
int main(void){
    int n, l, ans = 0;
    int a[100005], length[100005];
    vector<int> front, back;

    cin >> n >> l;

    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    for(int i=0; i<n-1; i++){
        length[i] = a[i] + a[i+1];
        if(length[i] >= l && ans == 0){
            ans = i+1;
        }else{
            if(ans == 0){
                front.push_back(i);
            }else{
                back.push_back(i);
            }
        }
    }

    reverse(back.begin(), back.end());

    for(int i=0; i<back.size(); i++){
        front.push_back(back[i]);
    }

    if(ans == 0){
        cout << "Impossible" << endl;
        return 0;
    }else{
        cout << "Possible" << endl;
    }

    for(int i=0; i<front.size(); i++){
        cout << front[i]+1 << endl;
    }
    
    cout << ans << endl;

    return 0;
}