08 Dec 2015, 12:26

TopCoderで深さ優先探索と幅優先探索の問題を解いてみる(Python)

以下の参考書を元に、TopCoderの対策をしています。

今日は、深さ優先探索と、幅優先探索について勉強しました。

深さ優先探索(DFS)

なるべく左に深い点から探索するアルゴリズム.

実装方法

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    実装では再帰関数を用いる. ここでは、答えを最大化する深さ優先探索の例.
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> def dfs(now):<br /> if &#8220;nowが終了条件&#8221;:<br /> return &#8220;nowの答え&#8221;
  </p>

  <p>
    ret = -1<br /> for i in range(&#8220;次の状態の個数&#8221;):<br /> next = &#8220;i番目の次の状態&#8221;<br /> if &#8220;nextが条件を満たしている&#8221;:<br /> ret = max(dfs(next), ret)<br /> return ret<br /> [/sourcecode]
  </p>
</div>

SRM 425 Div2 500

<div class="outline-text-3" id="text-orgheadline3">
  <ul class="org-ul">
    <li>
      <a href="https://community.topcoder.com/stat?c=problem_statement&pm=10095&rd=13516">https://community.topcoder.com/stat?c=problem_statement&pm=10095&rd=13516</a>
    </li>
  </ul>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> # -*- coding: utf-8 -*-<br /> import math,string,itertools,fractions,heapq,collections,re,array,bisect
  </p>

  <p>
    class CrazyBot:<br /> def __init__(self):<br /> self.grid = [[False for i in range(100)] for j in range(100)]<br /> self.vx = [1, -1, 0, 0]<br /> self.vy = [0, 0, 1, -1]<br /> self.prob = [0.0, 0.0, 0.0, 0.0]
  </p>

  <p>
    def dfs(self, x, y, n):<br /> # 一度通った場所は確率0<br /> if self.grid[x][y]:<br /> return 0<br /> if n == 0:<br /> return 1
  </p>

  <p>
    # 通った場所にフラグを立てる<br /> self.grid[x][y] = True<br /> ret = 0.0
  </p>

  <p>
    for i in range(4):<br /> ret += self.dfs(x + self.vx[i],<br /> y + self.vy[i], n &#8211; 1) * self.prob[i]
  </p>

  <p>
    self.grid[x][y] = False<br /> return ret
  </p>

  <p>
    def getProbability(self, n, east, west, south, north):<br /> self.prob[0] = east / 100.0<br /> self.prob[1] = west / 100.0<br /> self.prob[2] = south / 100.0<br /> self.prob[3] = north / 100.0
  </p>

  <p>
    return self.dfs(50, 50, n)<br /> [/sourcecode]
  </p>
</div>

幅優先探索(BFS)

深さの浅い、左側の点から順に探索するアルゴリズム.

実装方法

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    実装ではQueueを用いる.
  </p>

  <p>
    [sourcecode language=&#8221;text&#8221; title=&#8221;&#8221; ]<br /> 1. 根ノードを空のキューに加える。<br /> 2. ノードをキューの先頭から取り出し、以下の処理を行う。<br /> ノードが探索対象であれば、探索をやめ結果を返す。<br /> そうでない場合、ノードの子で未探索のものを全てキューに追加する。<br /> 3. もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ&#8221;not found&#8221;と結果を返す。2に戻る。<br /> [/sourcecode]
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> queue = []<br /> queue.append(&#8220;初期状態&#8221;)<br /> while len(queue) > 0:<br /> # 取り出し<br /> now = queue[0]<br /> del queue[0]<br /> # now に対しての処理<br /> for i in range(&#8220;次の状態の個数&#8221;):<br /> next = &#8220;i番目の次の状態&#8221;<br /> if &#8220;nextが訪問済みであるかどうかの判定&#8221;:<br /> queue.append(next)<br /> [/sourcecode]
  </p>
</div>

SRM 453.5 Div2 500

<div class="outline-text-3" id="text-orgheadline6">
  <ul class="org-ul">
    <li>
      <a href="https://community.topcoder.com/stat?c=problem_statement&pm=10451&rd=14174">https://community.topcoder.com/stat?c=problem_statement&pm=10451&rd=14174</a>
    </li>
  </ul>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> # -*- coding: utf-8 -*-<br /> import math,string,itertools,fractions,heapq,collections,re,array,bisect
  </p>

  <p>
    class MazeMaker:<br /> def longestPath(self, maze, startRow, startCol, moveRow, moveCol):<br /> width = len(maze[0])<br /> height = len(maze)<br /> board = []
  </p>

  <p>
    # ボードの初期化<br /> for i in range(height):<br /> list = []<br /> for j in range(width):<br /> list.append(-1)<br /> board.append(list)
  </p>

  <p>
    # スタート地点のマーク<br /> board[startRow][startCol] = 0
  </p>

  <p>
    # キューの宣言<br /> queueX = []<br /> queueY = []<br /> queueX.append(startCol)<br /> queueY.append(startRow)
  </p>

  <p>
    # キューが空になるまで、一つずつ取り出す<br /> while len(queueX) > 0:<br /> x = queueX[0]<br /> y = queueY[0]<br /> del queueX[0]<br /> del queueY[0]
  </p>

  <p>
    for i in range(len(moveRow)):<br /> nextX = x + moveCol[i]<br /> nextY = y + moveRow[i]
  </p>

  <p>
    if 0 <= nextX and nextX < width \ and 0 <= nextY and nextY < height \ and board[nextY][nextX] == -1 \ and maze[nextY][nextX] == ".": # ボードに移動量を更新する board[nextY][nextX] = board[y][x] + 1 # 末尾に次の移動点を挿入 queueX.append(nextX) queueY.append(nextY) # 最大移動量の計算 ret = 0 for i in range(height): for j in range(width): # 移動できない点があったら、-1を返す if maze[i][j] == "." and board[i][j] == -1: return -1 ret = max(ret, board[i][j]) return ret [/sourcecode] </div> </div> </div> 

    <div id="outline-container-orgheadline7" class="outline-2">
      <h2 id="orgheadline7">
        DFSとBFSの比較
      </h2>

      <div class="outline-text-2" id="text-orgheadline7">
        <ul class="org-ul">
          <li>
            全通りを列挙し、をまとめる必要がある場合は DFS
          </li>
          <li>
            始点からもっとも近いものを求めたいときは、BFS
          </li>
        </ul>
      </div>
    </div>

    <div id="outline-container-orgheadline8" class="outline-2">
      <h2 id="orgheadline8">
        Special Thanks
      </h2>

      <div class="outline-text-2" id="text-orgheadline8">
        <ul class="org-ul">
          <li>
            <a href="http://www.itmedia.co.jp/enterprise/articles/1001/16/news001.html">最強最速アルゴリズマー養成講座:知れば天国、知らねば地獄――「探索」虎の巻 &#8211; ITmedia エンタープライズ</a>
          </li>
          <li>
            <a href="http://qiita.com/MasayaMizuhara/items/86099ad721a329e1d6cd">全探索アルゴリズム入門 &#8211; Qiita</a>
          </li>
        </ul>
      </div>
    </div>

06 Dec 2015, 10:07

プログラミングコンテストのモチベーションをあげる良記事まとめ

はじめに

自分用記事. 最近、やることもないので、プロコンの勉強を始めた。

モチベーションをあげるために、 プログラミングコンテストの勉強のテンションあがる記事を集めてみた。

TopCoderを中心に頑張りたい。まずは、Div1にあがるところから頑張ろう。

すごい人たち

以下のスキルは身につかないと思います。 ・チーム開発のスキル ・設計スキル

自分が前に進んでることを感じたり、学習のやり方が間違ってないと確信する ために、TopCoder(競技プログラミング)やTOEICなど能力を数値で表してくれ るテストはとても頼りになりました。

プログラミングの能力を他人と競いあうのはとても楽しい! お金もかからな いし、勉強にもなるし一石二鳥じゃないか

TopCoderも企業に対して優秀なプログラマーをリクルートすることをビジネス モデルの要としている。「レーティングが2200を超えた人物は、表示文字が赤 くなるため、レッドコーダーと呼ばれるのですが、そうしたRedCoderたちが Googleへ入社した、といった話もよく耳にします

社会人

自分は社会人なので、頑張っている社会人のブログを見ると勇気づけられる(;д;)

あくまで競技プログラミングを練習することで得られる最大の効果は競技プロ グラミング能力の向上であって、仕事に役に立つとかいうのは運が良ければ副 次的に得られるものです

まだまだ脳は成長できる余地がありますよ世の20代後半のみなさん

他人と何かで競って、自分の立ち位置の上がったり下がったりが目に見えるのは楽しい

05 Dec 2015, 06:55

リスト探索(線形探索・二分探索) – Python

こんにちは。今日は、AOJ の問題に取り組むことで、探索の勉強をしてみました!

線形探索

[sourcecode language=”text” title=”” ]
リストや配列に入ったデータに対する検索を行うにあたって、
先頭から順に比較を行い、それが見つかれば終了する.
[/sourcecode]

ALDS1_4_A:

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    サンプル問題(AOJ): <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> n = int(input())<br /> S = list(map(int, input().split()))<br /> q = int(input())<br /> T = list(map(int, input().split()))
  </p>

  <p>
    def linearSearch(A, n, key):<br /> i = 0<br /> A.append(key) # 番兵<br /> while A[i] != key:<br /> i += 1<br /> A.pop()<br /> return i != n
  </p>

  <p>
    count = 0
  </p>

  <p>
    for i in range(q):<br /> if linearSearch(S, n, T[i]):<br /> count += 1
  </p>

  <p>
    print(count)<br /> [/sourcecode]
  </p>
</div>

二分探索

ソート済み配列に対する探索アルゴリズムの一つ

[sourcecode language=”text” title=”” ]
ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、
中央の値を見て、検索したい値との大小関係を用いて、
検索したい値が中央の値の右にあるか、左にあるかを判断して、
片側には存在しないことを確かめながら検索していく
[/sourcecode]

ALDS1_4_B:

<div class="outline-text-3" id="text-orgheadline4">
  <p>
    サンプル問題(AOJ): <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> n = int(input())<br /> S = list(map(int, input().split()))<br /> q = int(input())<br /> T = list(map(int, input().split()))
  </p>

  <p>
    def binary_search(A, key):<br /> left = 0<br /> right = n<br /> while left < right: mid = int((left + right)/2) if A[mid] == key: return True elif key < A[mid]: right = mid else: left = mid + 1 return False cnt = 0 for i in T: if binary_search(S, i): cnt += 1 print(cnt) [/sourcecode] </div> </div> </div> 

    <div id="outline-container-orgheadline5" class="outline-2">
      <h2 id="orgheadline5">
        Pythonの(文字列)探索ライブラリ
      </h2>

      <div class="outline-text-2" id="text-orgheadline5">
        <p>
          find, indexがある.
        </p>

        <ul class="org-ul">
          <li>
            <a href="http://python.civic-apps.com/string-find/">文字列検索系メソッド find, index, startswith, endswidth » Python Snippets</a>
          </li>
        </ul>
      </div>
    </div>

30 Nov 2015, 11:59

関数型プログラミングについて調べてみた

はじめに

関数型言語について、なんとなくは知っているけれども、 人に説明できないので、 調べてみた. いろんなサイトや書籍からの引用を含みます. 間違えてたら教えてください.

関数型プログラミングとは

関数型プログラミングとは、 複数の式を関数の適用によって組み合わせていくプログラミングスタイル. (from Wikipedia) https://ja.wikipedia.org/wiki/%E9%96%A2%E6%95%B0%E5%9E%8B%E8%A8%80%E8%AA%9E

なぜ関数型プログラミングが重要か

  • 分散処理や並行処理につよい. マルチコア、メニーコア、分散クラウド時代には、 それを容易にするパラダイムが必要です. 値を変更しない性質や、新しい平行モデルの導入によって、 CPUのコアを十二分に生かすことができるプログラミングができます.
  • コード量が少なくなる. 関数が値として扱えることによって、より抽象化がすすみ、 結果コード量が少なくなります. Scalaは Javaの 1/2のコード量でかけるとか.
  • バグりにくい・バクらせにくい 高度な制約条件を”型”として表現し、その制約条件が守られているかを コンパイル時などに検査させることが可能です. このことによって、コンパイルするだけでバグが出にくくなります.

    (http://gihyo.jp/book/2014/978-4-7741-6926-2 p4より)

どんな特徴があるか

以下のような特徴をもつプログラミングスタイルをもつ.

immutable

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    immutableとは、不定状態. 状態を全く変更できないということ. 変数に値が一度束縛されると変更できない。C言語でいう const.
  </p>
</div>

副作用がない

<div class="outline-text-3" id="text-orgheadline6">
  <p>
    副作用とは、状態を参照したり、あるいは状態に変化を与えること. 代入は副作用.副作用がないとは、関数を何度実行しても、 結果が変わらないことをいう.
  </p>

  <p>
    immutable性や副作用がないプログラミングパラダイムが平行処理に強くなる.
  </p>
</div>

第一級関数・高階関数

<div class="outline-text-3" id="text-orgheadline7">
  <p>
    第一級関数とは、関数を変数に格納できる性質のこと. 高階巻数とは、関数を引数にしたり、あるいは関数を戻り値とする性質のこと.
  </p>

  <p>
    このような性質で、関数を自在に組み合わせて抽象化できることで、 コード量がずっと少なくなり、シンプルなコードがかけるようになる.
  </p>
</div>

どんな関数型言語があるか

主要な関数型言語を列挙します.

Scala: Javaを置き換える勢いがある、現在もっとも注目の言語. オブジェクト指向と関数型の両方の特徴をもつハイブリッド言語.

Clojure: JVM上で動作するLisp言語. Scalaのライバル.

Haskell: もっとも関数型言語の特徴をもつ言語. 難しい概念が乱立する言語.

Elixir: 次に来る大物Web言語. 並行性と信頼性に特徴がある.

どうやって勉強するか

学びたい言語を決めて、その言語の本を読むのがよい勉強法だと思います. 以下、自分が勉強した経験をもとに、参考情報を載せます。

MOOCというオンラインでプログラミングを学べるWebサイトがあります. Scala:

Haskell:

Clojure:

書籍は以下が古典として有名です. 計算機プログラムの構造と解釈(通称SICP)

関数プログラミング実践入門. Haskell を題材に 関数型言語について解説してる本.

28 Nov 2015, 18:28

mindwave moblie で 瞑想力を鍛える!瞑想の効果と可視化について

はじめに

ストレスが多い世の中ですが、ストレス対処法には瞑想がオススメ。

グーグル・インテル・ゴルードマンサックスなどの大手企業が研修に瞑想を 取り入れ、スティーブ・ジョブズ、ビル・ゲイツ、イチローなどの成功者 たちが瞑想に取り組んでいます.

今日は、瞑想の効果と、mindwave mobile による瞑想状態の可視化について まとめて見ました.

瞑想の効果

瞑想には、さまざまな効果が確認されています.

  • ストレスがへる
  • 不安がなくなる
  • 集中力が上がる
  • アイディア力が上がる
  • ポジティブ思考になれる
  • やる気を起こす
  • よく眠れる
  • うつな気分が緩和される

個人的な体験

個人的な体験を書くと、自分が瞑想に興味を持ったのは、 ケリー・マクゴナガル著『スタンフォードの自分を変える教室』の本で 瞑想がやる気を引き出すことが解説されていたからでした.

それまで、瞑想というと、仏教に結びついた宗教臭さを感じていたのですが、 この本を読むことで、そんな胡散臭さが拭い去ら、瞑想に前向きな思いを持ちました.

ブログ記事からの引用

その他、瞑想の効果についてたくさんのブログにかかれています. いくつかピックアップしてみます.

不眠の原因となる自律神経の乱れや、不安、ストレスなどが瞑想を行うことに よって改善されるため、眠りやすくなることがわかりました。

瞑想は宗教と一切関係ない。瞑想は、宗教が誕生する前から存在していたんだ。

瞑想中の脳は普段行っている「情報処理」が停止している状態であるとわかっています。 瞑想時には、脳が情報処理を行っていることを示す「ベータ波」が減少するそうです

スティーブ・ジョブズ、ビル・ゲイツ、イチロー、マドンナ、ビートルズ、ク リント・イーストウッド、ヒラリー・クリントン、ビルフォード、リチャード・ ギア、稲盛和夫、長谷部誠、長嶋茂雄などのように、成功者の中には『瞑想』 を実践している、あるいは実践していた人がたくさんいます。

mindwave mobile

瞑想のコツは、呼吸に集中してなにもかんがえないこと.

さて、瞑想しようとしたとき、自分は本当に瞑想できているのだろうか??

そこで、そんな瞑想状態を可視化するためのツールか存在する! それが、これ、mindwave mobileだ.

1万7000円するが、思い切って買ってしまいました!

瞑想の脳トレをしよう!

これをつかうと、脳波データを取得することができます.

瞑想中の脳波は、アルファ波やθ波がでている状態. これを、mindwaveによって可視化しようと思いました.

筋トレも具体的な数値が見えるとやる気がでるように、 脳トレも、*具体的な数値目標* がみえるようになれば、 やる気が出るのでは??

mindwaveには、様々なAPPが無料・有料で公開されている. 瞑想用のアプリもあるので、紹介する.

Meditation Journal

PC用有料アプリ.

日々の瞑想状態をカレンダに記録していくアプリ. 一日の瞑想状態の平均値や分散値などの統計グラフを 見ることができる. これを毎日つかっている.

瞑想Hack!!

さて、本題. 瞑想データをPythonから取得するライブラリがある.

このライブラリを利用して、瞑想データを取得するスクリプトを書いてみた.

from NeuroPy import NeuroPy

# コールバック用メソッド
def meditation_callback(value):
    print "Meditation Rate:", value
    return None

# 接続
obj = NeuroPy("COM4")

# コールバック関数を登録
obj.setCallBack("meditation", meditation_callback)

# 処理をスタート
obj.start()

while True:
    None

コンソールから実行すると、瞑想データが0-100の間で取れる.

さて、これからどんなハッキングをしようかな.

以上、Happy Hacking!!

28 Nov 2015, 09:33

ソートアルゴリズムのまとめと実装(Python)

はじめに

以下の本を読みながら、アルゴリズムの勉強を始めてます.

挿入ソート(Insertion Sort)

挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列 してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計 算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、し ばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴ リズムであり、オンラインアルゴリズムである。

ALDS1_1_A

<div class="outline-text-3" id="text-orgheadline3">
  <p>
    サンプル問題(AOJ): <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> N = int(input())<br /> A = list(map(int, input().split()))
  </p>

  <p>
    def insertion_sort(A, N):<br /> for i in range(1, N):<br /> v = A[i]<br /> j = i &#8211; 1<br /> while j >= 0 and A[j] > v:<br /> # vより大きければ右へずらす<br /> A[j+1] = A[j]<br /> j -= 1<br /> A[j+1] = v<br /> print(*A)
  </p>

  <p>
    print(*A)<br /> insertion_sort(A, N)<br /> [/sourcecode]
  </p>
</div>

バブルソート(Bubble Sort)

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要 素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、ア ルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことか ら、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともい う。(単に交換法と言う場合もある)

ALDS1_2_A

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    サンプル問題(AOJ) <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> N = int(input())<br /> A = list(map(int, input().split()))
  </p>

  <p>
    def bubble_sort(A, N):<br /> cnt = 0<br /> flag = True<br /> while(flag):<br /> flag = False<br /> for i in range(N-1, 0, -1):<br /> if(A[i-1] > A[i]):<br /> A[i-1], A[i] = A[i], A[i-1]<br /> cnt += 1<br /> flag = True
  </p>

  <p>
    print(&#8221; &#8220;.join(list(map(str, A))))<br /> print(cnt)
  </p>

  <p>
    bubble_sort(A, N)<br /> [/sourcecode]
  </p>
</div>

選択ソート(Selection Sort)

選択ソート(英: selection sort)は、ソートのアルゴリズムの一つ。配列さ れた要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをお こなうこと。最悪計算時間がO(n2)と遅いが、 アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。 後述するように、安定ソートではない。

ALDS1_2_B

<div class="outline-text-3" id="text-orgheadline7">
  <p>
    サンプル問題(AOJ) <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B&lang=jp</a>
  </p>

  <p>
    ↓のコード、どうしてもAOJ のテストケースを通せなかった。 どこかバグってるのだろうか??
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> def selection_sort(A, N):<br /> count = 0<br /> for i in range(0, N):<br /> minj = i<br /> for j in range(i, N):<br /> if(A[minj] > A[j]):<br /> minj = j<br /> if(minj != i):<br /> count += 1<br /> A[minj], A[i] = A[i], A[minj]
  </p>

  <p>
    print(&#8221; &#8220;.join(map(str, A)))<br /> print(count)
  </p>

  <p>
    N = int(input())<br /> A = list(map(int, input().split()))<br /> selection_sort(A, N)<br /> [/sourcecode]
  </p>
</div>

シェルソート(Shell Sort)

基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列され たデータに対しては高速」という特長があるものの、「隣り合った要素同士し か交換しない」ため、あまり整列されていないデータに対しては低速であった。

そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソート しておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適 用したのがシェルソートである。

ALDS1_2_D

<div class="outline-text-3" id="text-orgheadline9">
  <p>
    サンプル問題(AOJ)
  </p>

  <ul class="org-ul">
    <li>
      <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D&lang=jp</a>
    </li>
  </ul>

  <p>
    コード省略。解けない..
  </p>
</div>

マージソート(Merge Sort)

分割統治法によるソート.

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1 個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列 も整列されている、というボトムアップの分割統治法による。大きい列を多数 の列に分割し、そのそれぞれをマージする作業は並列化できる。

n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分 割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレース なソートも提案されているが、通常O(n)の外部記憶を必要とする。

(ナイーブな)クイックソートと比べると、最悪計算量は少ない 。ランダムなデータでは通常、クイックソートのほうが速い。

ALDS1_5_B

<div class="outline-text-3" id="text-orgheadline11">
  <p>
    サンプル問題(AOJ) <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> def merge(A, left, mid, right):<br /> global count<br /> L = A[left:mid] + [1000000001]<br /> R = A[mid:right] + [1000000001]<br /> i = j = 0<br /> for k in range(left, right):<br /> if L[i] <= R[j]: A[k] = L[i] i += 1 else: A[k] = R[j] j += 1 count += right - left def merge_sort(A, left, right): if left + 1 < right: mid = (left + right) // 2 merge_sort(A, left, mid) merge_sort(A, mid, right) merge(A, left, mid, right) N = int(input()) A = list(map(int, input().split())) count = 0 merge_sort(A, 0, N) print(*A) print(count) [/sourcecode] </div> </div> </div> 

    <div id="outline-container-orgheadline12" class="outline-2">
      <h2 id="orgheadline12">
        クイックソート(Quick Sort)
      </h2>

      <div class="outline-text-2" id="text-orgheadline12">
        <blockquote>
          <p>
            クイックソート (quicksort) は、1960年にアントニー・ホーアが開発した ソートのアルゴリズム。分割統治法の一種。
          </p>

          <p>
            最良計算量および平均計算量はO( nlog n )である。他のソート法と比べて、 一般的に最も高速だといわれているが対象のデータの並びやデータの数によっ ては必ずしも速いわけではなく、最悪の計算量はO( n^2)である。また数々 の変種がある。 安定ソートではない。
          </p>
        </blockquote>

        <ul class="org-ul">
          <li>
            <a href="https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88">クイックソート &#8211; Wikipedia</a>
          </li>
        </ul>
      </div>

      <div id="outline-container-orgheadline13" class="outline-3">
        <h3 id="orgheadline13">
          ALDS1_6_B, ALDS1_6_C
        </h3>

        <div class="outline-text-3" id="text-orgheadline13">
          <p>
            サンプル問題(AOJ) <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_B&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_B&lang=jp</a> <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C&lang=jp</a>
          </p>

          <p>
            [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> def partition(a, p, r):<br /> x = a[r][1]<br /> i = p &#8211; 1<br /> for j in range(p, r):<br /> if a[j][1] <= x: i = i + 1 a[i], a[j] = a[j], a[i] a[i + 1], a[r] = a[r], a[i + 1] return i + 1 def quicksort(a, p, r): if p < r: q = partition(a, p, r) quicksort(a, p, q - 1) quicksort(a, q + 1, r) import sys n = int(input()) a = [] for i in range(n): suit, num = sys.stdin.readline().split() a += [[suit, int(num), i]] quicksort(a, 0, len(a) - 1) [/sourcecode] </div> </div> </div> 

            <div id="outline-container-orgheadline14" class="outline-2">
              <h2 id="orgheadline14">
                Python 標準ライブラリ
              </h2>

              <div class="outline-text-2" id="text-orgheadline14">
                <p>
                  リストオブジェクトに対する操作として、 sort()や, reverse()メソッドが用意されている.
                </p>

                <p>
                  [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> listobj.sort()<br /> listobj.reverce()<br /> [/sourcecode]
                </p>

                <ul class="org-ul">
                  <li>
                    <a href="http://qiita.com/fantm21/items/6df776d99356ef6d14d4">【Python】ソート &#8211; Qiita</a>
                  </li>
                  <li>
                    <a href="http://www.pythonweb.jp/tutorial/list/index11.html">要素のソート(sortメソッド, reverseメソッド) &#8211; リスト &#8211; Python入門</a>
                  </li>
                </ul>
              </div>
            </div>

            <div id="outline-container-orgheadline15" class="outline-2">
              <h2 id="orgheadline15">
                Special Thanks
              </h2>

              <div class="outline-text-2" id="text-orgheadline15">
                <ul class="org-ul">
                  <li>
                    <p>
                      <a href="http://gigazine.net/news/20140501-sorting/">数あるソートアルゴリズムをビジュアル化し堪能できるサービス「SORTING」 &#8211; GIGAZINE</a>
                    </p>

                    <p>
                      ソーティングアルゴリズムを可視化した動画がオモシロイ.
                    </p>
                  </li>
                </ul>

                <p>
                  <iframe width="560" height="315" src="https://www.youtube.com/embed/kPRA0W1kECg" frameborder="0" allowfullscreen></iframe>
                </p>

                <ul class="org-ul">
                  <li>
                    <a href="http://kojikoji75.hatenablog.com/entry/2013/09/21/115937">プログラムで簡単理解! 7つの超重要な整列アルゴリズム(ソートアルゴリズム)まとめ &#8211; TechNote</a>
                  </li>
                  <li>
                    <p>
                      <a href="http://qiita.com/hiso/items/5c36f50c7de61fe870a2">基本的なソートアルゴリズムまとめ+α。C言語での実装例 &#8211; Qiita</a>
                    </p>

                    <p style="font-size:32px">
                      以上、Happy Hacking!!
                    </p>
                  </li>
                </ul>
              </div>
            </div>

23 Sep 2015, 10:20

railsで努力の名言を表示するのサイトを作成

Ruby on Rails をいじってみたくなったので、試しにWebサイトを作成してみた.

偉人の名言をただ表示していているだけのサイトです. heroku上で動作.

Motivation

以下の記事に触発された.

シルバーウィークも5日間あることから、 簡単なサイトをつくってみようと思った.

  <div id="outline-container-orgheadline2" class="outline-2">
    <h2 id="orgheadline2">
      製作までにやったこと
    </h2>

    <div class="outline-text-2" id="text-orgheadline2">
      <p>
        railsのレールに乗るのに時間がかかった. 以下のチュートリアルをやった.
      </p>

      <ul class="org-ul">
        <li>
          <a href="http://openbook4.me/projects/92">小学生でもわかるRuby on Rails入門 | OpenBook</a>
        </li>
        <li>
          <a href="http://dotinstall.com/lessons/basic_rails_v2">Ruby on Rails 4入門 (全28回) &#8211; プログラミングならドットインストール</a>
        </li>
        <li>
          <a href="http://railstutorial.jp/">Ruby on Rails チュートリアル:実例を使って Rails を学ぼう</a>
        </li>
        <li>
          <a href="http://ruby-rails.hatenadiary.com/entry/20140813/1407915718">Railsを始めたばかりの人向け!Railsの仕組みを一から理解しながらブログを作成する &#8211; Rails Webook</a>
        </li>
      </ul>

      <p>
        いろんなチュートリアルをやることで、 なんとなくアプリをどう作るかが見えてきた.
      </p>

      <p>
        最終的には、2日間かけてサイトを作成.
      </p>

      <p style="font-size:32px">
        以上、Happy Hacking!!
      </p>
    </div>
  </div>

  <div id="outline-container-orgheadline3" class="outline-2">
    <h2 id="orgheadline3">
      これからどうするか
    </h2>

    <div class="outline-text-2" id="text-orgheadline3">
      <p>
        名言のサイトを機能拡張しようと思っていたのだが、 このジャンルでは、すでに先人がアイデアを実現していた.
      </p>

      <ul class="org-ul">
        <li>
          fesh <a href="http://www.fesh.jp/">http://www.fesh.jp/</a>
        </li>
        <li>
          OneQuote <a href="http://onequote.org/">http://onequote.org/</a>
        </li>
      </ul>

      <p>
        これに変わるアイデアがでてこないので、 名言はひとまず終わりにしようかと考え中.
      </p>

      <p>
        しかし、せっかくチュートリアルを終わらせてrailsが分かるように なってきたので、ここで終わらせたくないなぁ.
      </p>
    </div>
  </div>

13 Sep 2015, 10:36

今何時?に大々的に答えてくれるEmacsコマンド

今何時か知りたい. そんなときに、便利なコマンド.

time-now

超ビッグな表示で、時間が表示される.

[sourcecode language=”text” title=”” ]
(defun my:time-now ()
(interactive)
(let ((temp-buffer-show-function ‘switch-to-buffer))
(with-output-to-temp-buffer
“*time-now*”
(princ (format-time-string “%H:%M”)))
(setq buffer-face-mode-face ‘(:height 2000))
(buffer-face-mode)))
(global-set-key (kbd “C-“) ‘my:time-now)
[/sourcecode]

2015-09-13-192948_973x353_scrot.png

<p>
  時間を確認したら、q を押して閉じる.
</p>

<p>
  またこんなことで時間を潰してしまった。。。
</p>

<p style="font-size:32px">
  以上、Happy Hacking!!
</p>

12 Sep 2015, 02:01

オンライン学習 Functional programming with Clojure をやってみた

Clojureが学べるMOOC, Functional programming with Clojureをやってみました.

特徴

Clojureの文法と 関数型の考え方が学べるコース.

  • immutable な データ構造
  • 高階関数
  • 再帰

動画があるわけではなくて、説明とexerciseが交互に並んでいる.

exerciseの評価方法がおもしろい. githubのリポジトリをclone して問題をとき、完了したら pull request を出す. すると、 travisがテストを実行して、点数を出す.

内容は、そこまで難しくない. 自分は、最終ページの応用問題をまだやっていないが、 ここまでの学習時間は20時間程度.

clojureは文法がシンプルなので、 この講座のなかだけで、一通りの作法はみにつく.

感想

書籍による学習よりも、楽しく文法を身につけることができた.

この講座をやることによって、基本的な文法は身についた(つもり). 忘れないようになにかに応用したいところだ. みんなどうやって、 clojure力をつけているのだろうか.

同じようなオンラインの学習教材として、4clojureというものがある. これからは、4clojureをやることで、clojure力をつけていこうと思う.

09 Sep 2015, 13:00

対話力が足りない

年月を重ねると、5年、10年先の先輩に追いつくことができるのだろうか?

最近、このことをよく考える. プログラミングスキルだけを磨いていても、 一人前のプログラマにはなれない気がしてきた. 自分に足りないものはなんだろうか? それは、対話力のような気がしてきた.

対話力が足りない

もともと、会話することに苦手意識がある. 会話のない家庭に育ったからだと思う. 最近、自分の会話力のなさをよく痛感するようになった. 対話する力が自分には欠けている.

対話力は、理解力と説明力に分解できる. 両者に共通していることは、一番大切なことを伝えるということだ.

理解力

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    理解力は、相手の言っていることを理解すること. 話の中で、一番言いたいことを見つけ出して、 それを一段高い視点からとらえる行為. たとえば、進捗報告を聞くとすると、なにが原因で遅れが生じているのか、 ということが、もっとも聞きたいことだ。
  </p>
</div>

説明力

<div class="outline-text-3" id="text-orgheadline3">
  <p>
    説明力は、相手に言いたいことを伝えること. 話の中で、一番言いたいことを相手に伝えなければいけない. 伝えたいことと、その根拠を論理立てて相手に伝える行為.
  </p>
</div>

対話力をつけるにはどうすればいいか?

以下が、対話力克服のために考えた改善方法だ.

  • 失敗記録をつける
  • 反復練習をする
  • 話を高い視点から眺める
  • 一番言いたいことを意識する

理解力

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    理解力をつけるためには、 論理的に話の流れを分解するクセをつける. 目の前の言葉の羅列から一歩ひいて、 相手の言いたいことを理解するように努める.
  </p>
</div>

説明力

<div class="outline-text-3" id="text-orgheadline6">
  <p>
    説明力をつけるには、 はじめに結論を言ってそのあとに理由を述べるクセをつける. 話の流れが、支離滅裂にならないように注意する. 失敗したら、その結果をメモ帳につける. 再び失敗しないように家でシミュレーションをするようにする.
  </p>

  <p>
    小さな努力を積み重ねないと、なにも自分は変わらない.
  </p>
</div>