19 Dec 2015, 04:57

TopCoder SRM 676 Div2 550 BoardEscapeDiv2(参加)

問題

アリスとボブは、r行およびc列のグリッドに分割された矩形ボードを持っています。 グリッドは、String []型sで記述されています。 Sの各文字は、一つのセルを表します。cellには4つのタイプがあります。

  • ‘E’は終了を表しています。任意の数の終了、おそらくゼロがあるかもしれません。
  • ‘T’は正方形は単一のトークンが含まれていることを意味します。最初はボード全体に正確に一つのトークンが存在することになります。
  • ‘#’は、障害物を表します。
  • ‘。’空のセルを表します。

アリスとボブはこのボード上のゲームをプレイします。 ゲームはintkによってパラメータ化されます。トークンは、最初にその上に数kを持っています。 プレイヤーはアリスから始まる、ターンを交互にかかります。プレイヤーのターンは、以下のステップで構成されています。

  • プレイヤーは、下、左、または右のトークン1平方を上に移動します。トークンは、ボードの端に行くことができない、それが障害物をcellに入力することはできません。
  • このトークンが出口にある場合、それはボードから消えます。
  • それ以外の場合は、トークンの数から1を引きます。トークンの数がゼロの場合、ボードから取り外します。

行動を起こすことができない最初のプレーヤーがゲームを失います。 (すでにボードを去ったとき、トークンにもこだわっているときに発生します。)

アリスとボブの両方を最適にプレイすると仮定すると、あなたはString[]型のを与えられ、intkは、ゲームの勝者を計算します。 当選者の名前を返します:「アリス」または「ボブ」のいずれか。戻り値は、大文字と小文字が区別されることに注意してください。

方針

プレイヤーが2人いて、お互いに最適な戦略を取ったとき勝つのはどちらか、 みたいな問題は、WL-Algorithmsというものを利用して解くらしい.

[sourcecode language=”cpp” title=”” ]
boolean isWinning(State pos){
State[] nextStates = { posから到達できる全ての次の状態 };
for(State s : nextStates){
if(!isWinning(s)) return true;
}
return false;
}
[/sourcecode]

  • 相手を必ず負けさせるような手が存在するなら現在の位置では勝ち決定。
  • そのような手がないないのであれば負け。

参考リンクをはっておく. あとで勉強しよう.

今回は、このアルゴリズムにメモ化再帰を適用した.

解答

[sourcecode language=”python” title=”” ]
MAXN = 200

vx = [1, -1, 0, 0]
vy = [0, 0, 1, -1]
memo = [[[-1 for i in range(MAXN)] for j in range(MAXN)] for k in range(MAXN)]

class BoardEscapeDiv2:
def isWinning(self, s, x, y, move):
n = len(s)
m = len(s[0])

if move == 0: return False
if s[x][y] == ‘E’: return False
if memo[x][y][move] != -1: return memo[x][y][move]

for i in range(4):
nx = x + vx[i]
ny = y + vy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m or s[nx][ny] == ‘#’:
continue
if not self.isWinning(s, nx, ny, move – 1):
memo[x][y][move] = True
return True

memo[x][y][move] = False
return False

def findWinner(self, s, k):
n = len(s)
m = len(s[0])

for i in range(n):
for j in range(m):
if s[i][j] == ‘T’:
x = i
y = j

return “Alice” if self.isWinning(s, x, y, k) else “Bob”
[/sourcecode]

おわりに

本番では解けなかった. こういう問題をさらりととけないと Div1には上がれないのか… 道は遠いな.

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 問題は、解けなかった。