スズメの本棚

自分の知識の定着のために本や実装したことをまとめていきます.

プライバシーポリシー

目次

当サイトに掲載されている広告について

当サイトでは、第三者配信の広告サービスを利用しています。
このような広告配信事業者は、ユーザーの興味に応じた商品やサービスの広告を表示するため、当サイトや他サイトへのアクセスに関する情報 『Cookie』(氏名、住所、メール アドレス、電話番号は含まれません) を使用することがあります。
Googleアドセンスにおける広告への Cookie利用に関してはこちらに詳しく記載されているのでご確認ください。

当サイトが使用しているアクセス解析ツールについて

当サイトでは、Googleによるアクセス解析ツール「Googleアナリティクス」を利用しています。
このGoogleアナリティクスはトラフィックデータの収集のためにCookieを使用しています。
このトラフィックデータは匿名で収集されており、個人を特定するものではありません。

この機能はCookieを無効にすることで収集を拒否することが出来ますので、お使いのブラウザの設定をご確認ください。

免責事項

当サイトで掲載している画像の著作権・肖像権等は各権利所有者に帰属致します。権利を侵害する目的ではございません。
記事の内容や掲載画像等に問題がございましたら、各権利所有者様本人が直接メールでご連絡下さい。確認後、対応させて頂きます。

当サイトからリンクやバナーなどによって他のサイトに移動された場合、移動先サイトで提供される情報、サービス等について一切の責任を負いません。

当サイトのコンテンツ・情報につきまして、誤情報が入り込んだり、情報が古くなっていることもございます。あらかじめご了承ください。

当サイトに掲載された内容によって生じた不利益などには一切の責任を負いかねますのでご了承ください。


運営者:がう
初出掲載:2020/08/26

Pythonで木構造の問題を解いてみた

こんにちは,今回は前回扱った木構造の復習を兼ねて木を扱った問題と木の仕組みを利用した問題二つを解いていきたいと思います.
まだ,前回記事をみていない方,木構造を知らない方は一つ前の記事を読んでみてください.

目次

木構造の練習問題1(木の巡回)

今回の問題はALDS1_7_C: Tree Walk です.
問題の内容としては以下の二分木の探索方法を三つ実装するというものです.

  1. 根節点,左部分木,右部分木の順で節点の番号を出力する.(先行順巡回 : Preorder Tree Walk)
  2. 左部分木,根節点,右部分木の順で節点の番号を出力する.(中間順巡回 : Inorder Tree Walk)
  3. 左部分木,右部分木,根節点の順で節点の番号を出力する.(後行順巡回 : 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が与えられ,二行目に先行順巡回で得られる節点番号の列,三行目に中間順巡回で得られる節点番号の列が与えられます. 出力は後行順巡回で得られる節点番号の列を出力します.
問題は理解できますが,実装方法が若干複雑そうですね…

問題の解説

問題を順番に考えていきたいと思います. 先行順巡回では根→左部分木→右部分木の順に巡回していきます.
一方,中間順巡回では左部分木→根→右部分木の順に巡回していきます.
それぞれの巡回で生まれる違いを利用していきたいと思います.

f:id:tech_shelf:20200818191504p:plain

まず,上記の図のような木構造が与えられていた時
先行順巡回 = [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)や外部節点と呼びます.
図を見れば簡単に理解できると思うので載せておきます.

f:id:tech_shelf:20200803034542p:plain
木 (数学) - Wikipedia

では,実際に問題を解いていきたいと思います.

根付き木の問題

今回扱う問題は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以下である木構造のことを言います.
また,二分木では節点が持つ子を左の子と右の子に区別されます.つまり,子が一つの場合にも左の子にするか右の子にするか区別する必要があります.
こちらに関しても図で確認した方がわかりやすいので載せておきます.

f:id:tech_shelf:20200803040459p:plain
二分木 - Wikipedia

二分木の問題

二分木に関して扱っている問題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}が与えられた時の最小コストを考えてみます.
各要素がそれぞれあるべき場所に移動するための矢印を加えたものを図として表しています.

f:id:tech_shelf:20200620182744p:plain

この時,いくつかのサイクルができていることがわかると思います.このループごとに必要な最小コストを求めることを考えると次の図のようにコストは求められます.

f:id:tech_shelf:20200620182908p:plain

よって,最小コストはこの例の場合 "31" となります.
この例ではうまくループの中の最小コストの荷物を利用して要素を移動し,整列させることで最小コストを求めることができました.
しかし,ループに含まれる要素が大きすぎる場合前述の方法では最小のコストを求められない場合があります.
この問題を解消するために,次の2つコスト計算を用いてコストの比較を行います.

  1. ループ内の最小の重さの要素を使ってループ内の要素を整列させた時のコスト
  2. 全体の要素の中の最小の重さの要素をループの外から持ってきて要素を正しい順序に移動させることによって求めたコスト

この1番目の方法が先ほどの問題例の時の考え方になります.
二番目の方法に関して考えていきたいと思います.
外部から最小の重さの要素を持ってくるには元に戻すことも考慮にいれると
 2(min(w_i)+x) ( x = ループ内の最小の要素)
だけコストが増加します.
また,
 (n-1)(x-min(w_i))
だけコストは減少します.

つまり,合計のコストは

 Cost = sum(loop \ element) + (n-2)x + 2(min(w_i)+x) - (n-1)(x-min(w_i))

 \ \ \ \ \ \ \  = sum(loop \ element)+ x + (n+1)min(w_i)

となります.
この二つのコストを計算し,値が小さい方を最小の移動コストとして出力することでこの問題を解くことができます.

実装(コード)

では,実際に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が出力されると思います.

今回扱かった問題は考え方を思いつくまでに時間がかかりましたが,実装に関しては今までの知識を活用すれば難しくない範囲だったと思います.
気が向いた方は問題の考察の部分を読んで実際に自分で実装してみてください!

もし記事が気に入ってくれた方がいらっしゃったら,コメント・スターよろしくお願いします.