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

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

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

章末問題

3.1

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

3.2

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

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;
}

本

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)