「問題解決力を鍛える！アルゴリズムとデータ構造」の章末問題をPython3で実装していくシリーズ。

大枠まとめ記事は、ここに。 blacktanktop.hatenablog.com

前回の記事は、【第５章】設計技法(3)：動的計画法

今回は【第６章】設計技法(4)：二分探索法について扱う

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

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

内容
【第６章】設計技法(4)：二分探索法の概要
章末問題
まとめ
終わりに

内容

Python3でやっている。
簡単に自分の理解を整理する用。
そこまで厳密ではない可能性が高い。
記事を書いたら、書評の方に記事を載せていく。
コード等はGitHubにおいた。 github.com

【第６章】設計技法(4)：二分探索法の概要

にぶたん。探索範囲を半減させながら探索を行うため、非常に高速に探索できる。

二分探索法のポイント

探索範囲を半分にさせていきながら解を求める手法。

一般化させていくと、応用範囲が多い。

章末問題

6.1 座標圧縮

入力した配列aが重複がない整数列として、その配列の要素が何番目に小さいかを出力する。これを座標圧縮という。

二分探索で使うbisectのポイント
1. bisect_left(a, x)とすれば $a_i \lt x$ になるような個数が返ってくる。また、その数を挿入した場合の挿入先のindexでもある。
2. bisect_right(a, x)とすれば $a_i \leq x$ になるような個数が返ってくる。また、その数を挿入した場合の挿入先のindexでもある。

今回は、bisect_leftを使って、二分探索の関数binary_search()を実装した。が、Pythonはbisect_leftという組み込み関数があるのでそれを使えばいい。

入力は以下を想定している。

12 43 7 15 9

from bisect import bisect_left

def main():
    def binary_search(list, n):
        # 左右のindexで考える
        l = 0
        h = len(list) - 1
        flag = False
        while l <= h:
            mid = (l+h) // 2
            tmp = list[mid]
            if n == tmp:
                flag = True
                break
            elif tmp < n:
                l = mid + 1
            elif tmp > n:
                h = mid - 1
        return mid
    
    a = [int(x) for x in input().split()]
    # 二分探索するためにソート
    a_s = sorted(a)
    print('ソートされたa', a_s)
    for i in a:
        print('i', i)
        print('（index的に）何番目に小さいか(自作関数)', binary_search(a_s, i))
        print('（index的に）何番目に小さいか（組み込み関数）', bisect_left(a_s, i))
if __name__ == '__main__':
    main()

6.2 Snuke Festival

出典は、この問題。 atcoder.jp

二分探索に気づいても、愚直に $a \lt b$ を探すために $a$ をforで回すと、その中で $b\lt c$ を探すために対象の $b$ をforで回すことになって、 $O(nlog(n))$ にはならない。

ではどうするかというと、 $b$ を中心に考える。
$b$ をforで回して、以下のようにやる。

$a \lt b$ を探す。
を探す。
- 上で「二分探索で使うbisectのポイント」を書いたが、bisectでは対象のリストの要素がある数値よりも小さい個数を返すか(bisect_left)、ある数値以下の個数を返す(bisect_right)
- なので、 $b \lt c$ を探すには、bisect_rightで $c \leq b$ を求める。
- その値を $n$ から引くことで求める。

入力例は

6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288

b: 58
aの候補: [2, 3, 6, 14, 53]
cの候補: [79, 288, 383, 2643]
aの候補数 x cの候補数 20
b: 9
aの候補: [2, 3, 6]
cの候補: [50, 79, 288, 383, 2643]
aの候補数 x cの候補数 15
b: 79
aの候補: [2, 3, 6, 14, 53]
cの候補: [288, 383, 2643]
aの候補数 x cの候補数 15
b: 323
aの候補: [2, 3, 6, 14, 53, 159]
cの候補: [383, 2643]
aの候補数 x cの候補数 12
b: 84
aの候補: [2, 3, 6, 14, 53]
cの候補: [288, 383, 2643]
aの候補数 x cの候補数 15
b: 6
aの候補: [2, 3]
cの候補: [50, 79, 288, 383, 2643]
aの候補数 x cの候補数 10
なので、87が答え

from bisect import bisect_left, bisect_right

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    a_s = sorted(a)
    c_s = sorted(c)
    ans = 0
    for j in b:
        # a[i] < bの個数 
        a_b = bisect_left(a_s, j)
        print('b:', j)
        print('aの候補:', a_s[:a_b])
        # c[k] <= bの個数(求めたい方の逆)
        c_b = bisect_right(c_s, j)
        # b < c[k](全体の個数から引き算)
        b_c = n - c_b
        print('cの候補:', c_s[c_b:])
        print('aの候補数 x cの候補数', a_b * b_c)
        ans += a_b * b_c
    print('合計', ans)
if __name__ == '__main__':
    main()

6.3 ダーツ

問題の出典は第７回日本情報オリンピック本選の第３問

概要は、

$n$ 個の正の整数列 $a$ が与えられる。
重複を許して $a$ から4つ選んだ時の総和が $m$ を超えないようにする。
その時の総和の最大値は？
4つ選ぶ時に0もOK（何も選ばないもOK）
ただし計算量が $O(N^2log(N))$ で。

$O(N^2log(N))$ は結構厳しい。

愚直に、全てforで回すと $O(N^4))$
工夫して、6.2みたいに一つを固定する感じでやると $O(N^2log(N)))$
ではどうするか。
$a$ から2つ選んだ配列を作って、そこから1つずつ選ぶと考える。
まず、リストと値を与えたら、値を超えない最大値を得る関数をつくる。
bisectのポイントにも書いたが、bisect_right(a, x)とすれば $a_i \leq x$ になるような、その数を挿入した場合ので挿入先のindexを返してくるので値を超えない最大値のindexはそのindex-1となる。

from bisect import bisect_right
def listmax(l, x):
    return l[bisect_right(l, x)-1]

そして、あとは $a$ から2つ選んだ配列を作ってソート（配列 $q$ とする）
$q$ から1つずつ取り出して（値を $x$ とする）いって、 $x$ が $m$ を超えないなら、 $x + listmax(q, x)$ として、 $x$ ごとに最適な相手を見つけ、配列に加える。
最後にmaxをとる。入力は以下のような形を想定

from bisect import bisect_right

def main():
    # リストからx以下の最大値を得る
    def listmax(l, x):
        return l[bisect_right(l, x)-1]

    n, m = map(int, input().split())
    a = [0] + [int(input()) for _ in range(n)]
    q = sorted({i+j for i in a for j in a})
    print('aから重複（0も）許して２つ選んで足したリスト（qとする）', q)
    # m以下で抑えたいからx <= mの時に
    # qからm-x以下の最大値を得る
    # q = m-xのときはmぴったりになる
    qq = {x + listmax(q, m-x) for x in q if x <= m}
    print('qからmを超えないように2つ選んで足したリスト(qiごとに最大)', qq)
    ans = max(qq)
    print('最大値', ans)
if __name__ == '__main__':
    main()

6.4 Aggressive cows

保留

6.5 億マス計算

出典はこれ。

atcoder.jp

詳細をリンク先をみるとして、制約が結構きつい。

結果として $x$ 以下の数が $k$ 個以上あるような最小のxを求めるということである。　　
なので、まず $x$ 以下の積の数が $k$ 個以上あるかを判定する関数(check())を作る。
この問題では $a \times b \leq k$ は言い換えると $b \leq k//a$ (//は割った値の整数部分)となる。
あとは二分探索であり得る範囲の値、 $0 \leq x \leq 10^18+1$ で $x$ を探す。

入力は以下のような形を想定

from bisect import bisect_right

def main():
    n, k = map(int, input().split())
    A = [int(x) for x in input().split()]
    B = sorted([int(x) for x in input().split()])
    def check(x):
        # x以下の積の数がK個以上
        # a*b <= k　は b <= k//a
        cnt = 0
        for a in A:
            cnt += bisect_right(B, x // a)
        return cnt >= k
    # a. b の最大が10**9
    l = 0
    r = 10**18 + 1
    while r - l > 1:
        m = (r + l) // 2
        # m以下の積の数がK個以上ならmを右端に（現状のmより左側に答えが）
        if check(m):
            r = m
        # m以下の積の数がK個未満ならmを左端に（現状のmより右側に答えが）
        else:
            l = m
    # 全パターンを順番に並べた
    print('全パターンを順番に並べると')
    print(sorted(a * b for a in A for b in B))
    # 最後は右を答える
    print('小さい方から', k, '番目の値', r)
            
if __name__ == '__main__':
    main()

まとめ

二分探索はイメージしやすい。
複数の配列があるなど、探索する量が多い時は、複数の配列の１つを固定する、2つにまとめるなど、うまく工夫が必要。
問題に合わせてbisectで作ることができるチェック用の関数を作ると楽、例えば
- リストからx以下の最大値を得る関数
- $x$ 以下の積の数が $k$ 個以上あるかを判定する関数

終わりに

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

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

2020-10-20

Python3で実装問題解決力を鍛える！アルゴリズムとデータ構造【第５章】設計技法(3)：動的計画法

book_algorithm_solution

「問題解決力を鍛える！アルゴリズムとデータ構造」の章末問題をPython3で実装していくシリーズ。

大枠まとめ記事は、ここに。 blacktanktop.hatenablog.com

前回の記事は、【第４章】設計技法(2)：再帰と分割統治法

blacktanktop.hatenablog.com

今回は【第５章】設計技法(3)：動的計画法について扱うちょっとボリューム多いし、まだ途中。

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

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

内容
【第５章】設計技法(3)：動的計画法の概要
章末問題
まとめ
終わりに

内容

Python3でやっている。
簡単に自分の理解を整理する用。
そこまで厳密ではない可能性が高い。
記事を書いたら、書評の方に記事を載せていく。
コード等はGitHubにおいた。 github.com

【第５章】設計技法(3)：動的計画法の概要

章末問題

5.1 2つの要素をDPで取り扱う

入力は以下を想定して、

$dp[i]$ を $i$ 日目までに得られる幸福度の和の最大値としたいけど、それではダメ。
なぜなら、「連続で同じ行動をとることができない」という制約があるため。
当日に大きい値を選びたいけど、前日選んでたら選べない。
なので、 $dp[i][j]$ のようにして、 $i$ 日目に行動 $j$ をして、 $i$ 日目までに得られる幸福度の和の最大値とする方針で実装する。

def main():
    n = int(input())
    abc = [list(map(int, input().split())) for _ in range(n)]
    # dp[i][0or1or2]のような形にして、i+1日目にある行動をした時の最大値という意味
    # a, b, c = 0, 1, 2 として扱う
    # dp[3][2]なら4日目にCをした時の最大値
    # dpの枠の用意
    dp = [[0] * 3 for _ in range(n)]
    # dpの初期値
    # 1日目の幸福度
    for i in range(3):
        dp[0][i] = abc[0][i]
    print('初期値(1日目)代入', dp)
    # 2日目以降のdpを代入
    # 当日のある行動の値は、前日の当日の行動でない残りのどちらかの行動 + ある行動の値
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][1] + abc[i][0], dp[i-1][2] + abc[i][0])
        dp[i][1] = max(dp[i-1][0] + abc[i][1], dp[i-1][2] + abc[i][1])
        dp[i][2] = max(dp[i-1][0] + abc[i][2], dp[i-1][1] + abc[i][2])
        print(i, '日目の行動を考慮した',  i+1, '日目の行動別最大幸福', dp)
    # dpの最後の値の最大値が幸福度最大
    ans = max(dp[n-1])
    print(n, '日間の幸福度の最大値', ans)
if __name__ == '__main__':
    main()

5.2 部分和問題をDPで解く

$n$ 個の正の整数列 $a$ と正の整数 $w$ と正の整数 $k$ が与えられる。
これらの整数から何個かの整数を選んだ総和が $w$ になるかどうか。

4章と同じく部分和問題なので、入力は以下を想定して、

4 14
3 2 6 5

nn 個の正の整数 a[0],a[1],…,a[n−1]a[0],a[1],…,a[n−1] と正の整数 AA が与えられる。
これらの整数から何個かの整数を選んで総和が AA になるようにすることが可能か判定する。
可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。
$dp[i+1][j]$ は $a$ の(indexとして) $i$ 番目までの整数の中からいくつか選んで総和を $j$ とすることができるかどうか(できるなら1, できないなら0)
初期条件は $0$ 個の整数の和は $0$ なので、 $dp[0][0]$ = 1
を用いて、の値を以下のように更新していく。
- 整数を選ばない場合
  - $dp[i][j]$ が1なら、 $dp[i+1][j]$ = 1
- 整数を選ぶ場合 ( )
  - $dp[i][j-a[i]]$ が1なら、 $dp[i+1][j]$ = 1
これを実装する。
- 入力の数値をindexに合わせる方がいいので、dpのリストはn+1, w+1の多重リストにする。

def main():
    n, w = map(int, input().split())
    a = [int(x) for x in input().split()]
    print('a:', a)
    # dp[i+1][j]はi番目(indexにおいて)までの整数の中からいくつか選んで総和jにできるかという意味
    # dp[3][2]ならaの2番目(indexにおいて)までの整数の中からいくつか選んで合計が2になるなら1とする
    # dpの枠の用意(indexとn, wを合わせるので+1する)
    dp = [[0] * (w+1) for _ in range(n+1)]
    # dpの初期値(0個から0は作れるので)
    dp[0][0] = 1
    # ２重のfor文でO(nw)
    for i in range(n):
        for j in range(w+1):
            # a[i]を選ばない場合
            if dp[i][j]:
                dp[i+1][j] = dp[i][j]
                print(a[:i+1], 'の中の整数のいくつかで', j, 'が作れるか')
                print(dp)
            # a[i]を選ぶ場合
            if j >= a[i] and dp[i][j-a[i]]:
                    # a[i]を選んで成立するには
                    # dp[i][j-a[i]]がTrueである必要がある
                    dp[i+1][j] = dp[i][j-a[i]]
                    print(a[:i+1], 'の中の整数のいくつかで', j, 'が作れるか')
                    print(dp)
    if dp[n][w]:
        print(a[:i+1], 'の中の整数のいくつかで', j, 'が作れるか')
        print('Yes')
    else:
        print(a[:i+1], 'の中の整数のいくつかで', j, 'が作れるか')
        print('No')
    print('forの回転数は', (i+1) * j)
    print('n x w　は', n * w)
    
if __name__ == '__main__':
    main()

5.3 部分和問題（総和として得られる数の種類数）

少し問題が変更。得られる総和が成立するパターン数を数えることで、結果的にどんな値が総和として得られるのかを把握する。 * $n$ 個の正の整数列 $a$ と正の整数 $w$ が与えられる。
* これらの整数から何個かの整数を選んだ総和が $1$ 以上 $w$ 以下の整数が何通りあるかを求めよ。

$dp[i+1][j]$ は $a$ の(indexとして)i番目までの整数の中からいくつか選んで総和をjとすることができる組み合わせの数
初期条件は $0$ 個の整数の和は $0$ なので、 $dp[0][0]$ = 1。他は0
を用いて、の値を以下のように更新していく。
- 整数を選ばない場合
  - $dp[i][j]$ 通りを加える
- 整数を選ぶ場合 ( )
  - $dp[i][j-a[i]]$ 通りを加える。
これを実装する。
$dp[n][w]$ はどの値が、どのくらいの組み合わせ数あるかと言う意味で、今回は1以上のものが得られる数ということになる。
最後に $dp[n][w]$ のリストの中で0でないものをカウントする。ただし、 $dp[n][0]$ の1は除く。

def main():
    n, w = map(int, input().split())
    a = [int(x) for x in input().split()]
    print('a:', a)
    # dp[i+1][j]はi番目(indexにおいて)までの整数の中からいくつか選んで総和jにできる組み合わせの数
    # dp[3][2]ならaの2番目(indexにおいて)までの整数の中からいくつか選んで合計が2になる組み合わせの数
    # dpの枠の用意(indexとn, wを合わせるので+1する)
    dp = [[0] * (w+1) for _ in range(n+1)]
    # dpの初期値(0個から0は作れるので)
    dp[0][0] = 1
    # ２重のfor文でO(nw)
    for i in range(n):
        for j in range(w+1):
            # a[i]を選ばない場合
            dp[i+1][j] += dp[i][j]
            # a[i]を選ぶ場合
            if j >= a[i]:
                dp[i+1][j] += dp[i][j-a[i]]
    print('===============================================')
    print('0以上W以下に一致する組み合わせ数のそれぞれの数は', dp[n])
    print('1以上W以下で作ることができる整数の種類数は', sum([1 for i in dp[n] if i > 0]) - 1)
    print('===============================================')
    print('forの回転数は', (i+1) * j)
    print('n x w　は', n * w)
if __name__ == '__main__':
    main()

5.4 部分和問題（5.2に選べる数に制約があるパターン）

$n$ 個の正の整数列 $a$ と正の整数 $w$ と正の整数 $k$ が与えられる。
これらの整数から $k$ 個の整数を選んだ総和が $w$ になるかどうか。

普通に $dp[n][w][k]$ みたいにやろうとすると、計算量が増えるので、以下のようにやる。

$dp[i+1][j]$ は $a$ の(indexとして) $i$ 番目(indexにおいて)までの整数の中からいくつか選んで総和 $j$ にできる方法をすべて考えたときに選んだ整数の個数の最小値とする。
初期条件は $0$ 個の整数の和は $0$ なので、 $dp[0][0]$ = 0。他はinfとする。（とても大きい数にする）
を用いて、の値を以下のように更新していく。
- 整数を選ばない場合
  - $dp[i][j]$ を代入
- 整数を選ぶ場合 ( )
  - $dp[i][j]$ と $dp[i][j-a[i]] + 1$ の小さい方を代入
これを実装する。

def main():
    n, w, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    print('w', w)
    print('k', k)
    print('a:', a)
    # dp[i+1][j]はi番目(indexにおいて)までの整数の中からいくつか選んで総和jにできる方法をすべて考えたときに選んだ整数の個数の最小値
    # dpの枠の用意(indexとn, wを合わせるので+1する)
    # 
    INF = float('inf')
    dp = [[INF] * (w+1) for _ in range(n+1)]
    # dpの初期値(kは1以上で)
    dp[0][0] = 0
    # ２重のfor文でO(nw)
    for i in range(n):
        for j in range(w+1):
            # a[i]を選ばない場合
            dp[i+1][j] = dp[i][j]
            # a[i]を選ぶ場合
            if j >= a[i]:
                dp[i+1][j] = min(dp[i][j], dp[i][j-a[i]] + 1)
    print('===============================================')
    print(a, 'から', k, '個以下を選んで総和を', w, 'にした時の整数の個数の最小値は', dp[n][w])
    print(a, 'から', k, '個以下を選んで総和を', w, 'にできるか？')
    if dp[n][w] <= k:
        print('Yes')
    else:
        print('No')
    print('===============================================')
    print('forの回転数は', (i+1) * j)
    print('n x w　は', n * w)
if __name__ == '__main__':
    main()

5.5 部分和問題（個数制限なし）

5.6 部分和問題（個数制限あり）

5.9 Slimes

まとめ

DPは漸化式・初期条件をいかにうまく設定するかがポイント
- 5.4みたいに3条件にしちゃうと計算量ふえるから、定義を変えるなど。

終わりに

積極的に、DPの問題は余り解いてこなかったが、パターン分けされていて、頭に入った。コード書くのも少し慣れたが、もう少し時間をかけて取り組む。

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

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

2020-10-18

Python3で実装問題解決力を鍛える！アルゴリズムとデータ構造【第４章】設計技法(2)：再帰と分割統治法

book_algorithm_solution

「問題解決力を鍛える！アルゴリズムとデータ構造」の章末問題をPython3で実装していくシリーズ。

大枠まとめ記事は、ここに。 blacktanktop.hatenablog.com

前回の記事は、【第３章】設計技法(1)：全探索 blacktanktop.hatenablog.com

今回は【第４章】設計技法(2)：再帰と分割統治法について扱う

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

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

内容
【第４章】設計技法(2)：再帰と分割統治法の概要
章末問題
まとめ
終わりに

内容

Python3でやっている。
簡単に自分の理解を整理する用。
そこまで厳密ではない可能性が高い。
記事を書いたら、書評の方に記事を載せていく。
コード等はGitHubにおいた。 github.com

【第４章】設計技法(2)：再帰と分割統治法の概要

ここの章で再帰の考え方。図4.1の概念図がわかりやすくて、最初の流れは、 f(x) = x + f(x-1)でf(0) = 0とすると、
f(5) → f(4)を呼び出し → f(3)を呼び出し → f(2)を呼び出し → f(1)を呼び出し → f(0)を呼び出す。
次の流れは値の返り方で、 f(x) = x + f(x-1)がf(0)から逆流していく感じ
f(0) = 0なので、f(5)は
0 → 1 + 0 → 2 + 1 → 3 + 3 → 4 + 6 → 5 + 10 となり、15が返り値となる。

再帰関数のポイント
ベースケース（再帰の呼び出しを行わないでreturnするケースのこと）の処理が重要。

テンプレート的にはこんなイメージ

# 再帰関数のテンプレート
def recursive(引数):
        if 条件文:
            return 値
    return recursive(次の引数)

注意点は、再起呼び出しを行った時の引数はベースケースになるように（近づくように）設計しないと、無限ループになる。

章末問題

4.1 Tribonacci sequenceを再帰で計算する

入力は0以上の整数値を想定して、以下のコードのtribo_rec()が問題の意図している再帰関数を使った方法。
確認用のためにtribo_list()は配列とfor文を使った方法も書いておいた。 * テンプレート通りに、初期値の３つをベースケースとする。 * 再起呼び出しは、引数の手前の３つを使う(nに対して、n-1, n-2, n-3)

def main():
    def tribo_list(n):
        d = [0] * (n+1)
        # d[0]とd[1]とd[2]を規定。
        d[0] = 0
        d[1] = 0
        d[2] = 1
        # 3~nまでを見る必要がある
        for i in range(3, n+1):
            d[i] = d[i-1] + d[i-2] + d[i-3]
        return d
    def tribo_rec(n):
        if n == 0:
            return 0
        elif n == 1:
            return 0
        elif n == 2:
            return 1
        ans = tribo_rec(n-1) + tribo_rec(n-2) + tribo_rec(n-3)
        return ans
    print('0以上の整数を標準入力するとTribonacci sequenceを出力する')
    n = int(input())
    if n >= 0:
        print('Tribonacci list', tribo_list(n))
        # [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149,
        #  274, 504, 927, 1705, 3136, 5768, 10609, 19513,
        #  35890, 66012, 121415, 223317, 410744, 755476]
        # 項数は0から始まる
        print('再帰によるTribonacci sequenceの第', n, '項の計算の値：', tribo_rec(n), sep='')
        # 755476
    else:
        print('0以上の整数を標準入力するとTribonacci sequenceを出力する')
    
if __name__ == '__main__':
    main()

4.2 再帰関数のメモ化

入力は0以上の整数値を想定して、 4.1を少し変形する。tribo_memo()が意図した再帰関数。

この部分がポイントで、

# メモ作成
memo = [-1] * (n+1)
…
# 再計算をしないように、メモにあるならメモ使う
if memo[n] != -1:
    return memo[n]
memo[n] = tribo_memo(n-1) + tribo_memo(n-2) + tribo_memo(n-3)
return memo[n]

メモ化できるようにリストを作る。
すでに計算した値があれば、メモを利用するようにする。(ここが再計算を減らすポイント)
- メモの全ての初期値は-1なので-1じゃなかったらその値を使う。
メモ化のリストに再起した値を入れる。

def main():
    def tribo_list(n):
        d = [0] * (n+1)
        # d[0]とd[1]とd[2]を規定。
        d[0] = 0
        d[1] = 0
        d[2] = 1
        # 3~nまでを見る必要がある
        for i in range(3, n+1):
            d[i] = d[i-1] + d[i-2] + d[i-3]
        return d
    def tribo_memo(n):
        memo = [-1] * (n+1)
        if n == 0:
            return 0
        elif n == 1:
            return 0
        elif n == 2:
            return 1
        if memo[n] != -1:
            return memo[n]
        memo[n] = tribo_memo(n-1) + tribo_memo(n-2) + tribo_memo(n-3)
        return memo[n] 
    print('0以上の整数を標準入力するとTribonacci sequenceを出力する')
    n = int(input())
    if n >= 0:
        print('Tribonacci sequence', tribo_list(n))
        # [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149,
        #  274, 504, 927, 1705, 3136, 5768, 10609, 19513,
        #  35890, 66012, 121415, 223317, 410744, 755476]
        # 項数は0から始まる
        print('メモ化しながら再帰によるTribonacci sequenceの第', n, '項の計算の値：', tribo_memo(n), sep='')
        # 755476
    else:
        print('0以上の整数を標準入力するとTribonacci sequence出力する')
if __name__ == '__main__':
    main()

4.3 Fibonacci sequenceの一般項

フィボナッチ数列は三項間漸化式なので，特性方程式を用いて一般項を求めることができる。
ビネの公式っていうらしい。
漸化式を等比数列に帰着させて解けばいい。

漸化式： $a_n=a_{n−1}+a_{n−2}$ を $a1=a2=1$ の元で解く。

特性方程式は漸化式より、 $x^2=x+1$ である。

$x^2=x+1$ の解を $α=\frac{1+\sqrt{5}}{2}, β=\frac{1-\sqrt{5}}{2}$ とおく。

$α+β=1, αβ=−1$ であるので、

$a_n=(α+β)a_{n−1}+(αβ)a_{n−2}$

上記の式を変形すると、 $a_n - αa_{n-1} = β(a_{n−1} -αa_{n−2})$ となる。

よって、 $a_n - αa_{n -1}$ は公比 β の等比数列である。

以下の式から $a_{n-1}$ を消して、 $a_{n}$ について解く。

$a_n - αa_{n -1}$ = $β^{n−2}(a_2−αa_1)=β^{n−1}$

$a_n - βa_{n -1}$ = $α^{n−2}(a_2−βa_1)=α^{n−1}$

$a_n=\frac{α^n−β^n}{α−β}=$ ${\displaystyle\frac{1}{\sqrt{5}}\{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n\}}$

pythonにはSymPyというsolverモジュールがあるので、今回これを使って、漸化式の一般項を求めてみた。
(動かす場合はSymPyをインストールする必要あり)
さらに、その一般項を用いて、検算をしてFibonacci sequenceを求めた。

python solution_4_3.py とEnterした後、少し時間がかかる。

import sympy as sym
def main():
    # 一般項f(n)
    fn = sym.simplify("f(n)")
    # 左辺が0になるように漸化式を書く
    y = sym.simplify("f(n)-f(n-1)-f(n-2)")
    # 初期条件
    init = sym.simplify({"f(0)": 0, "f(1)": 1})
    # 初期条件iniの漸化式sをfについて解く
    fib_n = sym.rsolve(y, fn, init)
    print('Fibonacci sequenceの一般項の式は')
    print(fib_n)
    print('------------------------------')
    # -sqrt(5)*(1/2 - sqrt(5)/2)**n/5 + sqrt(5)*(1/2 + sqrt(5)/2)**n/5

    def fib_g(n):
        x = sym.symbols('x', nonnegative=True, integer=True)
        fib = -sym.sqrt(5)*(1/2 - sym.sqrt(5)/2)**n/5 + sym.sqrt(5)*(1/2 + sym.sqrt(5)/2)**n/5
        # fibの式のxにnを代入
        formula = fib.subs(x, n)
        ans = int(sym.simplify(formula))
        print(formula, '=', ans)
        return ans
    print('0以上の整数を標準入力するとFibonacci sequenceの一般項の式と検算結果を出力する')
    n = int(input())
    print('検算結果')  
    print('第', n ,'項までの', 'Fibonacci sequence', [fib_g(n) for n in range(0, n)], sep='')

if __name__ == '__main__':
    main()

4.4 Fibonacci Sequenceの計算量

コードはない。一般項から考えると、
${\displaystyle\frac{1}{\sqrt{5}}\{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n\}}$ は線形和であり、第２項は $n→∞$ とすると0へ収束するので、
$O((\frac{1+\sqrt{5}}{2})^n)$

4.5 753数

適当な正の整数の入力をを想定する。

再帰関数のテンプレートで考える。
ベースラインは入力値を数値化した時の値よりも大きくなったら0を返す。
入力されたものが753数ならcnt=1とする。
再起呼び出しは入力された値に'7', '5', '3'をそれぞれ右側からくっつけたものとして、cntをインクリメントする。
初期値は''(空文字)にしたいけど、intにできなくて止まるので'0'とする。
- Pythonではint('0123')とすると整数の123となる

def main():
    n = int(input())
    m = len(str(n))
    def dfs(A):
        # nよりも大きくなったら0を返す
        if int(A) > n:
            return 0
        # 入力されたものが753数ならcnt=1としていく
        cnt = 1 if all(A.count(c) > 0 for c in '753') else 0
        # 実際に用件を満たすような文字列の出力
        if cnt == 1:
            print(A[1:])
        for i in '753':
            cnt += dfs(A + i)
        return cnt
    print('入力値', n, 'の753数は', dfs('0'))
if __name__ == '__main__':
    main()

4.6 部分和問題をメモ化をつかった再帰関数にする

例題と同じく、こんな入力を想定して、

4 14
3 2 6 5

コメントアウトしたけど、ただの再帰関数を用いたものを用意した。（f_rec()）これを、メモ化していく。ポイントはベースケースのところで

メモリストにある場合はそれを返す。
f_rec()ではそのまま返していた値も、メモリストへ代入する。

def main():
    def f_memo(i, w, A):
        if i == 0:
            if w == 0:
                return True
            else:
                return False
        # すでにメモに計算結果がが合ったらそのメモの値を返す        
        if memo[i][w] != -1:
            # print('メモ利用', 'i=', i, 'w=', w, 'A[i]=', A[i])
            return memo[i][w]
        if f_memo(i-1, w, A):
            memo[i][w] = True
            print('i =', i, 'w =', w, 'A[', i-1, ']=', A[i-1], 'を選ばない')
            return memo[i][w]
        if f_memo(i-1, w-A[i-1], A):
            memo[i][w] = True
            print('i =', i, 'w =', w, 'A[', i-1, ']=', A[i-1], 'を選ぶ')
            return memo[i][w]
        memo[i][w] = False
        return memo[i][w]

    n, w = map(int, input().split())
    a = [int(x) for x in input().split()]
    # 1つのリストの要素数がw, それがn個ある多重リスト
    memo = [[-1]*(w+1) for _ in range(n+1)]
    if f_memo(n, w, a):
        # print(memo)
        print('Yes')
    else:
        # print(memo)
        print('No')
    # # 元のただの再帰関数
    # def f_rec(i, w, A):
    #     if i == 0:
    #         if w == 0:
    #             return True
    #         else:
    #             return False
    #     if f(i-1, w, A):
    #         return True
    #     if f(i-1, w-A[i-1], A):
    #         return True
    #     return False
    # n, w = map(int, input().split())
    # a = [int(x) for x in input().split()]
    # if f(n, w, a):
    #     print('Yes')
    # else:
    #     print('No')

if __name__ == '__main__':
    main()

まとめ

再帰はベースケースの処理が重要。
テンプレートを上手く使う。
メモ化しないと計算量が増えるので基本メモ化する。

終わりに

再帰とは関係ないけど、久しぶりに三項間漸化式における特性方程式を用いて一般項を求めた。
再帰は結構値が返ってこないまま次の処理に回して、後から答えが返ってくるので、イメージがしづらいが今回のケースを通じて理解が深まった。

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

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

2020-10-17

Python3で解く AtCoder Beginner Contest 180 D - Takahashi Unevolvedff

AtCoder 競プロ ABC-D 400点

条件を検討すると、 $x \times a$ 増えるか $b$ 増えるかで小さい方を選びたいってことに気付ければなんとかなる。

概要

問題

初期の強さは $x$ 、経験値は $0$
カコモンジムに通う：強さが $a$ 倍になり、経験値は $1$ 増える。
AtCoderジムに通う：強さが $b$ 増え、経験値は $1$ 増える。
経験値は $y$ を超えないように特訓した場合、最大の経験値は？

解くときに考えた内容

条件的に、 $x \times a$ 増えるか $b$ 増えるかで小さい方を選びたい。なので、以下の手順になる。

$x \times a$ が $b$ よりも小さいかつ $x \times a$ が $y$ よりも小さいなら、カコモンジムに通う。
残りの経験値は $y$ から初期の経験値とカコモンジムに通って得た経験値を引いた値。
それを超えないようにAtCoderジムに通う。
ここは割り算処理するのでぴったりの処理だけ気をつける。
今回は残りの経験値から $1$ 引いたものを $b$ で割った整数部分をAtCoderジムに通った数とした。

コード

x, y, a, b = map(int, input().split())
a_cnt = 0
while (x*a) < b and (x*a) < y: 
    x *= a
    a_cnt += 1
b_cnt = (y-x-1) // b
ans = a_cnt + b_cnt
print(ans)

参考になる書籍

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

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

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

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

章末問題を解いてる。まだ途中。 blacktanktop.hatenablog.com

2020-10-17

Python3で解く AtCoder Beginner Contest 180 C - Cream puff

AtCoder 競プロ ABC-C 300点約数列挙

問題の意図的に約数を列挙すればいい。

概要

問題

$n$ が与えられる。
$n \div i$ とした時に割り切れる $i$ を全て列挙できる？

解くときに考えた内容

文意から、約数列挙するだけ。
約数列挙は手元に関数があるので、それの復習。
検索範囲は $1$ から $\sqrt{n}$ 以下
$n$ が $i$ で割り切れたら、lowerに加える。
割った結果が $i$ と異なる場合はupperに加える。
intでほしいので演算子は//
最後にリストを合体させる。(一応順番にするためにupperを逆順にしてる)
- 出力が行だから、アンパックして改行。

コード

def divisors(n):
    lower, upper = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower.append(i)
            if i != n // i:
                upper.append(n//i)
        i += 1
    return lower + upper[::-1]
n = int(input())
ans = divisors(n)
print(*ans, end='\n')

参考になる書籍

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

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

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

章末問題を解いてる。まだ途中。 blacktanktop.hatenablog.com

2020-10-17

AtCoder Beginner Contest 180 参加ログ・感想

参加ログ AtCoder 競プロ式の実装約数列挙

今日は、飲み始めてたんだけど、急に開催と気づいてまぁ気軽にやるかと思ったんだけど、ABCD完（Dで10ペナもしちゃったけど）

けんちょんさんの本で勉強しているおかげか？！

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

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

内容
結果
どう考えたか + α
おわりに

内容

Python3でやっている。
参加ログ。
所感。
コンテスト中に何を考えたか。
コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
問題の詳細で細かく書こうと思うものは別記事とする。
E以上はとりあえず現状自力では無理なのでDまで。解けるようになってきたら更新するかも

結果

ABCD完。これまでよりも比較的簡単な印象ではあった。 Bは実装するだけで、Cは約数列挙とすぐ気づいた。Dは最初はどっちかの訓練を選ぶだけと思ったが、そうではなく経験値が倍数方向のに増える方が経験値が足算方向に増えるよりも小さいときは倍数方向の訓練、大きくなってしまうなら、足算方向の訓練ってかんがえればできたが、while文の条件をミスって最後の最後にようやく気づいて駆け込みABCD完。久しぶりにいいfinish

どう考えたか + α

A - box

問題タイプ：足し算と引き算

n, a, b = map(int, input().split())
ans = n - a + b
print(ans)

B - Various distances

問題タイプ：式の実装そのまま、計算式を実装する。

n = int(input())
x = [int(i) for i in input().split()]
Manhattan  = 0
Euclidean = 0
Chebyshev = - 10**5 - 1
for i in x:
    Manhattan  += abs(i)
    Euclidean += i ** 2
    Chebyshev  = max(abs(i), Chebyshev )
print(Manhattan)
print(Euclidean ** (1/2))
print(Chebyshev)

C - Cream puff

問題タイプ：約数列挙

問題の意図的に約数を列挙すればいい。約数列挙のポイントは、 * 素数の時と同様に $\sqrt(n)$ まで見れば良い * 試し割りしていった値が割れるなら、リストに加える。さらに、その値で割った結果もリストに加えていくこと。
別記事にする。

追記：

blacktanktop.hatenablog.com

D - Takahashi Unevolved

問題タイプ：最適条件を見つける感じ？

$x * a$ が $b$ よりも小さいかつ $x * a$ が $y$ よりも小さいなら、カコモンジムに通う（ $x$ を $a$ 倍していく方）。残りはAtCoderジムに通う。ここは割り算処理するのでぴったりの処理だけ気をつける。別記事にする。

追記：

blacktanktop.hatenablog.com

おわりに

久しぶりのABCD完。嬉しい。Highestになったけど、まだまだ沼に使っている・・・。定常的にこのくらいはできるようになりたい。

引き続き、精進と書籍のまとめ続けていこう。

blacktanktop.hatenablog.com

2020-10-16

【書評】問題解決力を鍛える！アルゴリズムとデータ構造

書籍紹介 AtCoder 競プロ book_algorithm_solution

「問題解決力を鍛える！アルゴリズムとデータ構造」を読んだので感想を書く。

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

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

書籍の概要と感想
章末問題の概要
まだ章末問題やっている最中の章
終わりに

書籍の概要と感想

待ちに待った、けんちょんさんの「問題解決力を鍛える！アルゴリズムとデータ構造」。ページを進めるたびに感動する。絵がたくさんあって、解説コードもたくさんあって、超絶わかりやすい!!! いくつかページを載せたいくらいだけど、載せられないので書き記すと、個人的に特にわかりやすかったところは、

設計技法
- 再帰
- DP
- にぶたん
- 貪欲
データ構造
- グラフと木
- Union-Find
グラフ

結局全部！っていう。それくらいどの章も絵とコードによる説明があって非常によかった。まだ始めたばかりで、グラフについてはおぼろげな感じで、この書籍を読んで理解が深まったので、実際に実装を踏まえて身につけていきたい。また、競技プログラミングはPythonかJuliaでやっているので、C++をほぼ知らないが、それでもC++のハンドリング覚えられるくらい丁寧に書かれているのもよかった。（副産物的にC++の基本がおさえられて個人的にはよかった。）

難易度てきには広くおさえられていて、全体的にこのくらいは知ってましょうねって言う感じなんだと思うので初心者~中級者向けって言うところなんだと思う。

ご本人が書籍のターゲットとか難易度とかも記しているのでそちらの方が確かかも。

drken1215.hatenablog.com

章末問題の概要

章末問題を解いたものの別記事載せて、その章ごとに概要を追記していく。とりあえず３章から別記事にて実際にコードを書く。

第１章アルゴリズムとは

深さ優先探索や幅優先探索・マッチングなどの具体的な例をだして、アルゴリズムの解説がされている。ここで、「問題に対する具体的な解を書き下すことができなくても解を得るための「手順」を与えることができればよい」ということが書かれていて、たしかにそうだなぁと思った。

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

計算量の計算の解説が具体例と共にめちゃわかりやすく書かれている。たとえば、年齢当てゲームで、線形探索でやった場合と二分探索で0歳以上65536歳未満を範囲とした時に、最悪ケースの回数には大きな差があることを紹介している。また１秒間で処理できる処理数はC++では $10^9$ 程度らしい。（CPUにもよるだろうが著者はMacBook Air Early2015でやっているようだ。）自分の環境ではPythonでは $1.5 \times 10^7$ 程度。(MacBook Pro Late 2016）

特にいい表は表2.2で、CPUなどにも左右されるが、競技プログラミング的な制約では処理数としてPythonでは $3 \times 10^7$ を超えそうならTLEと思ってた方が無難。（numpyなどその他の高速化をすれば別だけど。）なので、実際に使う言語などで、処理数を考えて $O(n)$ でやらなきゃなのか $O(log(n))$ でやらなきゃなのかなどを考える指標になる。

第３章設計技法(1)：全探索

詳細は、以下の記事に書いた。

blacktanktop.hatenablog.com

線形探索・ペアの探索・組み合わせの探索について取り扱っていて、組み合わせの探索はbitを使うので、初心者は慣れないとちょっときつい。

第４章設計技法(2)：再帰と分割統治法

詳細は、以下の記事に書いた。

blacktanktop.hatenablog.com

ベースケース（再帰の呼び出しを行わないでreturnするケースのこと）の処理に気をつけて、実装することを心がける。最大公約数の関数を作るときなどに再帰を使うといい。

第５章設計技法(3)：動的計画法

詳細は、以下の記事に書いた。

blacktanktop.hatenablog.com

DPの漸化式、初期条件を問題の制約に合わせて上手に設計することがポイント。せめて２重のリストで対応できるようになると解ける問題の幅が膨らむ。

第６章設計技法(4)：二分探索法

詳細は、以下の記事に書いた。

blacktanktop.hatenablog.com

複数の配列があるなど、探索する量が多い時は、複数の配列の１つを固定する、2つにまとめるなど、うまく工夫が必要。
問題に合わせてbisectで作ることができるチェック用の関数を作ると楽、例えば、

リストからx以下の最大値を得る関数
x以下の積の数がk個以上あるかを判定する関数

まだ章末問題やっている最中の章

以下の章はまだ別記事でまとめてないので保留。

第７章設計技法(5)：貪欲法

コードはGitHubに書いた

ここからあとは、AtCoderで問題が解けるものを基本扱うようにする。

第８章データ構造(1)：配列、連結リスト、ハッシュテーブル

第９章データ構造(2)：スタックとキュー

第１０章データ構造(3)：グラフと木

第１１章データ構造(4)：Union-Find

第１２章ソート

第１３章グラフ(1)：グラフ探索

第１４章グラフ(2)：最短路問題

第１５章グラフ(3)：最小全域木問題

第１６章グラフ(4)：ネットワークフロー

第１７章 PとNP

第１８章難問対策

終わりに

書籍に関しては、めっちゃわかりやすくて期待通り。自分がAtCoderはじめて間もないタイミングでこの本を読めることはめっちゃよかった。

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

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

現状、章末問題をPythonでこなしていこうと思っている。難易度が高いものはテータ構造・グラフあたりから厳しくなりそうだがやれるだけやってみる。

あと正直なところ、これとは別に初心者向けに、競技プログラミングに必要な数学知識実践編的な物が欲しい。個人的にはまとめているが、数学的に当たり前みたいなものが、ガンガンでてきて「知らんがな」「気づかねー」ってなることが結構あって、どうすればいいのかなーと思っている。

内容

【第６章】設計技法(4)：二分探索法の概要

章末問題

6.1 座標圧縮

6.2 Snuke Festival

6.3 ダーツ

6.4 Aggressive cows

6.5 億マス計算

まとめ

終わりに

内容

【第５章】設計技法(3)：動的計画法の概要

章末問題

5.1 2つの要素をDPで取り扱う

5.2 部分和問題をDPで解く

5.3 部分和問題（総和として得られる数の種類数）

5.4 部分和問題（5.2に選べる数に制約があるパターン）

5.5 部分和問題（個数制限なし）

5.6 部分和問題（個数制限あり）

5.7 最長共通部分列問題

5.8 区間DP

5.9 Slimes

まとめ

終わりに

内容

【第４章】設計技法(2)：再帰と分割統治法の概要

章末問題

4.1 Tribonacci sequenceを再帰で計算する

4.2 再帰関数のメモ化

4.3 Fibonacci sequenceの一般項

4.4 Fibonacci Sequenceの計算量

4.5 753数

4.6 部分和問題をメモ化をつかった再帰関数にする

まとめ

終わりに

目次

概要

解くときに考えた内容

コード

参考になる書籍

目次

概要

解くときに考えた内容

コード

参考になる書籍

内容

結果

どう考えたか + α

A - box

B - Various distances

C - Cream puff

D - Takahashi Unevolved

おわりに

書籍の概要と感想

章末問題の概要

第１章 アルゴリズムとは

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

第３章 設計技法(1)：全探索

第４章 設計技法(2)：再帰と分割統治法

第５章 設計技法(3)：動的計画法

第６章 設計技法(4)：二分探索法

まだ章末問題やっている最中の章

第７章 設計技法(5)：貪欲法

第８章 データ構造(1)：配列、連結リスト、ハッシュテーブル

第９章 データ構造(2)：スタックとキュー

第１０章 データ構造(3)：グラフと木

第１１章 データ構造(4)：Union-Find

第１２章 ソート

第１３章 グラフ(1)：グラフ探索

第１４章 グラフ(2)：最短路問題

第１５章 グラフ(3)：最小全域木問題

第１６章 グラフ(4)：ネットワークフロー

第１７章 PとNP

第１８章 難問対策

終わりに

第１章アルゴリズムとは

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

第３章設計技法(1)：全探索

第４章設計技法(2)：再帰と分割統治法

第５章設計技法(3)：動的計画法

第６章設計技法(4)：二分探索法

第７章設計技法(5)：貪欲法

第８章データ構造(1)：配列、連結リスト、ハッシュテーブル

第９章データ構造(2)：スタックとキュー

第１０章データ構造(3)：グラフと木

第１１章データ構造(4)：Union-Find

第１２章ソート

第１３章グラフ(1)：グラフ探索

第１４章グラフ(2)：最短路問題

第１５章グラフ(3)：最小全域木問題

第１６章グラフ(4)：ネットワークフロー

第１８章難問対策