読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

Google Code Jam Qualification Round 2017 C

C Bathroom Stallsは横一列にトイレの個室がN室並んでいて、そこにK人が現在使用中の個室から遠くなるように未使用個室入っていくというシチュエーション。漏れると思うんですけど・・・。問題文読んだ瞬間すわDPか?と思ったが全く違っていた。いわゆる電線の雀やどこぞの川辺のカップル状態。この問題の一番の肝は、出力が”K人目が入って行くときの両側の空き(の最大値と最小値)”というもので、どの場所かは求められていない。だからイメージ的には、Nmの棒が与えられてそれを半分に折って行く時、K番目のサイズが分かればOK。そう考えると簡単だ。また半分に折っていくから棒の長さは同じ長さのがたくさんになるのでそれらをまとめて処理できる。具体的には、K>2pとなるpを求め、p回Nを分割し(2p個に分割)、残った棒のK-2p番目の長さを求める。シミュレーションすると分かるが、棒の長さは高々2通りしかない。

def stall(n,k)
    h={n=>1}
    step=1
    while k>step
        f=Hash.new(0)
        h.each_pair{|key,value|
            if key.odd?
                f[key/2]+=value*2
            else
                f[key/2]+=value
                f[key/2-1]+=value
            end
        }
        h=f
        k-=step
        step*=2
    end
    last=0
    a,b=h.keys.max(2)
    if k<=h[a]
        last=a
    else
        last=b
    end

    if last.odd?
        return [last/2,last/2]
    else
        return [last/2,last/2-1]
    end
end

gets.to_i.times{
  n,k=gets.split.map(&:to_i)
  write(stall(n,k)*" ")
}

D Fashion Showはまっさらの時はエイトクイーンの問題に帰着できることがわかったが、すでに設置されている場合が全く不明で手を出せず・・・ 結果は、Rank: 3342 Score: 65 で突破したようです。uruのフレンド登録よろしこ!

Google Code Jam Qualification Round 2017 B

B Tidy Numbersは数字(の10進数表現)が1123456など非減少列になってるものをtidyと定義し、与えられたN以下で最大のtidy数を求めるもの。まずはtidyかどうかを判定するメソッドtidy?を作る。次に、与えられたNがtidyならそれを出力して終了なのでtidyでないとする。すると、Nを1ずつ減らしていきtidy数を見つけることになるが、その場合は1桁目は必ず9になることが分かる。そこで1桁目を忘れて1桁少ない数字が最初に与えられたとして同じようにtidy数を構築して、最終的にそれに9をくっつければOK。またDecrease-and-Conquerだ(笑) 今回は桁数が高々18桁なので再帰関数で書いてみた。一応、ブルートフォース版で小さい数でチェックもし、万全を期す。

def tidy?(n)
    n.to_s.bytes.each_cons(2).all?{|a,b|a<=b}
end

def bf_max_tidy(m)
    m.downto(1){|n|return n if tidy?(n)}
end

def rec_max_tidy(m)
    return m if m<10
    return m if tidy?(m)
    return rec_max_tidy((m-1-(m%10))/10)*10+9
end

gets.to_i.times{
  n=gets.to_i
  write(rec_max_tidy(n))
}

Google Code Jam Qualification Round 2017 A

待ちに待ったGoogle Code Jam。今年もやっていきますよー。 A. Oversized Pancake Flipperは上下逆さまになったパンケーキがN枚与えられるので全部表を向くよう並び替えるもの。ただし、K個の連続したパンケーキを一遍に並び替えるフリッパーを使わなきゃいけない。左右の順番を変えず、1枚1枚のパンケーキをひっくり返すなんてどういうメカニズムだ?!

左L番目からL+K-1番目までパンケーキをひっくり返す操作をFlip(L)と表すと、問題のキーポイントは、1)Flip操作は可換、つまりどういう順番でやっても結果は同じ、2)一番端(例えば左)が裏で与えられたら必ず一番左をひっくり返す必要がある点、すなわち、Flip(1)をする必要がある。それをした後は、一番左のことは忘れて残りのN-1枚が与えられたと考えて、同じことをしていけば最後にK-1枚のパンケーキが残り、それが全部表を向いているかどうかで可能か不可能かの判別ができる(Decrease-and-Conquer)。これをコードに落とせば次の通り。Largeも余裕でパスします。

なんか、よくある問題の気がします。

gets.to_i.times{
    s,k=gets.split
    s=s.chars.map{|c|c==?+}
    k=k.to_i
    ans=0
    0.upto(s.size-k){|i|
        unless s[i]
            k.times{|j|s[i+j]=!s[i+j]}
            ans+=1
        end
    }
  write(s.all? ? ans : "IMPOSSIBLE")
}

数学パズル本に敢てプログラムで挑戦(5)

プログラムといえばシミュレーション。今回のボールの問題はそれにピッタリ。ボールの増減の推移を追えば自ずと理屈が分かってくる

50. Last Ball

(a)20個の黒のボールと16個の白のボールが袋に入っている。その中からランダムに2個取り出し同色だったら白を1個入れ、異なる色だったら黒を1個入れる。この操作を残り1個になるまで繰り返す時、最後に残るボールは何か?

(b)20個の黒と15個の白で始めたらどうなるか?

結局白ボールが2ずつ減っていくということがわかれば(a)は白が1個になれないから最後に残るのは黒、(b)は白は0個になれないから自ずと最後に残るのは白とわかる。個人的にこういうパリティの問題好きです。数学の有名な証明が難しい定理も、mod 2の場合の証明は優しかったりしますからね

#50. LastBall
#(a) You have 20 black balls and 16 white balls in a bag.
#You repeat the following operation until a single ball is left in the bag.
#You remove two balls at a time. If they are of the same color,
#you add a black ball to the bag; if they are of different colors, you add a white ball to the bag.
#Can you predict the color of the last ball left in the bag?
#(b) Answer the same question if there are 20 black balls and 15 white balls to start with.

class Bag
    def initialize(bnum,wnum)
        @bnum=bnum
        @wnum=wnum
    end

    def remove
        r1=remove_one
        r2=remove_one
        add(r1==r2 ? :B : :W)
        [r1,r2]
    end

    def size
        @bnum+@wnum
    end

    def to_s
        "B:%d, W:%d"%[@bnum,@wnum]
    end

private
    def add(ball)
        if ball==:B
            @bnum+=1
        else
            @wnum+=1
        end
    end

    def remove_one
        if rand(size)<@bnum
            @bnum-=1
            return :B
        else
            @wnum-=1
            return :W
        end
    end
end

b=Bag.new(20,16)
puts b
until b.size==1
    b.remove
    puts b
end

数学パズル本に敢てプログラムで挑戦(4)

これも有名な問題で、Youtubeなどに解説動画がたくさんある。

www.youtube.com

7. Bridge Crossing at Night

4人の人が懐中電灯で橋を夜間渡るのだが、4人それぞれは渡るのに1分、2分、5分、10分かかり、橋は同時に2人までしか渡れない。二人同時に渡る時はかかる時間は遅い方の時間。渡る時に懐中電灯は必須。この時全員が渡る時間を最小化せよ

ついに来た。幅優先探索ではうまくいかないパターンが。これも、懐中電灯の位置が左と右どちらか、4名がそれぞれ橋の左右どちらにいるかの5bitで状態を表すことが出来る。それを頂点としてグラフを作り、ダイクストラの最短経路アルゴリズムを適用する。結果は17分で正解だった。ダイクストラの最短路アルゴリズムはこのblogでコードを紹介していたはず。このグラフのエッジは橋の移動を表すけど、その重みがかかる時間になり、それを最小化する、すなわち最短経路を求めることに繋がる。実装したプログラムはグラフを大域的に最初に生成して、それを既存のダイクストラアルゴリズムに渡している。グラフ問題でいつも迷うのはこのように最初にグラフを大域的に生成しちゃうか、頂点に辿り着くたびにそこから出る辺を生成するか。頂点の数が少なければ問題ないが、頂点数が沢山ありかつほとんど訪れないなら無駄になるから。ちなみに、このプログラムでかかる時間を変えると、グラフの辺の重みが変わるのでまた違ったルートが最短路になるし、peopleの数を4人から増やすとまた違う大きいグラフになるので面白い。でも多分、この[1,2,5,10]が盲点なルートなのだと思う。これはプログラムでは分からない点。

#ダイクストラアルゴリズムは略

def to_code(people_pos, light_pos)
  code = 0
  people_pos.each{|b|code = 2 * code + b}
  2 * code + light_pos
end

def pos_from(code, size)
  light_pos = code & 1
  people_pos = []
  size.times{
    code /= 2
    people_pos << (code & 1)
  }
  [people_pos.reverse, light_pos]
end

def generate_edge_cost(people)
  #flashlightの位置(左...0,右...1)とpeopleそれぞれの位置のビットで管理
  size = people.size
  node_num = 2 ** (size + 1)
  edges = Array.new(node_num){Array.new}
  costs = Array.new(node_num){Hash.new(INF)}
  node_num.times{|code|
    people_pos, light_pos = pos_from(code, size)
    candidate = []
    people_pos.each_with_index{|b, idx|candidate << idx if b == light_pos}

    #how many can cross the bridge at the same time
    1.upto(2){|n|
      candidate.combination(n).each{|indices|
        pos = people_pos.dup
        indices.each{|idx|pos[idx] = 1 - light_pos}
        next_code = to_code(pos, 1 - light_pos)
        edges[code] << next_code
        costs[code][next_code] = indices.map{|idx|people[idx]}.max      
      }
    }
  }
  [edges, costs]
end

people = [1, 2, 5, 10]
edges,costs = generate_edge_cost(people)
d, prec = dijkstra(edges, costs)
goal = to_code([1] * people.size, 1)
puts d[goal]

数学パズル本に敢てプログラムで挑戦(3)

どんどん挑戦していく。明日GCJ本番なのに目が冴えてしまってあかん。本日もAlgorithmic Puzzlesより。

49. Missionaries and Cannibals(宣教師と人食い部族)

3人の宣教師と3人の人食い族が船で川を渡る時(同時に2人まで)、両岸それぞれで人食い族の人数が宣教師よりも真に多くならないようにして渡る方法を求めよ

何処かで見たことのある問題も、結局はグラフの問題に帰着。船がどちらの岸にあるかと宣教師、人食い部族がそれぞれ左岸に何人いるかの情報を頂点とするグラフを幅優先探索すれば良い。具体的には[boat,Missionary,Cannibal]という配列で[0,3,3] -> [1,0,0]のステップ数を求める。結果は11ステップ。実際グラフを書くと相当単純(ほぼ一本道)のグラフになる。やはり数的優位が崩れると食べられてしまうという条件が厳しい。というのも、宣教師、人食い族それぞれ左右の岸にいる状態を考えると、どちらか一方は数的優位が成り立たなくなってしまうから。ちなみに4名以上でやってみたら渡る方法は無かった。

#49. Missionaries and Cannibals
#Three missionaries and three cannibals must cross a river.
#Their boat can only hold two people, and it cannot cross the river by itself
#with no people on board. Each missionary and each cannibal can row the boat.
#If present, missionaries cannot be outnumbered by cannibals.
#How can all six get across the river with the fewest crossings?

N=3
class State
    attr_reader :row_num
    def initialize(boat=0,people=[N,N],row_num=0)
        @boat=boat
        @people=people
        @row_num=row_num
    end

    def legitimate?
        rm,rc=@people
        lm,lc=N-rm,N-rc
        return false if rm>0&&rc>rm
        return false if lm>0&&lc>lm
        true
    end

    def accomplished?
        @boat==1&&@people==[0,0]
    end

    def next_move
        ret=[]
        m,c=@people
        if @boat==0
            ret<<State.new(1,[m-1,  c],@row_num+1) if m>0
            ret<<State.new(1,[m-2,  c],@row_num+1) if m>1
            ret<<State.new(1,[  m,c-1],@row_num+1) if c>0
            ret<<State.new(1,[  m,c-2],@row_num+1) if c>1
            ret<<State.new(1,[m-1,c-1],@row_num+1) if m>0&&c>0
        else
            ret<<State.new(0,[m+1,  c],@row_num+1) if m<N
            ret<<State.new(0,[m+2,  c],@row_num+1) if m<N-1
            ret<<State.new(0,[  m,c+1],@row_num+1) if c<N
            ret<<State.new(0,[  m,c+2],@row_num+1) if c<N-1
            ret<<State.new(0,[m+1,c+1],@row_num+1) if m<N&&c<N
        end
        ret
    end

    def to_code
        @boat.to_s+@people.join
    end
end


init_state=State.new
queue=Array.new
queue.push init_state
visited=Hash.new

until queue.empty?
    state=queue.shift
    next if visited[state.to_code]
    visited[state.to_code]=state.row_num
    if state.accomplished?
        puts state.row_num
        exit
    end

    state.next_move.each{|next_state|
        next unless next_state.legitimate?
        next if visited[next_state.to_code]
        queue.push next_state
    }
end

puts"impossible"

数学パズル本に敢てプログラムで挑戦(2)

いったん書くとこれがなかなか面白いのがblogの中毒的な所、というわけで今日も昨日の続きでAlgorithmic Puzzlesを解いていこう。

45. A Knight’s Shortest Path(ナイトの最短路)

100*100のチェスボード上の左下コーナーにナイトが居る時、右上のコーナーへは最短何手で行けるか?

最短路とあるけれど、ダイクストラアルゴリズムは必要ない。というのも、全ての一手の価値は同じだから幅優先探索でOK。つまり、最初の位置から一手で進める場所を調べて、そこから更に一手で進める場所を・・・というのを、ゴールに辿り着くまで||進める場所がなくなるまで、行う。もちろん同じ場所を何度も行こうとするから、visitedというハッシュにそのマスまでの最短手数を入れてフラグとする。 直感的にはナイトのジャンプはイビツだからうまくたどり着けない可能性やゴール直前で調整する手数が必要かなと思う。

#!ruby

#45. A Knight’s Shortest Path
#What is the minimum number of moves needed for a chess knight
#to go from one corner of a 100 × 100 board to the diagonally opposite corner?

N = 100

def is_pos_regitimate?(x, y)
    ((0...N) === x) && ((0...N) === y)
end

Moves = [
                    [ 1, 2],
                    [-1, 2],
                    [ 1,-2],
                    [-1,-2],
                    [ 2, 1],
                    [-2, 1],
                    [ 2,-1],
                    [-2,-1]
                ]
Init_Pos = [    0,     0]
Goal_Pos = [N - 1, N - 1]

queue = Array.new
queue.push [Init_Pos, 0]
visited = Array.new(N){Array.new(N)}

until visited.dig(*Goal_Pos) || queue.empty?
    pos, move_num = queue.shift
    next if visited.dig(*pos)
    x, y = pos
    visited[x][y] = move_num
    Moves.each{|dx, dy|
        next_pos = [x + dx, y + dy]
        if is_pos_regitimate?(*next_pos)
            queue.push [next_pos, move_num + 1] unless visited.dig(*next_pos)
        end
    }
end

puts visited.dig(*Goal_Pos) || "Impossible!"

ここでは新しく覚えたdigメソッドを使ってみた。多重構造の時にコード数を減らせるし、今回のように*展開で配列も渡せて美味しい。結果は66というなんとなく納得できる数字に。というのもナイトの動きって1行って2行くわけだから、2回動けば対角線に(3,3)に行ける。従って、(100,100)に行くには66回動けばいいでしょうという寸法。他のNでも同じ結果に。N=2のときだけ解がないようだ。

   N | answer
-----------
  10 | 6
 100 | 66
1000 | 666