C++ の動作確認をしてみた（３１）

C++の練習を兼ねて, AtCoder Beginner Contest 056 の問題C（Go Home), 問題D（No Need) を解いてみた.

■感想.
1. 問題C, 問題D ともに, 時間はかかったもの(※特に, 問題D)の, 解説見ずに解けたので, 良かったと思う.
2. 当方の解答方針は, 入力値N(カードの枚数), K(よい集合の判定条件) を, 再帰的に, どんどん縮小していく方針を採用した.

本家のサイトARC070 / ABC056 解説をご覧下さい.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    LL X;
    cin >> X;
    
    // 2. カンガルーの家に到着する最小の時刻を計算.
    // 移動距離の総和を計算していき, X 以上のときに, 抜ける.
    // -> dist と X の 差分に相当する時刻 dist - X において, 移動しないを選択すればよいので最小のはず.
    // n(n + 1) / 2 >= 10 の 9乗 を満たす n は, 44720.8 … なので, 44721 まで確認すれば十分のはず.
    LL dist = 0;
    LL ans  = 0;
    FOR(i, 1, 44722) {
        dist += i;
        ans = i;
        if(dist >= X) break;
    }
    
    // 3. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

LL X;

cin >> X;

// 2. カンガルーの家に到着する最小の時刻を計算.

// 移動距離の総和を計算していき, X 以上のときに, 抜ける.

// -> dist と X の差分に相当する時刻 dist - X において, 移動しないを選択すればよいので最小のはず.

// n(n + 1) / 2 >= 10 の 9乗を満たす n は, 44720.8 … なので, 44721 まで確認すれば十分のはず.

LL dist = 0;

LL ans = 0;

FOR(i, 1, 44722) {

dist += i;

ans = i;

if(dist >= X) break;

}

// 3. 出力～後処理.

cout << ans << endl;

return 0;

}

■C++版プログラム(問題D／WA版, 2_042.txt で, Wrong Answer).

#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

// 不要なカードの枚数を調査し, 返却.
// @param v: カードに書かれている数字の集合.
// @param K: カードの部分集合に関する判定基準.
// @return ans: 不要なカードの枚数.
LL noNeedCards(vector<LL> &v, LL K) {
    
    // 1-1. K が ゼロ未満 の 場合は, v に 保管したカードの枚数だけ不要なので, それを出力.
    if(K <= 0) return v.size();
    
    // 1-2. v について, Σvi を 確認し, K を 超えるときの vi を 把握.
    LL total = 0;
    LL index = 0;
    // cout << K << endl;
    FOR(i, 0, v.size()) {
        total += v[i];
        index = i;
        // cout << index << " " << v[i] << " " << total << " " << endl;
        if(total >= K) break;
    }
    
    // 1-3. K に 満たない場合は, v に 保管したカードの枚数だけ不要なので, それを出力.
    if(total < K)  return v.size();

    // 1-4. K に 等しい場合は, すべてのカードが必要となるので, 不要なカードは, 0枚.
    if(total == K) return 0;

    // 1-5. K より 大きい場合は, 本関数を再帰呼び出しする.
    K -= v[index];
    v.resize(index);
    return noNeedCards(v, K);
    
}

int main() {

    // 1. 入力情報取得.
    LL N, K;
    cin >> N >> K;
    vector<LL> v;
    FOR(i, 0, N) {
        // ai >= K は, Skip.
        LL a;
        cin >> a;
        if(a < K) v.push_back(a);
    }
    
    // 2. K より 大きい場合は, 以下の内容を調べることになる.
    // 2-1. v を 昇順sort.
    sort(v.begin(), v.end());
    
    // 2-2. 不要なカードの枚数を調べる.
    LL ans = noNeedCards(v, K);
    
    // 3. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

// 不要なカードの枚数を調査し, 返却.

// @param v: カードに書かれている数字の集合.

// @param K: カードの部分集合に関する判定基準.

// @return ans: 不要なカードの枚数.

LL noNeedCards(vector<LL> &v, LL K) {

// 1-1. K がゼロ未満の場合は, v に保管したカードの枚数だけ不要なので, それを出力.

if(K <= 0) return v.size();

// 1-2. v について, Σvi を確認し, K を超えるときの vi を把握.

LL total = 0;

LL index = 0;

// cout << K << endl;

FOR(i, 0, v.size()) {

total += v[i];

index = i;

// cout << index << " " << v[i] << " " << total << " " << endl;

if(total >= K) break;

}

// 1-3. K に満たない場合は, v に保管したカードの枚数だけ不要なので, それを出力.

if(total < K) return v.size();

// 1-4. K に等しい場合は, すべてのカードが必要となるので, 不要なカードは, 0枚.

if(total == K) return 0;

// 1-5. K より大きい場合は, 本関数を再帰呼び出しする.

K -= v[index];

v.resize(index);

return noNeedCards(v, K);

}

int main() {

// 1. 入力情報取得.

LL N, K;

cin >> N >> K;

vector<LL> v;

FOR(i, 0, N) {

// ai >= K は, Skip.

LL a;

cin >> a;

if(a < K) v.push_back(a);

}

// 2. K より大きい場合は, 以下の内容を調べることになる.

// 2-1. v を昇順sort.

sort(v.begin(), v.end());

// 2-2. 不要なカードの枚数を調べる.

LL ans = noNeedCards(v, K);

// 3. 出力～後処理.

cout << ans << endl;

return 0;

}

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

#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

// 不要なカードの枚数を調査し, 返却.
// @param v: カードに書かれている数字の集合.
// @param K: カードの部分集合に関する判定基準.
// @return ans: 不要なカードの枚数.
LL noNeedCards(vector<LL> &v, LL K) {
    
    // 1-1. K が ゼロ未満 の 場合は, v に 保管したカードの枚数だけ不要なので, それを出力.
    // if(K <= 0) return v.size();    // 2_042.txt の Wrong Answer対策.
    if(K < 0) return v.size();
    
    // 1-2. v の 要素で, K以上を除外.
    // 0_002.txt の Wrong Answer対策.
    vector<LL> lv;
    for(auto &p : v) if(p < K) lv.push_back(p);    // p >= K は, Skip.
    
    // 1-3. v について, Σvi を 確認し, K を 超えるときの vi を 把握.
    LL total = 0;
    LL index = 0;
    // cout << K << endl;
    FOR(i, 0, lv.size()) {
        total += lv[i];
        index = i;
        // cout << index << " " << lv[i] << " " << total << " " << endl;
        // [input]
        // 4 5
        // 1 2 3 4
        // 
        // [output]
        // 5
        // 0 1 1 
        // 1 2 3 
        // 2 3 6 
        // 2
        // 0 1 1 
        // 1
        // -> 1 2 3 4 の 4 について, noNeedCards関数で, 評価される前に, 
        // Skipしてしまうことが, Wrong Answer の 原因と推定される.
        // -> よって, 以下のif文をコメントアウトした.
        // if(total >= K) break;    // 2_042.txt の Wrong Answer対策.
    }
    
    // 1-4. K に 満たない場合は, lv に 保管したカードの枚数だけ不要なので, それを出力.
    if(total < K)  return lv.size();

    // 1-5. K に 等しい場合は, すべてのカードが必要となるので, 不要なカードは, 0枚.
    if(total == K) return 0;

    // 1-6. K より 大きい場合は, 本関数を再帰呼び出しする.
    K -= lv[index];
    lv.resize(index);
    return noNeedCards(lv, K);
    
}

int main() {

    // 1. 入力情報取得.
    LL N, K;
    cin >> N >> K;
    vector<LL> v;
    FOR(i, 0, N) {
        // ai >= K は, Skip.
        LL a;
        cin >> a;
        if(a < K) v.push_back(a);
    }
    
    // 2. K より 大きい場合は, 以下の内容を調べることになる.
    // 2-1. v を 昇順sort.
    sort(v.begin(), v.end());
    
    // 2-2. 不要なカードの枚数を調べる.
    LL ans = noNeedCards(v, K);
    
    // 3. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

// 不要なカードの枚数を調査し, 返却.

// @param v: カードに書かれている数字の集合.

// @param K: カードの部分集合に関する判定基準.

// @return ans: 不要なカードの枚数.

LL noNeedCards(vector<LL> &v, LL K) {

// 1-1. K がゼロ未満の場合は, v に保管したカードの枚数だけ不要なので, それを出力.

// if(K <= 0) return v.size(); // 2_042.txt の Wrong Answer対策.

if(K < 0) return v.size();

// 1-2. v の要素で, K以上を除外.

// 0_002.txt の Wrong Answer対策.

vector<LL> lv;

for(auto &p : v) if(p < K) lv.push_back(p); // p >= K は, Skip.

// 1-3. v について, Σvi を確認し, K を超えるときの vi を把握.

LL total = 0;

LL index = 0;

// cout << K << endl;

FOR(i, 0, lv.size()) {

total += lv[i];

index = i;

// cout << index << " " << lv[i] << " " << total << " " << endl;

// [input]

// 4 5

// 1 2 3 4

// [output]

// 5

// 0 1 1

// 1 2 3

// 2 3 6

// 2

// 0 1 1

// 1

// -> 1 2 3 4 の 4 について, noNeedCards関数で, 評価される前に,

// Skipしてしまうことが, Wrong Answer の原因と推定される.

// -> よって, 以下のif文をコメントアウトした.

// if(total >= K) break; // 2_042.txt の Wrong Answer対策.

}

// 1-4. K に満たない場合は, lv に保管したカードの枚数だけ不要なので, それを出力.

if(total < K) return lv.size();

// 1-5. K に等しい場合は, すべてのカードが必要となるので, 不要なカードは, 0枚.

if(total == K) return 0;

// 1-6. K より大きい場合は, 本関数を再帰呼び出しする.

K -= lv[index];

lv.resize(index);

return noNeedCards(lv, K);

}

int main() {

// 1. 入力情報取得.

LL N, K;

cin >> N >> K;

vector<LL> v;

FOR(i, 0, N) {

// ai >= K は, Skip.

LL a;

cin >> a;

if(a < K) v.push_back(a);

}

// 2. K より大きい場合は, 以下の内容を調べることになる.

// 2-1. v を昇順sort.

sort(v.begin(), v.end());

// 2-2. 不要なカードの枚数を調べる.

LL ans = noNeedCards(v, K);

// 3. 出力～後処理.

cout << ans << endl;

return 0;

}

■デバッグ出力例(問題D／AC版).
[入力例] について, 最初から3つ目までを, 本家のサイトから, 抜粋している.

[入力例]
3 6
1 4 3

[出力例]
6
0 1 1 
1 3 4 
2 4 8 
2
0 1 1 
1
-> 上記, 1 が解答となる.

[入力例]
5 400
3 1 4 1 5

[出力例]
400
0 1 1 
1 1 2 
2 3 5 
3 4 9 
4 5 14 
5
-> 上記, 5 が解答となる.

[入力例]
6 20
10 4 3 10 25 2

[出力例]
20
0 2 2 
1 3 5 
2 4 9 
3 10 19 
4 10 29 
10
0 2 2 
1 3 5 
2 4 9 
3
-> 上記, 3 が解答となる.

[入力例]
4 5
1 2 3 4

[出力例]
5
0 1 1 
1 2 3 
2 3 6 
3 4 10 
1
0
-> 上記, 0 が解答となる.

[入力例]
5 10
1 3 5 7 9

[出力例]
10
0 1 1 
1 3 4 
2 5 9 
3 7 16 
4 9 25 
1
0
-> 上記, 0 が解答となる.

[入力例]
8 16
1 2 3 4 5 16 16 16

[出力例]
16
0 1 1 
1 2 3 
2 3 6 
3 4 10 
4 5 15 
5
-> 上記, 5 が解答となる.

[入力例]

3 6

1 4 3

[出力例]

0 1 1

1 3 4

2 4 8

0 1 1

-> 上記, 1 が解答となる.

[入力例]

5 400

3 1 4 1 5

[出力例]

400

0 1 1

1 1 2

2 3 5

3 4 9

4 5 14

-> 上記, 5 が解答となる.

[入力例]

6 20

10 4 3 10 25 2

[出力例]

0 2 2

1 3 5

2 4 9

3 10 19

4 10 29

0 2 2

1 3 5

2 4 9

-> 上記, 3 が解答となる.

[入力例]

4 5

1 2 3 4

[出力例]

0 1 1

1 2 3

2 3 6

3 4 10

-> 上記, 0 が解答となる.

[入力例]

5 10

1 3 5 7 9

[出力例]

0 1 1

1 3 4

2 5 9

3 7 16

4 9 25

-> 上記, 0 が解答となる.

[入力例]

8 16

1 2 3 4 5 16 16 16

[出力例]

0 1 1

1 2 3

2 3 6

3 4 10

4 5 15

-> 上記, 5 が解答となる.

■参照サイト
AtCoder Beginner Contest 056

C++の練習を兼ねて, AtCoder Beginner Contest 056 の 問題C（Go Home), 問題D（No Need) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 056 の問題C（Go Home), 問題D（No Need) を解いてみた.

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