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

C++の練習を兼ねて, AtCoder Beginner Contest 038 の問題C（単調増加) ～問題D (プレゼント) を解いてみた.

■感想.
1. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
2. Binary Indexed Tree について, そもそも知らなかったので, 後述の参照サイトを元に, サンプルプログラム(binary_indexed_sample.cpp) で, いったん動作確認してみた.
3. 組み立てた解答が, テストケースをほとんど通過しなかったので, 正解者のコーディングを参照したところ, update関数で, tree[idx] の更新処理が誤っていることが分かったので, 以下のように修正した.
[修正前]
値 k で更新.

[修正後]
値 k と tree[idx] のうち, 大きい方で更新.

本家のサイトAtCoder Beginnar Contest 038 解説をご覧下さい.
※感想として, 私見ではあるが, 以下の読み替えが必要となるように思われる.
解説(P.20): “列で1番目からk番目の最小値を求める操作” -> “列で1番目からk番目の最大値を求める操作”
解説(P.21): “update(i,a)を列のi番目をaで更新” -> “update(i,a)を列のi番目を a, BIT[i] の大きい方で更新”

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    
    // 2. 単調増加を調べる.
    LL ans = 1;
    LL inc = 0;  // 単調増加の連続項数.
    LL bef;      // 前回の数.
    cin >> bef;
    FOR(i, 1, N) {
        LL a;
        cin >> a;
        if(bef < a) {
            inc = inc + 1;
            ans += inc;
        } else {
            inc = 0;
        }
        bef = a;
        ans++;
    }
    
    // 3. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

// 2. 単調増加を調べる.

LL ans = 1;

LL inc = 0; // 単調増加の連続項数.

LL bef; // 前回の数.

cin >> bef;

FOR(i, 1, N) {

LL a;

cin >> a;

if(bef < a) {

inc = inc + 1;

ans += inc;

} else {

inc = 0;

}

bef = a;

ans++;

}

// 3. 出力～後処理.

cout << ans << endl;

return 0;

}

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

// 解き直し.
// AtCoder Beginnar Contest 038解説
// http://abc038.contest.atcoder.jp/data/abc/038/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

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

struct box {
    int h; // 高さ.
    int w; // 幅.
};

// How do i sort a pair increasing based on first element then decreasing based on second element?
// https://stackoverflow.com/questions/35776189/how-do-i-sort-a-pair-increasing-based-on-first-element-then-decreasing-based-on
struct boxCompareHeight {
    bool operator()(const box &a, const box &b) {
        if (a.h == b.h) return a.w > b.w;
        else            return a.h < b.h;
    }
};

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the maximum from index 1 to idx
// @param idx: 指定された範囲におけるインデックスの最大値.
// @param tree: binary indexed tree の 構造を持った配列.
// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.
// -> @return ret: binary indexed tree の 構造を持った配列上で, インデックス 1 ～ idx までの最大値を計算.
int query(int idx, int tree[]) {
    int ret = 0;
    // Returns the sum from index 1 to idx
    // while(idx > 0) ret += tree[idx], idx -= LSB(idx);
    // -> 以下のように修正.
    while(idx > 0) ret = max(ret, tree[idx]), idx -= LSB(idx);
    return ret;
}

// Update each tree[idx] on the larger of k and tree[idx].
// @param idx: 通常の配列における更新対象要素のインデックス.
// @param k: 加算する値.
// @param tree: binary indexed tree の 構造を持った配列.
// @param size: 通常の配列についての配列サイズ.
// @return: none.
void update(int idx, int k, int tree[], int size) {
    // Adds k to element with index idx
    // while(idx < size) tree[idx] += k, idx += LSB(idx);
    // -> 以下のように修正.
    // Update k to element with index idx
    // while(idx < size) tree[idx] = k, idx += LSB(idx);
    // -> sample0.txt, sample1.txt, subtask0_10.txt, subtask0_11.txt, subtask1_10.txt, subtask1_11.txt 以外全てWA.
    // -> 正解者の方々のソースを参照して, 以下のように修正.
    while(idx < size) tree[idx] = max(k, tree[idx]), idx += LSB(idx);
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<box> v;
    FOR(i, 0, N) {
        box b;
        cin >> b.w >> b.h;
        v.push_back(b);
    }
    
    // 2. 解説通り.
    // プレゼントの入れ子の最大数を確認.
    // -> Binary Indexed Tree を使うとのこと.
    
    // 2-1. 高さで昇順sort.
    // -> 高さが同じ場合は, 幅の降順sortとする(※解説通り).
    boxCompareHeight bch;
    sort(v.begin(), v.end(), bch);
    // for(auto &p : v) cout << p.w << " " << p.h << endl;
    // cout << endl;

    // 2-2. dp, bit を 計算.
    // dp(i) == i番目の箱を, 最も外側とするとき, 最大何重の入れ子に出来るか.
    // int LIMIT = 10;  // Debug用.
    int LIMIT = 100000;
    int dp[LIMIT + 1] = {};
    // bit(i) == 最も外側の箱の横の長さが, iとなる入れ子の数の最大値.
    int bit[LIMIT + 1] = {};
    dp[0] = 0;
    bit[0] = 0;
    FOR(i, 1, N + 1) {
        dp[i] = query(v[i - 1].w - 1, bit) + 1;
        update(v[i - 1].w, dp[i], bit, LIMIT + 1);
    }
    // FOR(i, 0, LIMIT + 1) cout << "dp=" << dp[i] << " bit=" << bit[i] << endl;
    
    // 3. 出力 ～ 後処理.
    int ans = 0;
    FOR(i, 1, LIMIT + 1) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
    
}

100

101

102

103

// 解き直し.

// AtCoder Beginnar Contest 038解説

// http://abc038.contest.atcoder.jp/data/abc/038/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

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

struct box {

int h; // 高さ.

int w; // 幅.

};

// How do i sort a pair increasing based on first element then decreasing based on second element?

// https://stackoverflow.com/questions/35776189/how-do-i-sort-a-pair-increasing-based-on-first-element-then-decreasing-based-on

struct boxCompareHeight {

bool operator()(const box &a, const box &b) {

if (a.h == b.h) return a.w > b.w;

else return a.h < b.h;

}

};

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the maximum from index 1 to idx

// @param idx: 指定された範囲におけるインデックスの最大値.

// @param tree: binary indexed tree の構造を持った配列.

// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.

// -> @return ret: binary indexed tree の構造を持った配列上で, インデックス 1 ～ idx までの最大値を計算.

int query(int idx, int tree[]) {

int ret = 0;

// Returns the sum from index 1 to idx

// while(idx > 0) ret += tree[idx], idx -= LSB(idx);

// -> 以下のように修正.

while(idx > 0) ret = max(ret, tree[idx]), idx -= LSB(idx);

return ret;

}

// Update each tree[idx] on the larger of k and tree[idx].

// @param idx: 通常の配列における更新対象要素のインデックス.

// @param k: 加算する値.

// @param tree: binary indexed tree の構造を持った配列.

// @param size: 通常の配列についての配列サイズ.

// @return: none.

void update(int idx, int k, int tree[], int size) {

// Adds k to element with index idx

// while(idx < size) tree[idx] += k, idx += LSB(idx);

// -> 以下のように修正.

// Update k to element with index idx

// while(idx < size) tree[idx] = k, idx += LSB(idx);

// -> sample0.txt, sample1.txt, subtask0_10.txt, subtask0_11.txt, subtask1_10.txt, subtask1_11.txt 以外全てWA.

// -> 正解者の方々のソースを参照して, 以下のように修正.

while(idx < size) tree[idx] = max(k, tree[idx]), idx += LSB(idx);

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<box> v;

FOR(i, 0, N) {

box b;

cin >> b.w >> b.h;

v.push_back(b);

}

// 2. 解説通り.

// プレゼントの入れ子の最大数を確認.

// -> Binary Indexed Tree を使うとのこと.

// 2-1. 高さで昇順sort.

// -> 高さが同じ場合は, 幅の降順sortとする(※解説通り).

boxCompareHeight bch;

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

// for(auto &p : v) cout << p.w << " " << p.h << endl;

// cout << endl;

// 2-2. dp, bit を計算.

// dp(i) == i番目の箱を, 最も外側とするとき, 最大何重の入れ子に出来るか.

// int LIMIT = 10; // Debug用.

int LIMIT = 100000;

int dp[LIMIT + 1] = {};

// bit(i) == 最も外側の箱の横の長さが, iとなる入れ子の数の最大値.

int bit[LIMIT + 1] = {};

dp[0] = 0;

bit[0] = 0;

FOR(i, 1, N + 1) {

dp[i] = query(v[i - 1].w - 1, bit) + 1;

update(v[i - 1].w, dp[i], bit, LIMIT + 1);

}

// FOR(i, 0, LIMIT + 1) cout << "dp=" << dp[i] << " bit=" << bit[i] << endl;

// 3. 出力～後処理.

int ans = 0;

FOR(i, 1, LIMIT + 1) ans = max(ans, dp[i]);

cout << ans << endl;

return 0;

}

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

[出力例]
4

[入力例]
8
3 1000
2 3
3 4
2 999
4 7
5 4
1 998
1 2

[出力例]
4

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

[出力例]
7
※(1, 2) -> (2, 3) -> (3, 4) -> (5, 6) -> (7, 8) -> (8, 9) -> (10, 12) で, 7重と分かる.

[入力例]

8 8

5 3

2 2

4 2

2 1

※AtCoderテストケースより

[出力例]

[入力例]

3 1000

2 3

3 4

2 999

4 7

5 4

1 998

1 2

[出力例]

[入力例]

1 2

2 3

5 6

3 4

4 3

4 7

8 9

10 12

7 8

4 4

[出力例]

※(1, 2) -> (2, 3) -> (3, 4) -> (5, 6) -> (7, 8) -> (8, 9) -> (10, 12) で, 7重と分かる.

■Binary Indexed Tree とは？

// Fenwick tree.
// https://en.wikipedia.org/wiki/Fenwick_tree
// Fenwick (Binary Indexed) Trees.
// https://www.hackerearth.com/ja/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/
// Binary Indexed Tree のはなし.
// http://hos.ac/slides/20140319_bit.pdf
#include <bits/stdc++.h>

using namespace std;

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the sum from index 1 to idx
// @param idx: 指定された範囲におけるインデックスの最大値.
// @param tree: binary indexed tree の 構造を持った配列.
// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.
int query(int idx, int tree[]) {
    int ret = 0;
    while(idx > 0) ret += tree[idx], idx -= LSB(idx);
    return ret;
}

// Adds k to element with index idx
// @param idx: 通常の配列における更新対象要素のインデックス.
// @param k: 加算する値.
// @param tree: binary indexed tree の 構造を持った配列.
// @param size: 通常の配列についての配列サイズ.
// @return: none.
void update(int idx, int k, int tree[], int size) {
    while(idx < size) tree[idx] += k, idx += LSB(idx);
}

int main() {
    
    // 1. 変数初期化など.
    int N = 10;
    int tree[N + 1] = {};
    
    // 2. 配列 tree を, 通常の配列として初期化.
    // ex.
    // 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
    FOR(i, 1, N + 1) tree[i] = (1 << (i - 1));
    cout << "---------- initialize as an array -----------------------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;
    
    // 3. 配列 tree を, binary indexed tree の 構造を持った配列として初期化.
    // ex.
    // 1, 3(= 1 + 2), 4, 15(= 1 + 2 + 4 + 8), 16, 48(= 16 + 32), 64, 
    // 255(= 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128), 256, 768(= 256 + 512)
    FOR(i, 1, N + 1) tree[i + LSB(i)] += tree[i];
    cout << "---------- initialize as a binary indexed tree ----------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;
    
    // 4. 累積和確認.
    int a = query(3, tree);
    int b = query(7, tree);
    int c = query(9, tree);
    cout << "---------- check sum as a binary indexed tree -----------" << endl;
    cout << "a=" << a << " b=" << b << " c=" << c << endl;
    
    // 5. 更新確認.
    update(1, 5, tree, 10);
    cout << "---------- updated as a binary indexed tree -------------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;
    update(3, 2, tree, 10);
    cout << "---------- updated as a binary indexed tree -------------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

    return 0;

}

// Fenwick tree.

// https://en.wikipedia.org/wiki/Fenwick_tree

// Fenwick (Binary Indexed) Trees.

// https://www.hackerearth.com/ja/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/

// Binary Indexed Tree のはなし.

// http://hos.ac/slides/20140319_bit.pdf

#include <bits/stdc++.h>

using namespace std;

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the sum from index 1 to idx

// @param idx: 指定された範囲におけるインデックスの最大値.

// @param tree: binary indexed tree の構造を持った配列.

// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.

int query(int idx, int tree[]) {

int ret = 0;

while(idx > 0) ret += tree[idx], idx -= LSB(idx);

return ret;

}

// Adds k to element with index idx

// @param idx: 通常の配列における更新対象要素のインデックス.

// @param k: 加算する値.

// @param tree: binary indexed tree の構造を持った配列.

// @param size: 通常の配列についての配列サイズ.

// @return: none.

void update(int idx, int k, int tree[], int size) {

while(idx < size) tree[idx] += k, idx += LSB(idx);

}

int main() {

// 1. 変数初期化など.

int N = 10;

int tree[N + 1] = {};

// 2. 配列 tree を, 通常の配列として初期化.

// ex.

// 1, 2, 4, 8, 16, 32, 64, 128, 256, 512

FOR(i, 1, N + 1) tree[i] = (1 << (i - 1));

cout << "---------- initialize as an array -----------------------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

// 3. 配列 tree を, binary indexed tree の構造を持った配列として初期化.

// ex.

// 1, 3(= 1 + 2), 4, 15(= 1 + 2 + 4 + 8), 16, 48(= 16 + 32), 64,

// 255(= 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128), 256, 768(= 256 + 512)

FOR(i, 1, N + 1) tree[i + LSB(i)] += tree[i];

cout << "---------- initialize as a binary indexed tree ----------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

// 4. 累積和確認.

int a = query(3, tree);

int b = query(7, tree);

int c = query(9, tree);

cout << "---------- check sum as a binary indexed tree -----------" << endl;

cout << "a=" << a << " b=" << b << " c=" << c << endl;

// 5. 更新確認.

update(1, 5, tree, 10);

cout << "---------- updated as a binary indexed tree -------------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

update(3, 2, tree, 10);

cout << "---------- updated as a binary indexed tree -------------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

return 0;

}

※値の変化が目立つように, 出力結果に, コメント(<--- +5, <--- +2) を追加している.
---------- initialize as an array -----------------------
i=1 tree[1]=1
i=2 tree[2]=2
i=3 tree[3]=4
i=4 tree[4]=8
i=5 tree[5]=16
i=6 tree[6]=32
i=7 tree[7]=64
i=8 tree[8]=128
i=9 tree[9]=256
i=10 tree[10]=512
---------- initialize as a binary indexed tree ----------
i=1 tree[1]=1
i=2 tree[2]=3
i=3 tree[3]=4
i=4 tree[4]=15
i=5 tree[5]=16
i=6 tree[6]=48
i=7 tree[7]=64
i=8 tree[8]=255
i=9 tree[9]=256
i=10 tree[10]=768
---------- check sum as a binary indexed tree -----------
a=7 b=127 c=511
---------- updated as a binary indexed tree -------------
i=1 tree[1]=6    <--- +5
i=2 tree[2]=8    <--- +5
i=3 tree[3]=4
i=4 tree[4]=20   <--- +5
i=5 tree[5]=16
i=6 tree[6]=48
i=7 tree[7]=64
i=8 tree[8]=260  <--- +5
i=9 tree[9]=256
i=10 tree[10]=768
---------- updated as a binary indexed tree -------------
i=1 tree[1]=6
i=2 tree[2]=8
i=3 tree[3]=6    <--- +2
i=4 tree[4]=22   <--- +2
i=5 tree[5]=16
i=6 tree[6]=48
i=7 tree[7]=64
i=8 tree[8]=262  <--- +2
i=9 tree[9]=256
i=10 tree[10]=768

※値の変化が目立つように, 出力結果に, コメント(<--- +5, <--- +2) を追加している.

---------- initialize as an array -----------------------

i=1 tree[1]=1

i=2 tree[2]=2

i=3 tree[3]=4

i=4 tree[4]=8

i=5 tree[5]=16

i=6 tree[6]=32

i=7 tree[7]=64

i=8 tree[8]=128

i=9 tree[9]=256

i=10 tree[10]=512

---------- initialize as a binary indexed tree ----------

i=1 tree[1]=1

i=2 tree[2]=3

i=3 tree[3]=4

i=4 tree[4]=15

i=5 tree[5]=16

i=6 tree[6]=48

i=7 tree[7]=64

i=8 tree[8]=255

i=9 tree[9]=256

i=10 tree[10]=768

---------- check sum as a binary indexed tree -----------

a=7 b=127 c=511

---------- updated as a binary indexed tree -------------

i=1 tree[1]=6 <--- +5

i=2 tree[2]=8 <--- +5

i=3 tree[3]=4

i=4 tree[4]=20 <--- +5

i=5 tree[5]=16

i=6 tree[6]=48

i=7 tree[7]=64

i=8 tree[8]=260 <--- +5

i=9 tree[9]=256

i=10 tree[10]=768

---------- updated as a binary indexed tree -------------

i=1 tree[1]=6

i=2 tree[2]=8

i=3 tree[3]=6 <--- +2

i=4 tree[4]=22 <--- +2

i=5 tree[5]=16

i=6 tree[6]=48

i=7 tree[7]=64

i=8 tree[8]=262 <--- +2

i=9 tree[9]=256

i=10 tree[10]=768

■参照サイト
AtCoder Beginner Contest 038
Fenwick tree.
Fenwick (Binary Indexed) Trees.
Binary Indexed Tree のはなし.

C++の練習を兼ねて, AtCoder Beginner Contest 038 の 問題C（単調増加) ～ 問題D (プレゼント) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 038 の問題C（単調増加) ～問題D (プレゼント) を解いてみた.

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