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

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

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

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

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

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

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)

競技プログラミング向けの本には、チーター本、螺旋本、蟻本が有名ですがこの本もそういったカテゴリーに入ると思います。

第1章 アルゴリズムとは

具体的なアルゴリズムの例を挙げて説明されています。僕が好きなアルゴリズムは迷路を解くような幅優先探索です。

章末問題 虫食い算

虫食い算を解きました。そういえば競技プログラミングの問題で虫食い算は解いたことがありませんね。AOJとかにありそうな感じがします。本当は深さ優先探索で書いた方が良かったと思いますが、for文で書きました。

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


int main() {
    vector<pair<int, int>> p;
    for (ll i = 100000; i < 1000000; i++) {
        for (ll j = 1; j < 10; j++) {
            ll a = i * j;
            if (a >= 1000000) break;
            if ((a / 100000) % 10 != 6) continue;
            if ((a / 10000) % 10 != 6) continue;
            for (ll k = 1; k < 10; k++) {
                ll b = i * k;
                if (b >= 1000000) break;
                if ((b / 100000) % 10 != 6) continue;
                for (ll l = 9; l >= 1; l--) {
                    ll c = i * l;
                    if (c < 1000000) break;
                    if ((c / 100) % 10 != 6) continue;
                    if ((c / 1000) % 10 != 6) continue;
                    if ((c / 10000) % 10 != 6) continue;
                    for (ll m = 1; m < 10; m++) {
                        ll d = i * m;
                        if (d % 10 != 6) continue;
                        if ((d / 1000) % 10 != 6) continue;
                        ll e = 1000 * m + 100 * l + 10 * k + j;
                        if (((i * e) / 10000) % 10 != 6) continue;
                        if (((i * e) / 100000) % 10 != 6) continue;
                        if (i * e < 1000000000) continue;
                        cout << i << "*" << j << "=" << i * j << "\n";
                        cout << i << "*" << k << "=" << i * k << "\n";
                        cout << i << "*" << l << "=" << i * l << "\n";
                        cout << i << "*" << m << "=" << i * m << "\n";
                        cout << i << "*" << e << "=" << i * e << "\n";
                    }
                }
            }
        }
    }
    return 0;
}

章末問題 経路復元

競技プログラミングの問題でゴールまでの最小値をもとめる問題は数多く出題されていますが、経路を答えさせる問題は解いたことがありませんでした。多分、最小値を求めてから、ゴールからスタートに向かって最小値を辿ることで復元できると思います。

第 2 章 計算量とオーダー記法

競プロは計算量を見積もることは大事で、制約から適用できるアルゴリズムの候補を考えることもあります。僕は小さい制約で難しい問題が特に苦手です。

最近点対問題

2点間の距離の最小値を求める問題は愚直に解くと、 O(N^{2}) の計算量が必要ですが、分割統治法を使うと計算量が  O(N\log N) になります。

分割統治法で解くアルゴリズムを調べましたが、あまり理解できませんでした。分割したあとに境界付近の点を調べるところが分からなかったです。

章末問題 計算時間

 T(N) = 2^{N} + N^{2019}

どの項が大きいかを見れば良いんですが、ぱっと見で分かりませんでした。

 2^{N} =  \sum _{i = 0}^{N}{}_N \mathrm{C}\ _{i}

となるので、 {}_N \mathrm{C}\ _{2019} などを考えると、 2^{N} が大きいと思いました。

章末問題 調和級数の和

 \dfrac{1}{x}積分すれば出てきます。

感想

最近点対が鬼門でした。