再帰関数で作るフラクタル図形 ~コッホ曲線~
今回はフラクタル図形の各頂点の座標を求める問題に挑戦していきたいと思います．再帰関数の理解を深めるのにちょうどいい問題でしたのでぜひ挑戦してみてください．
目次
フラクタル図形とは
図形の部分と全体が自己相似（再帰）によってできているものをフラクタルと呼ぶそうです(wiki参照).
シェルピンスキーのギャスケット(初めて名前知りました…)がみなさん見たことあるフラクタル図形の一つだと思います．
フラクタル図形は自然界にもたくさんある形です．こういった幾何学模様は不思議な魅力があって綺麗に見えますよね.
コッホ曲線
コッホ曲線は先ほど説明したフラクタル図形の一つです.
線分を3等分し、分割した2点を頂点とする正三角形の作図するということを無限に繰り返すことによって得られる図形を指しています.
画像参考サイト
正三角形からこのコッホ曲線を描くと雪片のようになることでも有名です.
問題
今回扱う問題はALDS1_5_C: Koch Curveになります．
問題の内容としては入力nを受け,深さnの再帰呼び出しによって作成されるコッホ曲線の頂点の座標を出力するというものです.
作らなければならない動作としては
- 与えられた線分(p1, p2)を三等分にする
- 線分を三等分する2点(s, t)を頂点とする正三角形(s, t, u)を作成し，その座標を求める
- 新しくできた全ての線分[(p1, s),(s, u), (u, t), (t, p2)]に対して上記の処理を再帰的に繰り返す．
コード&解説
n=1の時は直感的にuの座標がわかると思うのですが，nが増えていくに連れてわかりづらくなると思います． (自分はここで詰まりました…)
ここで，点uの座標を求めるのに使うのが回転行列です．
原点中心に θ 回転して点 (x, y) が (x ', y ') に写るとすると、図形的考察または三角関数の加法定理より、x', y ' は以下のように表されることが分かる。
x'= x cosθ - y sinθ
y'= x sinθ + y cosθ
wiki参照
また，図形的考察をしてくれているサイトもあるのでこちらも参考にしてみてください(参考サイト).
では，これらの知識を活用して上記であげた動作をするプログラムを実装していきましょう.
import mathdef koch(n, p1, p2): if n == 0: return sx = 2p1[0]/3 + p2[0]/3 sy = 2p1[1]/3 + p2[1]/3 tx = p1[0]/3 + 2p2[0]/3 ty = p1[1]/3 + 2p2[1]/3 ux = (tx - sx)math.cos(math.radians(60)) - (ty - sy)math.sin(math.radians(60)) + sx uy = (tx - sx)math.sin(math.radians(60)) + (ty - sy)math.cos(math.radians(60)) + sy koch(n-1, p1, [sx, sy]) print(sx, sy) koch(n-1, [sx, sy], [ux, uy]) print(ux, uy) koch(n-1, [ux, uy], [tx, ty]) print(tx, ty) koch(n-1, [tx, ty], p2)
n = int(input()) #問題文より，端点がp1 = (0,0), p2 =(100,0)と指定されている p1 = [0, 0] p2 = [100, 0] print(p1[0], p1[1]) koch(n, p1, p2) print(p2[0], p2[1])
上記のコードを実行することでp1から順に繋がった形で線分の座標を出力することができます．
点uの座標を求める方法を考えるのに苦労しましたがコードにすると意外と簡潔になりますね．
再帰関数に関してはこの前
やったばかりなのでお手の物でした！
Pythonを使ってこれらの図形を実際に描くこともできるそうなので今度試してみたいと思います．
pythonで部分集合を探索する方法3選
前回の再帰に関する記事で組み合わせの列挙を扱いました．他の方法でも解いたみたいと考え，今回の記事を作成するに至りました．
目次
部分集合の問題って何？
部分集合を扱った問題がどのような問題なのかをまず解説していきます．
問題
n個の要素を持つ配列Aの要素を0個以上足し合わせることで作ることのできる整数を全て列挙してください．
このような問題があった時考えなければいけないのが足し合わせることのできる全ての配列要素の組み合わせを列挙し，それらの組み合わせを計算し，出力するということが考えられると思います．
このような組み合わせの列挙には配列の中の要素を選択するか，しないかという処理を全ての要素に行い，組み合わせを作ることでできます．
今回はこういった場合の組み合わせの列挙を3つの方法で作っていきたいと思います．
最後にはこういった組み合わせを使った問題を実際に解いてみたいと思います．
まずは選択する(1), しない(0)のリストをそれぞれの方法で作っていきます.
再帰関数を使った方法
まず，一つ目が自分で組み合わせを作り上げていくプログラムになります．再帰関数を用いて実際に自分で作るので実装力は身につくかもしれませんが，競技プログラミングなどではコードを書く速度を求められるのであまりお勧めはできません．
勉強がてら作ってみたいという人は挑戦してみてください.
def comb(i, A, ans): if i == n: ans.append(list(A)) return comb(i+1, A, ans) A[i] = 1 comb(i+1, A, ans) A[i] = 0 n = 5 A = [0]*n ans = [] comb(0, A, ans) print(ans)
出力
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 1, 0], [0, 0, 0, 1, 1], ・ ・ ・ [1, 1, 1, 1, 0], [1, 1, 1, 1, 1]]
itertoolsを使った方法
二つ目が，itertoolsを用いた方法です．pythonの標準ライブラリの一つで効率的なループ処理を行ってくれます．
よく使うものとしては順列(n!)，組み合わせの数(nCr)がありますが，その他にもたくさんのことができるので気になる方はこちらから確認してみてください．
今回のような問題に使えるのがこのitertoolsの中の"product"になります．
上記で作成したような配列を一瞬で作ることができます．
出力に関しては似たような形なので省略します．
import itertools n = 5 print(list(itertools.product(range(2), repeat = n)))
bitを使った方法
三つ目が，二進数(bit)を用いた方法です．bitでこのような組み合わせを探索することをbit全探索というような呼び方をしたりします．
整数を2進数表記に変えてくれるpythonの組み込み関数binを用いることでbitの文字列を作ることができます．
今回の組み合わせは選択するかしないか，つまり，0と1で表現できます．
この特性を生かして全組み合わせをbitで表現することができます．
bin()では先頭に "0b" が付いた形で出力されるのでそこだけ注意しましょう.
n = 5 ans = [] for i in range(2**n): ans.append(bin(i)[2:].zfill(n)) print(ans)
これら三つの方法それぞれ出力の形式がリスト，タプル，文字列と異なりますが，似たような処理で扱うことができるので探索方法として紹介しました．
最後にどういった問題を解くことができるのか実際に解くことで解説していきたいと思います.
実践編
今回はAtCoderの問題:C-たくさんの数式を使っていきたいと思います．
問題文
1 以上 9 以下の数字のみからなる文字列Sが与えられます． この文字列の中で,あなたはこれら文字と文字の間のうち,いくつかの場所に + を入れることができます.一つも入れなくてもかまいません. ただし,+ が連続してはいけません.
このようにして出来る全ての文字列を数式とみなし,和を計算することができます.
ありうる全ての数式の値を計算し,その合計を出力してください.
制約
1≤|S|≤10
Sに含まれる文字は全て 1 〜 9 の数字
解答コード
S =input() ans_list = [] if len(S) == 1: print(int(S)) else: for i in range(2**(len(S)-1)): comb = bin(i)[2:].zfill(len(S)-1) num_list = [] num = S[0] for i in range(len(comb)): if comb[i] == "1": num_list.append(int(num)) num = S[i+1] else: num += S[i+1] num_list.append(int(num)) ans_list.append(sum(num_list)) print(sum(ans_list))
今回扱った問題では入力Sの間に"+"を入れるかどうかという組み合わせを列挙し，実際にその組み合わせによってできた数式を計算することで答えにたどり着くことができると思います．
ビットシフトの考え方を使うことでもっとコードを短く書くこともできますが，直感的な理解のためにこのような形で書いてみました．
コードを順番にさらっていけば理解できると思うのでもし扱った問題が解けなければ上記のコードを参考にしてみてください.
また，zfill()はゼロ埋めのことで
例えば，("1").zfill(3)としたら"001"となります．このように指定した文字列の長さにするために左側に0を埋めてくれます．
今回は部分集合をpythonでどう作るかということを解説してきました．
こんな方法が他にもあるよだったり，もっとこうした方が簡単だよというようなことがありましたら，コメントよろしくお願いします．
組み合わせの列挙で学ぶ再帰関数
こんにちは，今回もプログラミングコンテスト攻略のためのアルゴリズムとデータ構造をPythonを用いて実装しながら，解説していきたいと思います．
目次
再帰・分割統治法
問題を解く時に，部分的に問題を解く関数を用意することで与えられた元の問題を解いていくテクニックの一つが分割統治法です．
再帰関数とは，関数の中で自分自身をさらに呼び出すような関数のことを言います．
全探索の問題
今回は全探索の問題を再帰を使って解いていきたいと思います．実際により効率的に解こうと思えば，他の方法もありますが，再帰に慣れるため計算時間のかかる方法で解いています．
問題文は以下の通りです．
長さnの数列Aと整数mに対して，配列Aの要素の中のいくつかの要素を足し合わせてmが作る事ができるかどうかを判定するプログラムを作成してください．Aの各要素は一度だけ使う事ができます．
入力：一行目にn,二行目にAを表すn個の整数,
三行目にq，四行目にq個の整数m_iが与えられます.
出力：整数mを作る事ができれば"yes",できなければ”no”
制約：n ≦ 20
q ≦ 200
1 ≦ Aの要素 ≦ 2000
1 ≦ 整数m ≦ 2000
対応する問題はALDS1_5_A:Exhaustive Searchです．
組み合わせ列挙の関数
今回は全探索で判定を行うようなプログラムを作成していきたいと考えているので，その要素を使うか使わないかを示した全組み合わせが必要になります．
まずが，要素の組み合わせを列挙するような関数をまず作ってみたいと思います．
#n=5の時の組み合わせ def comb(n): A = [0]*n select(0,A) def select(i, A): if i == n: print(A) return select(i+1, A) A[i] = 1 #A[i]を選択 select(i+1, A) A[i] =0 #A[i]を選択しない n = 5 comb(n)
これで組み合わせの列挙はできるようになりました．
また，要素の組み合わせをpythonで作る場合より効率的な方法がいくつかあるので別記事で紹介しています．
全探索を解くためのプログラム
次にこの組み合わせの中で整数mを作ることができるかどうかチェックするプログラムを作成します．
これは先ほどのプログラムのA[i]を選択するかしないかの部分を書き換えていくことで作成することができます．
n = 5 A = [1,5,7,10,21] q = 4 m = [2,4,17,8] def solve(i,m): if m == 0: return 1 if i >= n: return 0 rec = solve(i+1,m) or solve(i+1, m - A[i]) return rec for i in m: if solve(0,i): print("yes") else: print("no")
このプログラムを一般化することでこの問題は解くことができます．
問題の解答
では，問題に答えられるように形を整えていきます．
n = int(input()) A = list(map(int,input().split())) q = int(input()) m = list(map(int,input().split())) sumA = sum(A) def solve(i,m): if m == 0: return 1 if i >= n: return 0 rec = solve(i+1,m) or solve(i+1, m - A[i]) return rec for i in m: if i >= sumA: print("no") else: if solve(0,i): print("yes") else: print("no")
※Pythonで問題を解く場合，整数mが配列Aの総和より大きい場合再帰関数に飛ばさないという分岐を作成する必要があります．
このアルゴリズムは選択するかしないかというのを各配列の要素に聞くような再帰関数を用いています．そのため，計算量はO（2n）となっており，nが小さい場合にしか活用することができません．
今後さらに章を進めていく中でもっと効率的なアルゴリズムがでてくるので，まずは全列挙が簡単に作れるようにマスターしましょう．
実装して学ぶ基本探索アルゴリズム ~二分探索の応用~
解答部分だけに興味がある方は二分探索による実装からみてください
目次
基本探索アルゴリズムの応用問題
今回扱うのはALDS1_4_D:Allocationです．
最大積載量が決まっているトラックに対して荷物をどう割り当てるかというのがこの問題の趣旨になります．
詳しく問題文を読み解いていきます．.
重さがそれぞれw_i(i = 0, 1,…, n-1)のn個の荷物をk台のトラックに積みます．トラックには荷物はいくらでも載せられますが，最大積載量Pを超えられません．この時の最大積載量Pの最小値を求めるという問題になります．
制約は
- 1 ≦ n ≦ 100000
- 1 ≦ k ≦ 100000
- 1 ≦ w ≦ 10000
となっています．
線形探索による実装
まず，問題を解く時に考えられるのが線形探索の考え方を使い，最大積載量Pを0から増やしていき，その時に荷物を積み切ることができるかどうか調べていくということが考えられます．
では，線形探索を用いて実装していきます．
#Pの時に必要なトラックの数を求める関数 def unit_check(n, k, w_list, P): i = 0 for j in range(k): weight = 0 while weight + w_list[i] <= P: weight += w_list[i] i += 1 if i == n: return 1 return 0 n, k = map(int,input().split()) w_list = [0] * n for i in range(n): w_list[i] = int(input()) P = max(w_list) - 1 flag = 0 while flag == 0: P += 1 flag = unit_check(n,k,w_list,P) print(P)
このコードの提出結果は次のようになります．
二分探索による実装
前述のコードの結果を見ると問題自体は解けているようですが，計算時間が間に合わないことがわかります．
ここで注目して欲しいところが，Pの値を一つずつ増やしているという部分です．
基本的には P で積載できなければ P+1 でも積載できない可能性が高いので，Pの値を大きく動かしながら探索した方が検討をつけやすいことがわかると思います．
そこで，これまでに学んだ二分探索を使ってPの値を作成する部分を調整してみましょう．
では，早速実装していきます．
#Pの時に必要なトラックの数を求める関数 def unit_check(n, k, w_list, P): i = 0 for j in range(k): weight = 0 while weight + w_list[i] <= P: weight += w_list[i] i += 1 if i == n: return 1 return 0 n, k = map(int,input().split()) w_list = [0] * n for i in range(n): w_list[i] = int(input()) left = 0 #荷物の最大数x荷物の最大の重さ right = 100000*10000 while left+1 < right: mid = (left+ right)//2 check = unit_check(n, k, w_list, mid) if check == 1: right = mid else: left = mid print(right)
このコードでの提出結果
コード解説
まず，rightの初期値ですが，荷物の最大数x荷物の最大の重さとすることで k=1 の時でもトラックに全ての荷物を積むことができるので，このような値を取っています．
"while left + 1< right" の部分に関しては今回はleftとrightが共存するということがなく,"while left < right"とするとループを抜けられなくなってしまうのでこのようになっています．
最後にrightを出力しているのはunit_checkで"1"が帰ってきている中で最小のものが答えなのでwhileを抜けた時のrightが答えになっています．
コードの中身に関してこうした方がいいやここがわからないなどあればコメントよろしくお願いします！
実装して学ぶ基本探索アルゴリズム ~線形探索と二分探索~
目次
探索とは
データ集合の中から目的の要素を探し出す処理のことです．
競技プログラミングでは与えられた配列に対して処理を行うことが多いので，覚えておくべきものの一つになります．
その中でも基本となるアルゴリズムは線形探索，二分探索，ハッシュ法になります．
では，早速それぞれのアルゴリズムの説明と実装に移っていきます．
線形探索(Linear Search)
配列の先頭から各要素が目的の値と等しいかどうかを順番に調べます．等しいものを見つけた時点でその位置情報を返し，探索を終了する単純なものになります．
もし末尾まで調べて目的の要素がなければ特別な値(競プロなどでは"-1"など指定されています．)を返します．
アルゴリズム効率の悪さはありますが，データの並び方に関係なく，利用することができます.
競プロでは計算量を考慮しなければいけませんが，まずはこれでいけるかどうか考えてみるといいかもしれませんね．
対応する問題はALDS1_4_A:Linear Searchです．
問題の意図としてはn個の整数を含むリストxとq個の重なりのない整数を含むリストyを比較し，リストyの要素がリストxに何個含まれているかを答える問題になっています．
では，早速実装していきましょう．
今回は素直な実装とpythonの特徴を生かした実装の二つを用意してみました．
素直な実装
N = int(input()) num_list = list(map(int, input().split())) q = int(input()) search_num = list(map(int,input().split())) ans = 0 for i in search_num: if i in num_list: ans += 1 print(ans)
最初の4行は入力を受け取っているだけなのであまり気にしないでください．if文でnum_listの中にsearch_num[i]が含まれているか確認しています．この時，n回の比較をしているので，オーダーはO(qN)となります．
pythonの特徴(set)を生かした実装
N = int(input()) num_list = list(map(int, input().split())) q = int(input()) search_num = list(map(int,input().split())) ans = 0 for i in set(num_list): if i in search_num: ans +=1 print(ans)
少し計算量の話を追加で書きます.
pythonの特徴を生かした実装で使ったsetは集合を表していてリストの中身の重なりのある整数を重なりのない状態にしています．また，setのオーダーはO(1)です(参考)．扱った問題ではn個のリストの中に同じ整数が含まれていることがあったので，多少計算時間が短くなると思います．
今回の問題ではNが大きくなれば計算量はもちろん増えますが，qにも依存しているので条件次第では計算時間が大きく変わるので問題文などをよく読んで解きましょう.
実際Atcoderのような競技プログラミングではPythonでO(n2)になると厳しいケースなどもあるので選ぶ探索アルゴリズムが重要になってきます．
二分探索(Binary Search)
二分探索ではデータの大小関係を利用しています．そのため，配列が整列されて管理されている場合，効率的に探索することができるアルゴリズムです．
基本的な動作は
- 配列全体を探索の範囲にする
- 探索が終了するまで以下の処理を繰り返す．
- 探索の範囲内の中央の要素を調べる
- 目的の値と中央の要素が一致した場合探索を終了する．
- 目的の値が中央の要素よりも小さければ二分したうちの前半部分を，
大きければ二分したうちの後半部分を探索範囲として1.に戻る．
各計算ステップが終わるごとに調べる範囲が半分になっていくので，高速に探索を行うことができます．
対応する問題はALDS1_4_B:Binary Searchになります．
問題の意図は先ほどと変わらないのですが，注目して欲しいのが制約部分です．
- 整数のリストSは昇順に並んでいる．
- n ≤ 100,000 , q ≤ 50,000
つまり，入力はソートされた整数で与えられることと先ほどの線形探索だとO（qn）だったので 5.0 x 109 となり計算量が先ほどの問題の1000 倍かかるようになっているということに注目して欲しいです．こういった場合に二分探索は威力を発揮します．
では早速実装して行ってみましょう．
def binary_search(num_list, key): left = 0 right = len(num_list) while right > left: mid = (left + right)//2 if num_list[mid] == key: return 1 #前半部分に答えがある if num_list[mid] > key: right = mid #後半部分に答えがある elif num_list[mid] < key: left = mid + 1 return 0 n = int(input()) S = list(map(int, input().split())) q = int(input()) T = list(map(int, input().split())) ans = 0 for i in T: ans += binary_search(S, i) print(ans)
今回解いた問題は同じなので，線形探索のコードと二分探索のコードどちらとも提出してみました．
結果は次のようになります．
線形探索の結果
二分探索の結果
後半のテストケースになるにつれて(計算量が多くなるにつれて)計算速度に違いが大きく表れていることがわかると思います．
二分探索はその名の通り計算する範囲を半分にしていくので必要となる計算量はO(logn)となります．
今回の問題では n ≦ 100,000 までの範囲だったので二分探索自体は16回程度の探索回数で答えにたどり着きます．
二分探索を扱った問題は競技プログラミングでよく出てくるのでこれを機に一緒に覚えましょう!
ハッシュ法
ハッシュ関数と呼ばれる関数値によって，要素の格納場所を決定する方法です．データ構造の一種でハッシュテーブルと呼ばれる表を用いる探索アルゴリズムです．
要素の値を引数として関数を呼び出すだけでその位置を特定することができるので，データの特性によっては高速に探索することができます．
pythonの場合全く同じではないですが辞書型がこれに当たると思います．
該当する問題はあるのですが，pythonで解くと簡単に済んでしまうので今回は省略させていただきます.
