山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

問題解決能力を鍛える!アルゴリズムとデータ構造 Part. 1

第3章 設計技法 (1) : 全探索

競技プログラミングでも基本となる全探索について学びます。全探索は全ての問題の基本となります。

章末問題

3.1

線形探索でターゲットとなる値の添え字を取得します。

3.2

 N 個の整数の最大値の配列を用意して、 b_i を整数を  i の出現回数とします。

3.3

線形探索で最大値と2番目に大きい値を更新します。

3.4

線形探索で最小値と最大値を見つけます。

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

int main() {
    int N, A;
    cin >> N;
    int best = 10000;
    for (int i = 0; i < N; i++) {
        cin >> A;
        int cnt = 0;
        while (A % 2 == 0) {
            A /= 2;
            cnt++;
        }
        best = min(best, cnt);
    }
    cout << best << "\n";
    return 0;
}
3.6
#include <bits/stdc++.h>
using namespace std;

int main() {
    int K, S;
    cin >> K >> S;
    int cnt = 0;
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j <= K; j++) {
            if (S - i - j >= 0 && S - i - j <= K) cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}
3.7

stoi でオーバーフローすることに気が付かずに、戸惑ってしまった。

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

int main() {
    string S;
    cin >> S;
    int n = 1 << (S.length() - 1);
    ll sum = 0;
    for (int i = 0; i < n; i++){
        int idx = 0;
        for (int j = 0; j < S.length() - 1; j++) {
            if ((i & (1<<j))) {
                sum += stoll(S.substr(idx, j + 1 - idx).c_str());
                idx = j + 1;
            }
        }
        sum += stoll(S.substr(idx).c_str());
    }
    cout << sum << "\n";
    return 0;
}