ためすう

割り算の切り上げを計算する (C++)

2020-01-13

やったこと

割り算した結果、小数を切り上げます。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    // 9 / 2 の切り上げ
    int t1 = ceil(9 / 2.0);
    cout << t1 << endl;

    // 9 / 2 の切り上げ
    int t2 = (9 + 2 - 1) / 2;
    cout << t2 << endl;


    // 9 / 3 の切り上げ
    int t3 = (9 + 3 - 1) / 3;
    cout << t3 << endl;
}

出力結果

5
5
3

2つ目の式の形

(x + y - 1) / y

こうすると割り切れる場合も、割り切れない場合も切り上げることができます。

__builtin_popcount を使ってみる (C++)

2020-01-13

やったこと

2進数で1を数えるため、 __builtin_popcount を使ってみます。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    for (int i = 0; i < (1 << 3); i++) {
        cout << bitset<8>(i);
        printf(" 1ビットが立っている数: %d\n", __builtin_popcount(i));
    }
}

出力結果

00000000 1ビットが立っている数: 0
00000001 1ビットが立っている数: 1
00000010 1ビットが立っている数: 1
00000011 1ビットが立っている数: 2
00000100 1ビットが立っている数: 1
00000101 1ビットが立っている数: 2
00000110 1ビットが立っている数: 2
00000111 1ビットが立っている数: 3

参考

popcount - cpprefjp C++日本語リファレンス

replace を使ってみる (C++)

2020-01-05

やったこと

replace を使ってみます。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    string t = "abcdefg";
    t.replace(1, 2, "-");
    cout << t << endl;

    t.replace(0, 1, 3, 'A');
    cout << t << endl;
}

出力結果

a-defg
AAA-defg

参考

accumulate でオーバーフローすることがある (C++)

2020-01-05

やったこと

accumulate で計算結果がオーバーフローした時の対処方法です。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

// accumulateの戻り値型は、第3引数の型となるため、変数sum_llの型はlong long

戻り値の型は、第3引数で決まります。なので、戻り値を long long にする場合、 0LL にする必要があります。

test.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll a[] = {(ll)1e9, (ll)1e9, (ll)1e9, (ll)1e9};

    cout << accumulate(a, a + 4, 0) << endl;
    cout << accumulate(a, a + 4, 0LL) << endl;
}

出力結果

-294967296
4000000000

参考

priority_queue を使ってみる (C++)

2019-12-30

やったこと

priority_queue を使ってみます。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[] = {3, 5, 2, 1, 9, 8};

    // 降順
    priority_queue<int> pq;

    // 昇順
    priority_queue<int, vector<int>, greater<int>> pq2;

    for (int i = 0; i < 6; i++) {
        pq.push(a[i]);
        pq2.push(a[i]);
    }

    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;


    while (!pq2.empty()) {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    cout << endl;
}

出力結果

9 8 5 3 2 1
1 2 3 5 8 9

参考

priority_queue - cpprefjp C++日本語リファレンス

deque を使ってみる (C++)

2019-12-30

やったこと

deque を使ってみます。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

＞ std::deque (double-ended queue) は先頭と末尾の両方に高速な挿入と削除が行えるインデックス付きのシーケンスコンテナです。

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> d = {2, 4, 6};
    d.push_front(100);
    d.push_back(333);

    for (int v : d) {
        cout << v << " ";
    }
    cout << endl;
}

出力結果

100 2 4 6 333

参考

std::deque - cppreference.com

getline を使ってみる (C++)

2019-12-29

やったこと

標準入力で空白文字を受け取るため、getline を使ってみます。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    string t;
    getline(cin, t);
    cout << t << endl;
}

出力結果

a b c (入力)
a b c

参考

getline - cpprefjp C++日本語リファレンス

erase を使ってみる (C++)

2019-12-29

やったこと

erase を使ってみます。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    string t = "abcdefg";
    t.erase(1, 2);
    cout << t << endl;

    vector<int> v = {1, 3, 5, 7};
    v.erase(v.begin() + 2);
    for (auto iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << endl;
    }
}

出力結果

adefg
1
3
7

参考

vector::erase - cpprefjp C++日本語リファレンス

tuple を使う (C++)

2019-12-29

やったこと

tuple を使ってみます。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    tuple<int, char, string> t = make_tuple(1, 'a', "abcd");
    cout << get<0>(t) << endl;
    cout << get<1>(t) << endl;
    cout << get<2>(t) << endl;
}

出力結果

1
a
abcd

参考

tuple - cpprefjp C++日本語リファレンス

unique を使ってみる (C++)

2019-12-26

やったこと

to_string を使ってみます。

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

この関数は、隣り合った重複要素を除いた要素を、範囲の先頭に集める。

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 1, 3, 2, 4, 5};
    sort(v.begin(), v.end());
    auto iter = unique(v.begin(), v.end());

    v.erase(iter, v.end());

    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << endl;;
    }
}

出力結果

参考

unique - cpprefjp C++日本語リファレンス