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

C++の練習を兼ねて, AtCoder Beginner Contest 165 の問題F (LIS on Tree) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. LIS(Longest increase subsequence) を学習できたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc165/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
const int INF = 2020202020;
int a[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    vi dp(N), ans(N);
    auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m){
        // 終了条件.
        if(m[cur]) return;
        
        // 訪問済みフラグ設定.
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            // Skip.
            if(nex == bef) continue;
            
            // dp更新.
            int at = lower_bound(all(dp), a[nex]) - dp.begin();
            int pd = dp[at];
            dp[at] = a[nex];
            
            // 狭義単調増加な数列の長さの最大値は？
            // -> 解説上 の LIS(Longest increase subsequence) の ロジック を 考慮すると, 
            //    初期化で, INF を設定するので, (INF - 1) の インデックス を 採用すれば, 良さそうに見える.
            ans[nex] = lower_bound(all(dp), INF - 1) - dp.begin();
            
            // 次へ.
            self(self, G, nex, cur, m);
            
            // dp戻し.
            dp[at] = pd;
        }
    };
    int memo[N];
    ans[0] = 1;
    rep(i, N) memo[i] = 0, dp[i] = INF;
    dp[0] = a[0];
    dfs(dfs, G, 0, -1, memo);
    
    // 3. 出力.
    rep(i, N) printf("%d\n", ans[i]);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc165/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

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

#define pb push_back

#define all(x) x.begin(), x.end()

const int INF = 2020202020;

int a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%d", &a[i]);

vvi G(N);

rep(i, N - 1){

int u, v;

scanf("%d %d", &u, &v);

--u;

--v;

G[u].pb(v);

G[v].pb(u);

}

// 2. dfs.

// https://ja.wikipedia.org/wiki/深さ優先探索

vi dp(N), ans(N);

auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m){

// 終了条件.

if(m[cur]) return;

// 訪問済みフラグ設定.

m[cur] = 1;

// 隣接頂点.

for(auto &nex : G[cur]){

// Skip.

if(nex == bef) continue;

// dp更新.

int at = lower_bound(all(dp), a[nex]) - dp.begin();

int pd = dp[at];

dp[at] = a[nex];

// 狭義単調増加な数列の長さの最大値は？

// -> 解説上の LIS(Longest increase subsequence) のロジックを考慮すると,

// 初期化で, INF を設定するので, (INF - 1) のインデックスを採用すれば, 良さそうに見える.

ans[nex] = lower_bound(all(dp), INF - 1) - dp.begin();

// 次へ.

self(self, G, nex, cur, m);

// dp戻し.

dp[at] = pd;

}

};

int memo[N];

ans[0] = 1;

rep(i, N) memo[i] = 0, dp[i] = INF;

dp[0] = a[0];

dfs(dfs, G, 0, -1, memo);

// 3. 出力.

rep(i, N) printf("%d\n", ans[i]);

return 0;

}

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

[出力例]
1
2
3
3
4
4
5
2
2
3
※AtCoderテストケースより

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

[出力例]
1
2
2
2
3

[入力例]
12
2 3 5 6 11 12 15 17 18 22 24 27
1 2
2 5
2 4
6 4
7 1
7 8
7 9
9 10
4 3
3 11
3 12

[出力例]
1
2
3
3
3
4
2
3
3
4
4
4

[入力例]
20
1 3 4 7 8 11 12 17 21 25 28 31 33 49 55 77 100 101 123 222
1 6
1 7
1 9
18 9
19 9
20 9
3 7
3 10
3 11
16 11
17 11
8 7
8 5
5 2
5 4
2 12
2 13
13 14
13 15

[出力例]
1
3
2
3
3
2
2
3
2
3
3
4
4
5
5
4
4
3
3
3

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

[入力例]

1 2 5 3 4 6 7 3 2 4

1 2

2 3

3 4

4 5

3 6

6 7

1 8

8 9

9 10

[出力例]

※AtCoderテストケースより

[入力例]

2 5 7 9 10

1 2

4 1

5 4

3 4

[出力例]

[入力例]

2 3 5 6 11 12 15 17 18 22 24 27

1 2

2 5

2 4

6 4

7 1

7 8

7 9

9 10

4 3

3 11

3 12

[出力例]

[入力例]

1 3 4 7 8 11 12 17 21 25 28 31 33 49 55 77 100 101 123 222

1 6

1 7

1 9

18 9

19 9

20 9

3 7

3 10

3 11

16 11

17 11

8 7

8 5

5 2

5 4

2 12

2 13

13 14

13 15

[出力例]

■参照サイト
AtCoder Beginner Contest 165

C++の練習を兼ねて, AtCoder Beginner Contest 165 の 問題F (LIS on Tree) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 165 の問題F (LIS on Tree) を解いてみた.

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