AtCoder AGC 002 C - Knot Puzzle (水色, 500 点)

気づけばすぐな感じかな

問題へのリンク

問題概要

本のロープがあってそれぞれの長さは で与えられる。最初、ロープ の右端とロープ の左端が結ばれている。今、

• 長さが 以上のひとつながりのロープを選び、その中に結び目があればどれか 1 つ選んでほどく

という操作を結び目がなくなるまで 回行いたい。これが可能かどうか判定し、可能ならその方法を 1 つ示せ。

制約

• 

# 考えたこと いろいろ実験してみると、ひとまず

• 最後に長さ 2 の区間は必ず残ることになるので、
• 長さ 2 の連続した区間であって、その総和が 以上のところがなかったらどうしようもない

ということが言えて、逆に長さ 2 の連続区間であって、その総和が 以上のところがあったら、そこを最後に残すようにして左右から少しずつ切って行けば問題ない。

この問題だと割と易しめだから見えづらいけど、「必要条件を列挙したら十分条件になっていた」という高難易度でもお馴染みの典型パターンがすごく如実に含まれているイメージの問題だった。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; long long L; cin >> N >> L;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    int pl = -1;
    for (int i = 0; i+1 < N; ++i) if (A[i] + A[i+1] >= L) pl = i;

    if (pl == -1) { cout << "Impossible" << endl; return 0; }

    cout << "Possible" << endl;
    for (int i = 0; i < pl; ++i) cout << i+1 << endl;
    for (int i = N-2; i > pl; --i) cout << i+1 << endl;
    cout << pl+1 << endl;
}