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]

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>

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>

20 Nov 2013, 14:47

C++でのSTLアルゴリズムの使い方まとめ(sort)

C++ STLの algorithmで便利そうなものをメモしてきます.

並べ替え・ソート(sort)

  • 並べ替えを実施します。
  • vectorなどのランダムアクセス可能なコンテナで利用可能。
  • ロジックはクイックソートを利用している。

使い方

sortの引数として、並べ替えたい初めと終わりのイテレータを渡す。たいていは begin(),end().

sort(a.begin(), a.end());

デフォルトでは小さい順(less())に並べ替えられる。大きい順に並べ替える時は、以下のようにgreater<>()を引数として渡す。

sort(a.begin(), a.end(), greater<int>());

#include <algorithm>
#include<vector>
#include<iostream>

using namespace std;

int main()
{
  vector<int> a;
  a.push_back(3);
  a.push_back(1);
  a.push_back(2);

  sort(a.begin(), a.end());
  for( auto x : a ) cout << x;
  cout << endl;

  sort(a.begin(), a.end(), greater<int>());
  for( auto x : a ) cout << x;
  cout << endl;
}

実行結果

$ g++ -std=c++11 sort.cpp
$ ./a
123
321