18 Dec 2015, 17:52

TopCoder SRM 676 Div2 250 FarmvilleDiv2(参加)

問題

n個の植物がある. それぞれ time[i]秒成長するのにかかる.

cost[i]をbudgetのなかから支払うと、1秒成長を早めることができる.

time, cost, budgetが与えられる. 植物を育てることのできる時間の最小値をかえせ.

方針

costを昇順にソーティング. costの低い順に時間を計算

  • budgetがまだあるときは、total時間は加算しない.
  • budgetがないときは、time分 total時間を加算する.

解答

timeとcostをインデックスをそろえながらソーティングするよい方法が思い つかなかったので、自力でソーティングアルゴリズムを実装した。

なにかよい方法はないものか。他の人の解答をみて研究することにする.

[sourcecode language=”python” title=”” ]
class FarmvilleDiv2:
def insertion_sort(self, time, cost, N):
for i in range(1, N):
v1 = time[i]
v2 = cost[i]
j = i – 1
while j >= 0 and cost[j] > v2:
time[j + 1] = time[j]
cost[j + 1] = cost[j]
j -= 1
time[j + 1] = v1
cost[j + 1] = v2
return time, cost

def minTime(self, time, cost, budget):
time = list(time)
cost = list(cost)
time, cost = self.insertion_sort(time, cost, len(cost))

ret = 0

for t, c in zip(time, cost):
for i in range(t):
if budget – c >= 0:
budget -= c
else:
ret += 1

return ret
[/sourcecode]

18 Dec 2015, 10:31

TopCoder SRM 575 Div2 250 TheSwapsDivTwo (練習)

TopCoder

問題

int型配列が与えられる。 2個の数値の位置を入れ替える場合、得られるユニークな数列が何通りあるか.

方針

全通り swapしてみて、ユニークな数列の数を数える.

回答

[sourcecode language=”python” title=”” ]
class TheSwapsDivTwo:
def find(self, sequence):
s = set()
n = len(sequence)

for i in range(n – 1):
for j in range(i + 1, n):
l = list(sequence)
l[i], l[j] = l[j], l[i]
s.add(tuple(l))

return len(s)
[/sourcecode]

18 Dec 2015, 03:04

TopCoder SRM 672 Div2 500 SubstitutionCipher

問題

可換暗号の問題. 暗号化のために可換テーブルを利用する。

ところが、この可換テーブルがなくなってしまった。

a,b, y が与えられるので a -> b の変換を手がかりにして、 暗号化されたy から 復号化された文字列xを求めよ。

方針

可換テーブルを b->aの複合ルールから求めてそれを y に適用する.

文字が25文字のとき、全てのアルファベットの中で利用されていない 文字を調べてテーブルに追加する必要がある.

回答

[sourcecode language=”python” title=”” ]
allchar = list(“ABCDEFGHIJKLMNOPQRSTUVWXYZ”)
class SubstitutionCipher:
def notIn(self, s):
return “A”

def decode(self, a, b, y):
cipher = {}

for i in range(len(a)):
cipher[b[i]] = a[i]

if len(cipher) == 25:
remain_a = list(set(allchar) – set(a))[0]
remain_b = list(set(allchar) – set(b))[0]
cipher[remain_b] = remain_a

x = “”
for i in range(len(y)):
if y[i] not in cipher:
return “”
x += cipher[y[i]]

return x
[/sourcecode]

18 Dec 2015, 01:46

TopCoder SRM672 Div2 Easy SetPartialOrder

TopCoder

問題

Intの配列AとBが与えられる。

  • 等しいなら”EQUAL”、
  • AがBのサブセットなら”LESS”、
  • BがAのサブセットなら”GREATER”、
  • それ以外なら”INCOMPARABLE”と返す。

方針

setを使う. サブセットは < で比較するのを始めて知った. issubset というメソッドもあるらしい.

回答

[sourcecode language=”python” title=”” ]
class SetPartialOrder:
def compareSets(self, a, b):
a = set(a)
b = set(b)

if a == b:
return “EQUAL”
elif a < b: return "LESS" elif a > b:
return “GREATER”
else:
return “INCOMPARABLE”
[/sourcecode]

16 Dec 2015, 07:12

テーブル駆動方式をつかってif文やswitch文をシンプルにする

Code Complete を読んでいて、テーブル駆動方式というものを知った.

条件分岐のロジックを配列やテーブルにデータをもたせ、そこからデータ取得することで処理を行う方式

入力されたキーで分岐して何か処理させたいとき、 普通はif文やswitch文を利用するのだけれども、 テーブル(配列)を利用すると、処理が短くかけるというテクニック.

  • キーが数値のときは配列をつかう
  • キーが文字のときは連想配列をつかう

テーブルには値を入れてもいいし、オブジェクトや無名関数をいれてもいい.

前回取り組んだ TopCoder SRM 675 Div2 Easy問題に適用してみた.

問題

異なる長さの単位の変換を考える.

  • 1 ft = 12 in
  • 1 yd = 3 ft
  • 1 mi = 1760 yd

amount と fromUnit と toUnit が与えられるので、 toUnit の単位の amountを計算せよ!

普通の解き方

条件を全てif文で分岐して解く.

class LengthUnitCalculator:
    def calc(self, amount, fromUnit, toUnit):
        if fromUnit == toUnit:
            return amount

        if fromUnit == "in":
            if toUnit == "ft":
                return amount / 12
            elif toUnit == "yd":
                return amount / (12 * 3)
            elif toUnit == "mi":
                return amount / (12 * 3 * 1760)
        if fromUnit == "ft":
            if toUnit == "in":
                return amount * 12
            elif toUnit == "yd":
                return amount / 3
            elif toUnit == "mi":
                return amount / (3 * 1760)
        if fromUnit == "yd":
            if toUnit == "in":
                return amount * 3 * 12
            elif toUnit == "ft":
                return amount * 3
            elif toUnit == "mi":
                return amount / 1760
        if fromUnit == "mi":
            if toUnit == "in":
                return amount * 12 * 3 * 1760
            elif toUnit == "ft":
                return amount * 3 * 1760
            elif toUnit == "yd":
                return amount * 1760
        return 0.0

テーブル駆動方式

連想配列をつかって、キーと値を対応づける.

class LengthUnitCalculator:
    def calc(self, amount, fromUnit, toUnit):
        units = {
            'in': 1,
            'ft': 12,
            'yd': 36,
            'mi': 63360
        }
        return float(amount) * units[fromUnit] / units[toUnit]

うーん、鮮やか!!

12 Dec 2015, 13:41

プログラミングに興味がなくなってしまった

このブログ、10月, 11月と2ヶ月間、更新しなかった。

なぜなら、技術的なこと、 とくにプログラミングに対して興味が持てなくなってしまったからだ。

自分でも、なんでこんなことになってしまったのか、わからない。

かつては、プログラミングが大好きで、プログラマになってよかったと 心から思っていたので。

今日、精神科の先生からうつ病の診断書が出された. うつ病による2ヶ月の自宅療養が必要とのこと。

IMG_UTU.jpg

ここに至るまでの心の変化を過去記事とtwitterから振り返る.

プライベート

去年までは、熱心にMOOCの勉強をしていたのだが、 MOOCはやっぱり自分には難しく、消化不良で終わることが多かった.

以下の記事を書いたのが, 6月.

MOOCをやめて、書籍による勉強に切り替えたのだが、 書籍による学習も、挫折を繰り替えした. どうも、自分は理解力がないというか、頭が悪いというか、 どの本を読んでも、理解できずに途中で読むのを諦めてしまった.

以下の本を読んでどれもこれも挫折したのが精神的に響いた. 今思えば、どれも難しい本なので挫折して当然なのだけれども.

自分は理解力がないという脅迫観念がいつも頭をよぎるようになった.

仕事でも話す力や理解する力が足りないような気がしてきた.

なにをやってもうまくいかないので、 いったいプログラミングはなにが楽しいのだろうと考えてみた.

なにかものをつくると楽しさを思い出すのではないかと思って、 なにかを作ろうとした.

Emacs Lisp と Ruby on Railsに手を出した. どちらも、アイデアと技術力不足で挫折した.

なにをやっても挫折してしまうので、 ここにきて、次になにをすればよいのかわからなくなってしまった.

仕事

このブログは会社の同僚も読んでいるので、仕事のことは、軽めに.

半年間、プログラミングを仕事でしなかった.

プログラミングがしたくて、今年もいろんな言語に手を出した. R, Scala, Emacs Lisp, Scheme, CommonLisp, Clojure, Python…

次の仕事は、Pythonによる新規開発だと言われたので、Pythonをたくさん勉強した.

けど、やむを得ない事情があって、Javaの流用開発になった.

やっとプログラミングができると思って初めはうれしかった.

でも、流用するコードは、複雑で読んでも理解できない. 次第に嫌になってきた.

流用開発は、当たり前にあることだし、それが嫌だなんて甘えだとおもってる.

でも、コードを見るのがとても苦痛になってしまった. 今は、プログラミングが嫌で嫌でしかたがない.

まとめ

とりあえず、休職したい.

かつてのように、技術的興味が回復するのを祈る.

もし、技術的なことに興味が持てなければ、 この先プログラマとして仕事をしていく自信がもてない.

12 Dec 2015, 08:05

Pythonでナップザック問題(AOJ)

今日は、ナップザック問題を勉強しました.

今回は、AOJの問題をPythonで解いてみます.

ナップザック問題については、以下のサイトを参考にしました.

以下、記号の意味などは、上記サイトを参照願いします.

深さ優先探索

[sourcecode language=”python” title=”” ]
N, W = map(int, raw_input().split())

v = [0] * N
w = [0] * N

for i in range(N):
v[i], w[i] = map(int, raw_input().split())

def rec(i, j):
if i == N:
res = 0
elif j < w[i]: res = rec(i + 1, j) else: res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]) return res print(rec(0, W)) [/sourcecode]

これだと、時間制限に引っかかって、テストが通らない

  <div id="outline-container-orgheadline2" class="outline-2">
    <h2 id="orgheadline2">
      メモ化再帰
    </h2>

    <div class="outline-text-2" id="text-orgheadline2">
      <p>
        深さ優先探索を改良.
      </p>

      <p>
        メモ化のためのテーブル dp を宣言する.
      </p>

      <p>
        rec(i,j)の結果は、(i,j)によって一意に決まるため、計算結果の dp[i][j]を返す.
      </p>

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

      <p>
        v = [0] * N<br /> w = [0] * N<br /> dp = [[-1 for i in range(W + 1)] for j in range(N + 1)]
      </p>

      <p>
        for i in range(N):<br /> v[i], w[i] = map(int, raw_input().split())
      </p>

      <p>
        def rec(i, j):<br /> if dp[i][j] != -1:<br /> return dp[i][j]
      </p>

      <p>
        if i == N:<br /> res = 0<br /> elif j < w[i]: res = rec(i + 1, j) else: res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]) dp[i][j] = res return res print(rec(0, W)) [/sourcecode] </div> </div> 

        <div id="outline-container-orgheadline3" class="outline-2">
          <h2 id="orgheadline3">
            動的計画法
          </h2>

          <div class="outline-text-2" id="text-orgheadline3">
            <p>
              漸化式を解く.
            </p>

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

            <p>
              v = [0] * N<br /> w = [0] * N<br /> dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
            </p>

            <p>
              for i in range(N):<br /> v[i], w[i] = map(int, raw_input().split())
            </p>

            <p>
              for i in range(N &#8211; 1, -1, -1):<br /> for j in range(W + 1):<br /> if j < w[i]: dp[i][j] = dp[i + 1][j] else: dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]) print(dp[0][W]) [/sourcecode] </div> </div> 

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

                <div class="outline-text-2" id="text-orgheadline4">
                  <ul class="org-ul">
                    <li>
                      <a href="http://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html">最強最速アルゴリズマー養成講座:病みつきになる「動的計画法」、その深淵に迫る (1/4) &#8211; ITmedia エンタープライズ</a>
                    </li>
                  </ul>
                </div>
              </div>

11 Dec 2015, 14:55

TopCoder SRM 675 Div2 500

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14091&rd=16625

n個の街がある。二つの街を移動するには、dist[i][j]時間かかる.

また、k magic pointが与えられる。 magic pointをつかうと移動時間を半分にすることができる.

街0から1への最小の移動時間を求めよ.

方針

ダイクストラ法をつかうのだと思った.

以下のリンクを参考に実装してみた.

ポイントは、magic pointをk回つかうことで、最小の移動時間が変動すること. 0から1へk回 magic pointをつかった結果を記憶しておいて、 最後に、その結果のなかでの最小値を求める.

で、いいのかな?? よくわからず、もう5時間くらい悩んでいるのだけれども。。。

回答

10 Dec 2015, 15:31

TopCoder SRM 675 Div2 250

2年ぶりに TopCoder に参加しました。

以前はC++erだったけど、Pythonに武器を持ち替えて参戦.

事前準備のために20時間くらいトレーニングを積んだ.

結果、easy問題すら解けませんでした。システムテストで落とされました。

落とされた原因を延々と考えていて、ようやく分かった!

Python3だとテストが成功するのだけれども、Python2だと失敗することに気づく.

TopCoderのPythonのバージョンは2系です!!

割り算をすると、python3は、勝手にfloat型になったのでテストが通ったけど、 python2はint型のままなので、小数点以下が計算されなかったという落ち. そして、float型なんて考慮していなかったという別の盲点もあった.

middle 問題は、解けなかった。

09 Dec 2015, 10:42

TopCoderで動的計画法とメモ化再帰の問題を解いてみる(Python)

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

今日は、動的計画法とメモ化再帰について勉強しました.

動的計画法(Dynamic Programming)

[sourcecode language=”text” title=”” ]
対象となる問題を複数の部分問題に分割し、
部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ
[/sourcecode]

分類

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    動的計画法には、トップダウン方式、ボトムアップ方式の二つがある. 以下のように呼ばれることが多い.
  </p>

  <ul class="org-ul">
    <li>
      再帰関数のメモ化 ・・・メモ化再帰、メモ化、トップダウン方式
    </li>
    <li>
      漸化式 + ループ ・・・動的計画法、分割統治法、ボトムアップ方式
    </li>
  </ul>
</div>

トップダウン方式(メモ化再帰)

<div class="outline-text-3" id="text-orgheadline3">
  <p>
    一度計算した結果を覚えておいて、 同じ計算をしようとしたときに記憶していた値を利用する.
  </p>

  <p>
    再帰関数を利用することで、問題を解く.
  </p>
</div>

ボトムアップ方式(漸化式)

<div class="outline-text-3" id="text-orgheadline4">
  <p>
    漸化式を立てて、順々に漸化式を解いていく.
  </p>

  <p>
    for文を回すことで、問題を解く.
  </p>
</div>

問題

SRM413 Div1 Medium

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    以下の問題をPythonで解いてみる.
  </p>

  <ul class="org-ul">
    <li>
      <a href="http://www.itmedia.co.jp/enterprise/articles/1003/06/news002_3.html">最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (3/5) &#8211; ITmedia エンタープライズ</a>
    </li>
    <li>
      <a href="https://community.topcoder.com/stat?c=problem_statement&pm=9922&rd=13504">https://community.topcoder.com/stat?c=problem_statement&pm=9922&rd=13504</a>
    </li>
  </ul>
</div>

<div id="outline-container-orgheadline6" class="outline-4">
  <h4 id="orgheadline6">
    動的計画法
  </h4>

  <div class="outline-text-4" id="text-orgheadline6">
    <p>
      <b>まとめらる処理をまとめて、同じ計算を行わないようにする</b>
    </p>

    <p>
      途中経過をメモしておいて、次の計算で使うというのが動的計画法. ここでは、i を順に計算していく.
    </p>

    <p>
      [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> class InfiniteSequence2:<br /> def calc(self, n, p, q, x, y):<br /> dp = [0 for i in range(n + 1)]<br /> dp[0] = 1
    </p>

    <p>
      for i in range(1, n + 1):<br /> nexta = i / p &#8211; x<br /> nextb = i / q &#8211; y
    </p>

    <p>
      if nexta <= 0: a = 1 else: a = dp[nexta] if nextb <= 0: b = 1 else: b = dp[nextb] dp[i] = a + b return dp[n] [/sourcecode] </div> </div> 

      <div id="outline-container-orgheadline7" class="outline-4">
        <h4 id="orgheadline7">
          深さ優先探索
        </h4>

        <div class="outline-text-4" id="text-orgheadline7">
          <p>
            トップダウンで探索をしていく.
          </p>

          <p>
            [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> class InfiniteSequence2:<br /> def calc(self, n, p, q, x, y):<br /> return self.dfs(n, p, q, x, y)
          </p>

          <p>
            def dfs(self, n, p, q, x, y):<br /> if n <= 0: return 1 return self.dfs(n / p - x, p, q, x, y) + self.dfs(n / q - y, p, q, x, y) [/sourcecode] </div> </div> 

            <div id="outline-container-orgheadline8" class="outline-4">
              <h4 id="orgheadline8">
                メモ化再帰
              </h4>

              <div class="outline-text-4" id="text-orgheadline8">
                <p>
                  一度計算した点は覚えておいて、余計な計算をしないのがメモ化再帰.
                </p>

                <p>
                  [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> class InfiniteSequence2:<br /> def calc(self, n, p, q, x, y):<br /> self.memo = {}<br /> return self.dfs(n, p, q, x, y)
                </p>

                <p>
                  def dfs(self, n, p, q, x, y):<br /> if n <= 0: return 1 if n in self.memo: return self.memo[n] self.memo[n] = self.dfs(n / p - x, p, q, x, y) + self.dfs(n / q - y, p, q, x, y) return self.memo[n] [/sourcecode] </div> </div> </div> </div> 

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

                    <div class="outline-text-2" id="text-orgheadline10">
                      <ul class="org-ul">
                        <li>
                          <a href="http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html">最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) &#8211; ITmedia エンタープライズ</a>
                        </li>
                        <li>
                          <a href="http://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html">最強最速アルゴリズマー養成講座:病みつきになる「動的計画法」、その淵に迫る (1/4) &#8211; ITmedia エンタープライズ</a>
                        </li>
                        <li>
                          <a href="http://shindannin.hatenadiary.com/entry/20131208/1386512864">動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる &#8211; じじいのプログラミング</a>
                        </li>
                        <li>
                          <a href="http://www.slideshare.net/iwiwi/ss-3578511">プログラミングコンテストでの動的計画法</a>
                        </li>
                      </ul>
                    </div>
                  </div>