C++ の動作確認をしてみた（４９）

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題C（C – Knot Puzzle) を解いてみた.

■感想.
1. いったん実装してみた(下記, WA版)が, ロジックの修正方法が分からなかったので, 解説を見て, 再度やり直ししたものである.
解説を見て, 本問についても, なるほどと感心させられた.

本家のサイトAtCoder Grand Contest 002 解説をご覧下さい.

■C++版プログラム(問題C／WA版).
※テストケース(1_04.txt, 1_08.txt, 1_10.txt, 1_18.txt, 1_21.txt, 1_22.txt, 1_24.txt, 1_26.txt, 1_27.txt, 1_29.txt)で,
WA判定となった.

// WA版.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<string, int> P;

bool comp1(const P& f, const P& s) { return f.second < s.second; }
bool comp2(const P& f, const P& s) { return (f.first < s.first && f.second > s.second); }

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

int main() {
    
    // 1. 入力情報取得.
    int N;
    LL L;
    cin >> N >> L;
    vector<P> knots;
    
    // 結び目情報(前回, 今回).
    LL bef, cur;
    int ok = 0;
    cin >> bef;
    FOR(i, 1, N) {
        string s;
        cin >> cur;
        if(cur + bef >= L)  s = "OK", ok++;
        else                s = "NG";
        knots.push_back(make_pair(s, i));
        // 前回結び目情報を更新.
        bef = cur;
    }
    // for(auto &p : knots) cout << "status: " << p.first << "  knot index:" << p.second << endl;
    
    // 2. OK が 一つもない場合は, 終了.
    string ans = "Impossible";
    if(ok == 0) {
        cout << ans << endl;
        return 0;
    }
    
    // 3. 各区間に, "OK" が, 一つずつ含まれるように分割.
    vector<vector<P>> setOfKnots;
    priority_queue<P> q;
    ok = 0;
    for(auto &p : knots) {
        
        string status = p.first;
        int knotIndex = p.second;
        // 3-1. status が "OK" なら, ok を increment.
        if(status == "OK") ok++;
        // cout << "status: " << status << "  knot index:" << knotIndex << " q.size()=" << q.size() << " ok=" << ok << endl;
        // 3-2. ok == 1 の 場合は, setOfKnots に 登録.
        if(ok == 1) {
            // priority queue を 空にする.
            vector<P> v;
            while(!q.empty()) {
                v.push_back(q.top());
                q.pop();
            }
            setOfKnots.push_back(v);
            ok = 0;
        }
        q.push(make_pair(status, knotIndex));
    }
    // 3-3. 残りを setOfKnots に 登録.
    vector<P> v;
    while(!q.empty()) {
        v.push_back(q.top());
        q.pop();
    }
    setOfKnots.push_back(v);
    
    // 4. 各区間について, 出力.
    // setOfKnots の 各区間の先頭が, status: OK になっているはず.
    // -> 最初の区間は, status: OK が含まれてないはずなので,2番目の区間に合わせて出力.
    ans = "Possible";
    cout << ans << endl;
    int nKnot = 1;
    for(auto &knots : setOfKnots) {
        // cout << "--- start this set ---" << endl;
        if(nKnot == 1) sort(knots.begin(), knots.end(), comp1);
        else           sort(knots.begin(), knots.end(), comp2);
        for(auto &p : knots) {
            // cout << "status: " << p.first << "  knot index:" << p.second << endl;
            cout << p.second << endl;
        }
        // cout << "---- end this set ----" << endl;
        nKnot++;
    }
    return 0;
    
}

// WA版.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<string, int> P;

bool comp1(const P& f, const P& s) { return f.second < s.second; }

bool comp2(const P& f, const P& s) { return (f.first < s.first && f.second > s.second); }

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

int main() {

// 1. 入力情報取得.

int N;

LL L;

cin >> N >> L;

vector knots;

// 結び目情報(前回, 今回).

LL bef, cur;

int ok = 0;

cin >> bef;

FOR(i, 1, N) {

string s;

cin >> cur;

if(cur + bef >= L) s = "OK", ok++;

else s = "NG";

knots.push_back(make_pair(s, i));

// 前回結び目情報を更新.

bef = cur;

}

// for(auto &p : knots) cout << "status: " << p.first << " knot index:" << p.second << endl;

// 2. OK が一つもない場合は, 終了.

string ans = "Impossible";

if(ok == 0) {

cout << ans << endl;

return 0;

}

// 3. 各区間に, "OK" が, 一つずつ含まれるように分割.

vector<vector> setOfKnots;

priority_queue q;

ok = 0;

for(auto &p : knots) {

string status = p.first;

int knotIndex = p.second;

// 3-1. status が "OK" なら, ok を increment.

if(status == "OK") ok++;

// cout << "status: " << status << " knot index:" << knotIndex << " q.size()=" << q.size() << " ok=" << ok << endl;

// 3-2. ok == 1 の場合は, setOfKnots に登録.

if(ok == 1) {

// priority queue を空にする.

vector v;

while(!q.empty()) {

v.push_back(q.top());

q.pop();

}

setOfKnots.push_back(v);

ok = 0;

}

q.push(make_pair(status, knotIndex));

}

// 3-3. 残りを setOfKnots に登録.

vector v;

while(!q.empty()) {

v.push_back(q.top());

q.pop();

}

setOfKnots.push_back(v);

// 4. 各区間について, 出力.

// setOfKnots の各区間の先頭が, status: OK になっているはず.

// -> 最初の区間は, status: OK が含まれてないはずなので,2番目の区間に合わせて出力.

ans = "Possible";

cout << ans << endl;

int nKnot = 1;

for(auto &knots : setOfKnots) {

// cout << "--- start this set ---" << endl;

if(nKnot == 1) sort(knots.begin(), knots.end(), comp1);

else sort(knots.begin(), knots.end(), comp2);

for(auto &p : knots) {

// cout << "status: " << p.first << " knot index:" << p.second << endl;

cout << p.second << endl;

}

// cout << "---- end this set ----" << endl;

nKnot++;

}

return 0;

}

■C++版プログラム(問題C／AC版).

// 解き直し.
// AtCoder Grand Contest 002 解説.
// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i, a, b)  for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)

int main() {
    
    // 1. 入力情報取得.
    int N;
    LL L;
    cin >> N >> L;
    vector<LL> a;
    FOR(i, 0, N) {
        LL k;
        cin >> k;
        a.push_back(k);
    }
    
    // 2. 解説通り.
    // a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.
    LL knotInfo[N - 1] = {};
    int lastKnotIndex = -1;
    FOR(i, 0, N - 1) {
        LL x = a[i] + a[i + 1];
        knotInfo[i] = x;
        if(x >= L) {
            lastKnotIndex = i + 1;
            break;
        }
    }
    
    // 3. 解説通り.
    // 最後にほどく結び目が, 一つもない場合は, 終了.
    if(lastKnotIndex == -1) {
        cout << "Impossible" << endl;
        return 0;
    }
    
    // 4. 解説通り.
    cout << "Possible" << endl;
    // 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.
    FOR(l, 1, lastKnotIndex)      cout << l << endl;
    // 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.
    FORR(r, N - 1, lastKnotIndex) cout << r << endl;
    // 4-3. 最後に，結び目 i をほどく.
    cout << lastKnotIndex << endl;

    return 0;
    
}

// 解き直し.

// AtCoder Grand Contest 002 解説.

// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

#define FORR(i, a, b) for(int i = (a); i > (b); --i)

int main() {

// 1. 入力情報取得.

int N;

LL L;

cin >> N >> L;

vector<LL> a;

FOR(i, 0, N) {

LL k;

cin >> k;

a.push_back(k);

}

// 2. 解説通り.

// a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.

LL knotInfo[N - 1] = {};

int lastKnotIndex = -1;

FOR(i, 0, N - 1) {

LL x = a[i] + a[i + 1];

knotInfo[i] = x;

if(x >= L) {

lastKnotIndex = i + 1;

break;

}

// 3. 解説通り.

// 最後にほどく結び目が, 一つもない場合は, 終了.

if(lastKnotIndex == -1) {

cout << "Impossible" << endl;

return 0;

}

// 4. 解説通り.

cout << "Possible" << endl;

// 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.

FOR(l, 1, lastKnotIndex) cout << l << endl;

// 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.

FORR(r, N - 1, lastKnotIndex) cout << r << endl;

// 4-3. 最後に，結び目 i をほどく.

cout << lastKnotIndex << endl;

return 0;

}

■C++版プログラム(問題C／AC版).
上記のプログラムが, 冗長に感じたので, 修正.

// 解き直し(その②).
// AtCoder Grand Contest 002 解説.
// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i, a, b)  for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)

int main() {
    
    // 1. 入力情報取得.
    int N;
    LL L;
    cin >> N >> L;
    
    // 2. 解説通り.
    // a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.
    int lastKnotIndex = -1;  // 最後にほどく結び目.
    LL bef;                  // 前回ロープ長.
    cin >> bef;
    FOR(i, 1, N) {
        LL cur;    // 今回ロープ長.
        cin >> cur;
        if(bef + cur >= L) {
            lastKnotIndex = i;
            break;
        }
        // 前回ロープ長を更新.
        bef = cur;
    }
    
    // 3. 解説通り.
    // 最後にほどく結び目が, 一つもない場合は, 終了.
    if(lastKnotIndex == -1) {
        cout << "Impossible" << endl;
        return 0;
    }
    
    // 4. 解説通り.
    cout << "Possible" << endl;
    // 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.
    FOR(l, 1, lastKnotIndex)      cout << l << endl;
    // 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.
    FORR(r, N - 1, lastKnotIndex) cout << r << endl;
    // 4-3. 最後に，結び目 i をほどく.
    cout << lastKnotIndex << endl;

    return 0;
    
}

// 解き直し(その②).

// AtCoder Grand Contest 002 解説.

// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

#define FORR(i, a, b) for(int i = (a); i > (b); --i)

int main() {

// 1. 入力情報取得.

int N;

LL L;

cin >> N >> L;

// 2. 解説通り.

// a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.

int lastKnotIndex = -1; // 最後にほどく結び目.

LL bef; // 前回ロープ長.

cin >> bef;

FOR(i, 1, N) {

LL cur; // 今回ロープ長.

cin >> cur;

if(bef + cur >= L) {

lastKnotIndex = i;

break;

}

// 前回ロープ長を更新.

bef = cur;

}

// 3. 解説通り.

// 最後にほどく結び目が, 一つもない場合は, 終了.

if(lastKnotIndex == -1) {

cout << "Impossible" << endl;

return 0;

}

// 4. 解説通り.

cout << "Possible" << endl;

// 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.

FOR(l, 1, lastKnotIndex) cout << l << endl;

// 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.

FORR(r, N - 1, lastKnotIndex) cout << r << endl;

// 4-3. 最後に，結び目 i をほどく.

cout << lastKnotIndex << endl;

return 0;

}

■参照サイト
AtCoder Grand Contest 002

C++の練習を兼ねて, AtCoder Grand Contest 002 の 問題C（C – Knot Puzzle) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題C（C – Knot Puzzle) を解いてみた.

コメントを残すコメントをキャンセル