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

C++の練習を兼ねて, AtCoder Beginner Contest 006 の問題D (D – トランプ挿入ソート) を解いてみた.

■感想.
1. 解答方針がよく分からなかったので, 解説を丸写しする感覚で解き直しした.
2. 新しい知識として, LIS(Longest increase subsequence) のアルゴリズムを体感できたので, 非常に勉強になったと思う.

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

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

// 解き直し.
// AtCoder Beginner Contest 006 解説.
// https://www.slideshare.net/chokudai/abc006
#include <bits/stdc++.h>
using namespace std;
const int MAX = 3e4 + 1;

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<int> c(N);
    vector<int> dp;
    for(int i = 0; i < N; i++) cin >> c[i];
    
    // 2. 解説通り.
    // -> LIS で 解く必要があるとのこと.
    dp.push_back(c[0]);
    for(int i = 1; i < N; i++){
        // 2-1. dpテーブル末尾 の 要素(last) より大きな値(c[i])であれば, dpテーブル に 追加.
        int last = dp.back();
        if(last < c[i]) dp.push_back(c[i]);
        // 2-2. dpテーブル末尾 の 要素(last) より小さな値(c[i])であれば, 
        // dpテーブル上 の 更新場所 を 探索後, dpテーブル を 更新.
        if(last > c[i]){
            auto it = lower_bound(dp.begin(), dp.end(), c[i]);
            int dist = it - dp.begin();
            dp[dist] = c[i];
            // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
            // cout << endl;
        }
    }
    // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
    // cout << endl;
    
    // 3. カードを昇順に並べるのに必要な回数を計算し, 出力.
    int ans = N - dp.size();
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

// AtCoder Beginner Contest 006 解説.

// https://www.slideshare.net/chokudai/abc006

#include <bits/stdc++.h>

using namespace std;

const int MAX = 3e4 + 1;

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<int> c(N);

vector<int> dp;

for(int i = 0; i < N; i++) cin >> c[i];

// 2. 解説通り.

// -> LIS で解く必要があるとのこと.

dp.push_back(c[0]);

for(int i = 1; i < N; i++){

// 2-1. dpテーブル末尾の要素(last) より大きな値(c[i])であれば, dpテーブルに追加.

int last = dp.back();

if(last < c[i]) dp.push_back(c[i]);

// 2-2. dpテーブル末尾の要素(last) より小さな値(c[i])であれば,

// dpテーブル上の更新場所を探索後, dpテーブルを更新.

if(last > c[i]){

auto it = lower_bound(dp.begin(), dp.end(), c[i]);

int dist = it - dp.begin();

dp[dist] = c[i];

// for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";

// cout << endl;

}

// for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";

// cout << endl;

// 3. カードを昇順に並べるのに必要な回数を計算し, 出力.

int ans = N - dp.size();

cout << ans << endl;

return 0;

}

[入力例]
6
1
3
5
2
4
6

[出力例(debug版)]
1 2 5 
1 2 4 
1 2 4 6 
2
※AtCoderテストケースより

[入力例]
8
1
2
5
3
8
6
4
7

[出力例(debug版)]
1 2 3 
1 2 3 6 
1 2 3 4 
1 2 3 4 7 
3

[入力例]
12
1
9
2
12
3
7
4
11
5
6
10
8

[出力例(debug版)]
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5 
1 2 3 4 5 6 8 
1 2 3 4 5 6 8 
5

実際, 
1 9  2 12 3  7  4 11  5  6 10  8 
↓
↓(1回目)
↓
1 2 12  3 7  4 11  5  6 10  8  9
↓
↓(2回目)
↓
1 2  3  7 4 11  5  6 10  8  9 12
↓
↓(3回目)
↓
1 2  3  7 4  5  6 10  8  9 11 12
↓
↓(4回目)
↓
1 2  3  7 4  5  6  8  9 10 11 12
↓
↓(5回目)
↓
1 2  3  4 5  6  7  8  9 10 11 12
の 5回 と分かる.

[入力例]

[出力例(debug版)]

1 2 5

1 2 4

1 2 4 6

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

1 2 3

1 2 3 6

1 2 3 4

1 2 3 4 7

[入力例]

[出力例(debug版)]

1 2

1 2 3

1 2 3 4

1 2 3 4 5

1 2 3 4 5 6 8

実際,

1 9 2 12 3 7 4 11 5 6 10 8

↓

↓(1回目)

↓

1 2 12 3 7 4 11 5 6 10 8 9

↓

↓(2回目)

↓

1 2 3 7 4 11 5 6 10 8 9 12

↓

↓(3回目)

↓

1 2 3 7 4 5 6 10 8 9 11 12

↓

↓(4回目)

↓

1 2 3 7 4 5 6 8 9 10 11 12

↓

↓(5回目)

↓

1 2 3 4 5 6 7 8 9 10 11 12

の 5回と分かる.

■参照サイト
AtCoder Beginner Contest 006

C++の練習を兼ねて, AtCoder Beginner Contest 006 の 問題D (D – トランプ挿入ソート) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 006 の問題D (D – トランプ挿入ソート) を解いてみた.

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