Pythonで木構造の問題を解いてみた
こんにちは，今回は前回扱った木構造の復習を兼ねて木を扱った問題と木の仕組みを利用した問題二つを解いていきたいと思います．
まだ，前回記事をみていない方，木構造を知らない方は一つ前の記事を読んでみてください．
目次
木構造の練習問題1(木の巡回)
今回の問題はALDS1_7_C: Tree Walk です．
問題の内容としては以下の二分木の探索方法を三つ実装するというものです．
- 根節点，左部分木，右部分木の順で節点の番号を出力する．(先行順巡回 ： Preorder Tree Walk)
- 左部分木，根節点，右部分木の順で節点の番号を出力する．(中間順巡回 ： Inorder Tree Walk)
- 左部分木，右部分木，根節点の順で節点の番号を出力する．(後行順巡回 : Postorder Tree Walk)
入力は最初の行に節点の個数nが与えられ，続くん行には各節点の情報(id, left, right)が与えられます．
※子供を持たない場合left, rightは-1が与えられます．
出力は上記の三つの探索方法の名称と巡回した順番に節点番号を出力するというものです．
では，練習なので早速取り掛かっていきましょう．
実装コード
class Node: def __init__(self): self.parent = -1 def make_orderlist(node_id, answer_dic): preorder(node_id, answer_dic) inorder(node_id, answer_dic) postorder(node_id,answer_dic) def preorder(node_id, answer_dic): if node_id == -1: return answer_dic["Preorder"].append(str(node_id)) preorder(Tree[node_id].left, answer_dic) preorder(Tree[node_id].right, answer_dic) def inorder(node_id, answer_dic): if node_id == -1: return inorder(Tree[node_id].left, answer_dic) answer_dic["Inorder"].append(str(node_id)) inorder(Tree[node_id].right, answer_dic) def postorder(node_id, answer_dic): if node_id == -1: return postorder(Tree[node_id].left, answer_dic) postorder(Tree[node_id].right, answer_dic) answer_dic["Postorder"].append(str(node_id)) N = int(input()) Tree = [Node() for _ in range(N)] #make_tree for _ in range(N): #id, left, right tree_info = list(map(int, input().split())) node_id = tree_info[0] left = tree_info[1] right = tree_info[2] #自身の子をセット Tree[node_id].left = left Tree[node_id].right = right #子からみた親をセット if left != -1: Tree[left].parent = node_id if right != -1: Tree[right].parent = node_id #search_root root_id =[i for i,t in enumerate(Tree) if t.parent == -1][0] answer_dic = {"Preorder":[], "Inorder":[], "Postorder":[]} make_orderlist(root_id, answer_dic) #answer_output for i in answer_dic: print(i) #出力の形式上先に空白を一つ入れる必要があるらしい print(" "+" ".join(answer_dic[i]))
コードの解説
前回と同じコードを最初の部分にはそのまま活用しています．
今回扱っている木構造では兄弟の情報や深さなどは必要なく，単純に自分の親と左右の子供の状態を知っていれば大丈夫です．
また，基本的にはrootは最初の入力された節点だと思うので必要に応じて使い分けてください．
中身に関してはmake_orderlistの部分が新しい部分にはなってきます．
しかし，ここの部分に関しても今までやってきた再帰のやり方を覚えていれば難なくできると思います．
練習問題1の応用(木の巡回の応用)
問題内容
ある二分木に対して，それぞれ先行順巡回と中間順巡回を行なって得られる節点番号の列が与えられるので，その二分木の後行順巡回で得られる節点の列を出力するプログラムを作成するというものです．
入力としては一行目に節点の数nが与えられ，二行目に先行順巡回で得られる節点番号の列，三行目に中間順巡回で得られる節点番号の列が与えられます．
出力は後行順巡回で得られる節点番号の列を出力します．
問題は理解できますが，実装方法が若干複雑そうですね…
問題の解説
問題を順番に考えていきたいと思います．
先行順巡回では根→左部分木→右部分木の順に巡回していきます．
一方，中間順巡回では左部分木→根→右部分木の順に巡回していきます．
それぞれの巡回で生まれる違いを利用していきたいと思います．
まず，上記の図のような木構造が与えられていた時
先行順巡回 = [1,2,3,4,5,6,7,8,9]
中間順巡回 = [3,2,5,4,6,1,8,7,9]
というような列が与えられます．
この時，先行順巡回の先頭の値は根であるので中間順巡回を
左部分木 = [3,2,5,4,6]
右部分木 = [8,7,9]
のように分けることができます.
次に先行順巡回の次の値は"2"なので左部分木をさらに
左部分木 = [3]
右部分木 = [5,4,6]
のようにわけることができます．
この操作を繰り返すことで木構造がどのような形であったか再構築することができます．
この再構築をしていく過程で後行順巡回の巡回方法に沿って答えのリストを作っていけば問題を解くことができそうですね.
では実際に実装していきたいと思います.
実装コード
def reconstruct(l, r): if l >= r: return root = pre_list.pop(0) center = in_list.index(root) reconstruct(l, center) # 左部分木 reconstruct(center+1, r) #右部分木 ans_list.append(str(root)) N = int(input()) pre_list = list(map(int, input().split())) in_list = list(map(int, input().split())) #answer_output ans_list = [] reconstruct(0, N) print(" ".join(ans_list))
コードの解説
コードに落とし込むと解説するほどのものではなくなっていますね.
先行順巡回の節点を引っ張り，それに対応する中間順巡回の場所をまずは探します．
その中間順巡回の場所が左部分木と右部分木にわける位置となっています．
同様の操作を分けられた左部分木と右部分木でも行うよう再帰させています．
左部分木が再帰できなくなった点が最初の後行順巡回の値になるのでそのタイミングでリストに値を追加されるようにしています.
最後に
今回は前回扱った木構造の問題を復習しながら扱いました．また，扱った木の巡回の応用問題も解いていきました．
この木の巡回の応用は二分探索にもつながる考え方なので二分探索の仕組みを知りたい人にぜひ解いてもらいたいです．
解いてほしい問題や解き方に関するコメントなどなんでもいいのでありましたらコメントよろしくお願いします!
スターも励みになるので気が向いたら押してください！
Pythonで木構造を実装してみた ~二分木と根付き木~
こんにちは，今回は競技プログラミングでよく見る木構造について解説していきたいと思います．
目次
木
木構造は階層的な構造を表すのに適したデータ構造で効率的なアルゴリズムやデータ構造を実装するための基本となる考え方です．
今回は木をどのように表現するかや木構造を利用した基本的なアルゴリズムの実装をしていきたいと思います．
まず木構造とは節点(node)と節点同士を結ぶ辺(edge)で表されるデータ構造です．それを踏まえた上で根付き木と二分木を紹介していきたいと思います．
根付き木
根付き木は木の中でも根(root)と呼ばれる他の節点と区別された一つの節点を持つ木の構造のことを言います．
根付き木の節点には親子関係があります．rootを基準にそこからつながる節点は子供となり，同じ深さにある節点は兄弟と呼びます．
また，子を持たない節点を葉(leaf)や外部節点と呼びます．
図を見れば簡単に理解できると思うので載せておきます．
では,実際に問題を解いていきたいと思います．
根付き木の問題
今回扱う問題はALDS1_7_A:Rooted Treesになります．
問題の内容としては与えられた根付き木の各節点について
- 節点番号
- 節点の種類(根， 内部ノード, 葉)
- 親の節点番号
- 子のリスト
- 深さ
の情報を出力するプログラムを生成するというものです．
入力は節点の個数nとそれに続く行で節点の番号(id), 次数(k), 1~k番目までの子の節点番号(c1,…,ck)の情報が与えられます．
制約
- 1 ≦ n ≦ 100,000
- 節点の深さは20以下
- 任意の二つの節点間に必ず経路が存在する
となっています．
根付き木の実装コード
では，早速実装していきたいと思います．
class Node: def __init__(self): self.parent = -1 self.children = [] def cal_depth(node_id, d = 0): Tree[node_id].depth = d for child in Tree[node_id].children: cal_depth(child, d+1) N = int(input()) Tree = [Node() for _ in range(N)] #make_tree for _ in range(N): #id, 子供の数k, c_0~c_k tree_info = list(map(int, input().split())) node_id = tree_info[0] k = tree_info[1] if k > 0: children = tree_info[2:] Tree[node_id].children = children Tree[node_id].type = "internal node" else: Tree[node_id].type = "leaf" for child in Tree[node_id].children: Tree[child].parent = node_id #search_root root_id =[i for i,t in enumerate(Tree) if t.parent == -1][0] Tree[root_id].type = "root" cal_depth(root_id) #answer_output for i, t in enumerate(Tree): print("node {}: parent = {}, depth = {}, {}, {}".format(i, t.parent, t.depth, t.type, t.children))
コードの解説
まず，今回扱う問題ではrootは"-1"にするように，また,節点に子がいなければ"[]"を出力するように求められているので初期化して最初の呼び出しの時にはその状態になるようにしています．
次に，深さの計算の説明をしていきます．
深さに関しては上記のプログラムの特性上すでにrootの節点が分かっている状態になっています．
そのため，root節点から上から順に辿っていくことで各節点の深さを求めることができます．
各ノードには自身の持つ子の状態が保存されているので，各子供に対して再帰的にプログラムを呼び出すことで深さを求めています
最後に，メインとなっている木構造を作っている部分に関してです．
ここでは，まずはじめにN個のNodeを作成します．
次に，入力を受け取りながら子供の情報，ノードのタイプを作っていきます．
子供に関してはkが1以上なら入力情報に合わせて子供のリストを作成，kが0なら子供がいないのでそのままとしています．
ノードのタイプに関しては一つでも子がいれば"internal node"になるのでNodeに内部ノードであると情報を追加します．
一方で，もし子供がいなければその節点は葉であることが確定しているのでNodeに対して"leaf"という情報を追加しています．
これらだけではどれがrootかというのがわかっていないので最後にすべてのノードの情報を確認し，親が"-1"のままのノードを探し，rootとしています．
二分木
二分木は根付き木の中でも全ての節点についてその子の数が2以下である木構造のことを言います．
また，二分木では節点が持つ子を左の子と右の子に区別されます．つまり，子が一つの場合にも左の子にするか右の子にするか区別する必要があります．
こちらに関しても図で確認した方がわかりやすいので載せておきます．
二分木の問題
二分木に関して扱っている問題ALDS1_7_B: Binary_Treeを解いていきたいと思います．
問題の内容としては
与えられた二分木Tの各節点uについて
- uの節点番号
- uの親
- uの兄弟
- uの子の数
- uの深さ
- uの高さ
- uの節点の種類
を出力するというものです.
入力は id, right, leftが与えられ，もし子を持たない場合left(right)-1と表されます．
問題の作り自体は先ほどの根付き木に似ているので上記のプログラムを書き換えていくこと解けるのではないかと思います．
二分木の実装コード
では，早速実装に取り掛かりたいと思います．
class Node: def __init__(self): self.parent = -1 self.degree = 0 self.sibling = -1 def cal_depth(node_id, d = 0): Tree[node_id].depth = d if Tree[node_id].left !=-1: cal_depth(Tree[node_id].left, d+1) if Tree[node_id].right !=-1: cal_depth(Tree[node_id].right, d+1) def cal_height(node_id): left_h = 0 right_h = 0 if Tree[node_id].left != -1: left_h = cal_height(Tree[node_id].left) + 1 if Tree[node_id].right != -1: right_h = cal_height(Tree[node_id].right) + 1 Tree[node_id].height = max(left_h, right_h) return max(left_h, right_h) N = int(input()) Tree = [Node() for _ in range(N)] #make_tree for _ in range(N): #id, left, right tree_info = list(map(int, input().split())) node_id = tree_info[0] left = tree_info[1] right = tree_info[2] #自身の子をセット Tree[node_id].left = left Tree[node_id].right = right #子からみた親をセット if left != -1: Tree[left].parent = node_id if right != -1: Tree[right].parent = node_id #ノードのタイプをセット if left == -1 and right == -1: Tree[node_id].type = "leaf" elif left == -1 or right == -1: Tree[node_id].degree = 1 Tree[node_id].type = "internal node" else: #兄弟をセット Tree[right].sibling = left Tree[left].sibling = right Tree[node_id].degree = 2 Tree[node_id].type = "internal node" #search_root root_id =[i for i,t in enumerate(Tree) if t.parent == -1][0] Tree[root_id].type = "root" cal_depth(root_id) cal_height(root_id) #answer_output for i, t in enumerate(Tree): print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(i, t.parent, t.sibling, t.degree, t.depth, t.height, t.type))
コードの補足
先ほどの根付き木のコードとの変更点で少しつまずきそうな部分だけ補足説明していきたいと思います．
追加された要素として，siblingとdegreeとheightの三つがあります．
siblingとdegreeに関しては入力のleft，rightが-1である場合において注意しながら条件分岐させ，プログラムを作成することで簡単に出力の形を作ることができると思います．
heightに関しては再帰関数を用いています．
おおまかな流れとしては，呼び出し元に対して呼び出し先のheightを返し，それを+1したものが呼び出し元のheightになるようになっています．
これを再帰的に呼び出すことでrootまでの全節点のheightがわかるようになっています．
最後に
今回扱っている木構造はイメージはしやすいのですが，実装に関しては何度かやっていく中で慣れていく必要があると感じました．
実際に自分も作ってみたのは初めてだったので読みづらい部分があると思いますが，愚直に解いているので上からしっかり読み進めていけば理解できるようになっていると思います．
今後このような問題を解いてほしい，木構造のより簡単な実装などありましたらコメントよろしくお願いします!!
Pythonで最小コストソート(Silly Sort)解いてみた
一週間ほど期間が空きましたが，今日もアルゴリズムの実装をしていきたいと思います．
今回扱う問題は解き方を考えるまでに苦労しますが，実装はそれほど難しくないと思うのでぜひ競技プログラミングが好きな方にはチャレンジしてもらいたい問題になっています．
目次
最小コストソート(Silly Sort)
何の大会かはわかりませんが2002年の世界大会で扱われたこともある問題だそうです．(参考)
問題の内容としては個々の重さwiが定められたn個の荷物を重さの昇順に並び替えた時の最小の移動コストを求めるという問題です．また，荷物の位置の交換は何度でも行うことができます．
対応する問題はALDS1_6_D: Minimum Cost Sortになります．
まずは問題を解いてみたいという方は先に見に行ってみてください.
では，早速問題の中身をみていきたいと思います．
与えられる入出力は
入力 : 一行目に整数nが与えられ，二行目にn個の整数が空白区切りで与えられる.
出力 : 最小コストを出力
制約 : 1 ≦ n ≦ 1000
0 ≦ wi ≦ 104
wiはすべて異なる
となっております．
制限が1秒なのでO(n2)ぐらいまでなら通すことができそうですね．
問題の考察
詳しく問題の内容を紐解いていきたいと思います.
まずは簡単な例を使って問題を図式的にとらえてみようと思います.
例えば，ランダムに並べられた1~8までの重さを持つ荷物の配列{5, 2, 6, 1, 4, 8, 7, 3}が与えられた時の最小コストを考えてみます．
各要素がそれぞれあるべき場所に移動するための矢印を加えたものを図として表しています．
この時，いくつかのサイクルができていることがわかると思います．このループごとに必要な最小コストを求めることを考えると次の図のようにコストは求められます．
よって，最小コストはこの例の場合 "31" となります．
この例ではうまくループの中の最小コストの荷物を利用して要素を移動し，整列させることで最小コストを求めることができました．
しかし，ループに含まれる要素が大きすぎる場合前述の方法では最小のコストを求められない場合があります．
この問題を解消するために，次の2つコスト計算を用いてコストの比較を行います.
- ループ内の最小の重さの要素を使ってループ内の要素を整列させた時のコスト
- 全体の要素の中の最小の重さの要素をループの外から持ってきて要素を正しい順序に移動させることによって求めたコスト
この1番目の方法が先ほどの問題例の時の考え方になります.
二番目の方法に関して考えていきたいと思います．
外部から最小の重さの要素を持ってくるには元に戻すことも考慮にいれると
(
ループ内の最小の要素)
だけコストが増加します．
また，
だけコストは減少します．
つまり，合計のコストは
となります．
この二つのコストを計算し，値が小さい方を最小の移動コストとして出力することでこの問題を解くことができます．
実装(コード)
では，実際にPythonで実装していきたいと思います.
def solve(w_list, sort_list): ans = 0 min_num = sort_list[0] for i in range(len(w_list)): x = sort_list.index(w_list[i]) if x == i: continue sum_cost = 0 min_loop_n = 10**4 + 1 j = i loop_count = 0 while True: loop_count += 1 sum_cost += w_list[j] min_loop_n = min(min_loop_n, w_list[j]) if x == i: break w_list[x], w_list[j] = w_list[j], w_list[x] x = sort_list.index(w_list[j]) ans += min(sum_cost + (loop_count-2)*min_loop_n, sum_cost + min_loop_n + (loop_count+1)*min_num) return ans n = int(input()) w_list = list(map(int, input().split())) sort_list = sorted(w_list) print(solve(w_list, sort_list))
最初の図で扱った問題例をsolveにいれてみると，，，
w_list =[5, 2, 6, 1, 4, 8, 7, 3] sort_list = sorted(w_list) print(solve(w_list, sort_list))#31
31が出力されると思います．
今回扱かった問題は考え方を思いつくまでに時間がかかりましたが，実装に関しては今までの知識を活用すれば難しくない範囲だったと思います．
気が向いた方は問題の考察の部分を読んで実際に自分で実装してみてください！
もし記事が気に入ってくれた方がいらっしゃったら，コメント・スターよろしくお願いします．
pythonでバケットソートの実装してみた
バケットソート(計数ソート)
pythonでは可変長の配列を作り出すことが簡単にできるのでバケットソートに関しては今まで学んだ知識を使わずに実装することができます．
今回扱うバケットソートには, 大きく分けて2種類の実装があります．
まずひとつは,可変個の要素を保持できるデータ構造を使ってバケツを表現する方法です．pythonのリストの考え方で言うと数値の種類分の二次元配列を用意し,その中にデータを入れていく方法です．
もうひとつは,いったん整列対象のデータを走査して値ごとの出現回数を数えておき,その出現回数に従った数値をリスト化する方法です．
この実装によるバケットソートのみを指して特に分布数えソート，計数ソート(Counting Sort)などと言うそうです．(参照)
バケットソートの実装
今回は後者の計数ソートの形をpythonで実装していきたいと思います．
import random def counting_sort(A, max_num): #配列は0スタートのため count_list = [0]*(max_num+1) for i in A: count_list[i] += 1 i = 0 for num in range(len(count_list)): for c in range(count_list[num]): A[i] = num i += 1 #要素数15の配列を作成 A = [random.randint(1,10) for _ in range(15)] #randomに生成できる整数の最大値をmax_numとしてsortしていく print(A) counting_sort(A, 10) print(A)
出力例
[9, 3, 8, 3, 6, 7, 6, 4, 8, 5, 9, 8, 2, 2, 2] [2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 8, 9, 9]
pythonのリストを利用するとメモリを動的に増やすことができるのでバケットソートに関してはマージソート，クイックソートと比べると簡単に実装することができますね．
メモリの確保をしないといけないので要素数の数にだけ注意が必要になります．
pythonでアルファベットのリストの出力
先日受けたアルゴリズム実技検定でアルファベットのリストを作成してそれを利用するような問題が出ていたので自身の備忘録も兼ねてアルファベットのリストの作成方法をまとめました．
基本的にはqiita記事を参考にしているので元記事が気になる人はこちらを見てください．
コード例
まず，コピペ用にアルファベットの全ての小文字を出力する三つのコード例を載せておきます．
import string print(list(string.ascii_lowercase))
print([chr(ord("a")+i) for i in range(26)])
print([chr(i) for i in range(97, 97+26)])
出力はいずれも下記のようになっています．
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
stringを使った方法
pythonの標準ライブラリのstringを使った方法です．stringではアルファベット以外にも特殊文字や数字に関しても扱うことができます．文字列で出力されるのでlist()でリスト化すれば，アルファベットのリストが手に入ります．
ここでは，stringを使って何を出力できるのかコードとその出力を載せておきたいと思います．
import string #アルファベットの大文字小文字の出力 print(string.ascii_letters) #アルファベットの小文字のみの出力 print(string.ascii_lowercase) #アルファベットの大文字のみの出力 print(string.ascii_uppercase) #数値の文字列の出力 print(string.digits) #16進数で扱う文字列の出力 print(string.hexdigits) #８進法で扱う文字列の出力 print(string.octdigits) #特殊文字列の出力 print(string.punctuation) #上記で扱った文字列の出力 print(string.printable) #スペースや改行など空白に関する文字列の出力 print(string.whitespace)
出力(printableとwhitespace以外に関して)
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789 0123456789abcdefABCDEF 01234567 !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~
chrを使った方法
PythonでUnicodeコードポイント（文字コード）の文字列を返してくれるのがchr()です.
ある一文字に対応するUnicodeコードポイントを表す整数値を返してくれるのがord()です．
#chrとordの関係性 print(chr(49)) # "1" print(ord("1")) # 49
この関係性を使うことでアルファベットのリストを出力することができます．
# upper-case A-Z print([chr(i) for i in range(65,65+26)]) print([chr(ord("A")+i) for i in range(26)]) # lower-case a-z print([chr(i) for i in range(97,97+26)]) print([chr(ord("a")+i) for i in range(26)])
競技プログラミングなどでたまにリストを用意しておく必要があるので，今後すぐに見られるようにメモとして記事にしました．
