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

本履歴

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

マジ数学本に敢てプログラムで挑戦(1):包除原理(Inclusion-Exclusion Principle)

SpringerのGTMと言えば黄色のカバーで有名ですが、238 A Course in Enumerationに包除原理を使った面白い問題が

Ex. 5.7.

How many integer solutions \( x_1+x_2+x_3+x_4=30 \) exist with the restriction -10 \le x_{i} \le 20 ?

上限が無ければよくある問題でcombinationで計算できます。

O(n4)

数字が小さいので四重ループで解けます、がO(n4)なのでNが大きいとお手上げです。

N=30
L=-10
R=20

def f_bf
    ret=0
    L.upto(R){|x|
        L.upto(R){|y|
            L.upto(R){|z|
                L.upto(R){|w|
                    ret+=1 if x+y+z+w==N
        }}}}
    ret
end

O(n2)

次に考えるのは4変数一括ではなく2変数ずつで考える。具体的には\( x_1+x_2 \) の取りうる組み合わせ計算しておき、 x_1+x_2=a となる個数と x_3+x_4=30-a を満たす個数をかけ合わせて行く方法。これはO(n2)で計算できる。

def f_dc
    memo=Array.new((R-L)*2+N,0)
    L.upto(R){|x|
        (x+1).upto(R){|y|
            memo[x+y]+=2
    }}
    L.upto(R){|x|memo[2*x]+=1}
    ret=0
    (2*L).upto(2*R){|i|
        ret+=memo[i]*memo[N-i]
    }
    ret
end

O(1)

最後の方法が包除原理を使ったもので、これが一番早い。まず初めに、次の事実に注意:

\( x_1+x_2+x_3+x_4=30 \)を満たす正整数の組み合わせ個数は  _{29} C_3 である

これは、ボールを30個横に並べて3つの衝立で分割すること(◯◯|◯・・◯◯|◯・・◯|◯◯◯)に方程式の解が一対一に対応し、衝立を入れる場合の数は29箇所から3つ選ぶことになるから。次に\( y_i=x_i+10 \) と変形することで同値な問題

How many integer solutions \( (\ast) \ y_1+y_2+y_3+y_4=70 \) exist with the restriction (\star) \ 0 \le y_{i} \le 30 ?

にできます。すると求めるのは包除原理より、

(\ast) を満たす正整数の組み合わせ数-(\ast) を満たすけど1変数だけ(\star)を満たさない+(\ast) を満たすけど2変数だけ(\star)満たさない・・・

となりますね。j個の変数だけ(\star)を満たさないということはj個の変数の値は31以上。つまりj個の変数を\( z_i=y_i-31 \) とすることで元と同じ問題、ただし総和が70-31*jを解くことに帰着されます。4変数のうちj個を選ぶのは _4 C_j ですから結局次のようなアルゴリズムになります。

def f_inc_exc
    n=4
    k=N-L*n
    s=R-L+1
    #new problem: find the # of sol x+y+z+w=70 with the restriction 0<= each<=30?
    ret=0
    0.upto(n){|j|
        sgn=j.odd? ? -1 : 1
        temp=sgn*combination(n,j)*combination(n+k-j*s-1,n-1)
        ret+=temp
    }
    ret
end

小さいNでは差が分かりませんが大きいと違いは明らか。ブルートフォース版は10分待っても帰ってきませんでした。

N=10000
L=-5000
R=7000

       user     system      total        real
inclusion & exclusion : 828252025001
  0.000000   0.000000   0.000000 (  0.000093)
divide & conquer      : 828252025001
  7.710000   0.020000   7.730000 (  7.735661)
bruteforce            : ^Cex05_07.rb:12:in `block (4 levels) in f_bf': Interrupt

A Course in Enumeration (Graduate Texts in Mathematics)

A Course in Enumeration (Graduate Texts in Mathematics)

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

チェス盤のタイリング問題に挑戦。この問題はALGORITHMIC PUZZLESではチュートリアルの例題として載っていた。 まあ有名ですからね。

Domino Tiling of Deficient Chessboards

8x8のチェス盤をドミノ(1*2)で隙間なく埋めることを考える。a)左上が欠けているチェス盤で可能か? b)左上、右下が欠けている場合は?

a)は偶奇性が異なる(空きは偶数である必要がある)からNGは明らか。b)はちょっとトリッキーだが、チェス盤が市松模様なのとドミノをどう置いても2色をカバーする必要があることからチェス盤の2色は同じセル数ある必要があるからNG。 念のため、深さ優先でプログラムを組んでドミノを置いてみたが、理屈通りできませんでした(笑) まあ、ロジックで出来ないを判定できるのはすごいことだ。

#domino tiling on N*N board

N = 8
board = Array.new(N + 1){Array.new(N + 1, false)}
(N + 1).times{|j|board[N][j] = true} #sentinel
(N + 1).times{|i|board[i][N] = true}
board[0][0] = true #deficient cell
board[N - 1][N - 1] = true

def find_next(b, x, y, n)
    x.upto(N){|i|return [i, y] unless b[i][y]}
    (y + 1).upto(n - 1){|j|N.times{|i|return [i, j] unless b[i][j]}}
    nil
end

def f(b)
    def dfs(b, x, y, rest, n)
        ret = 0

        #horizontal
        if b[x][y + 1] == false
            return 1 if rest == 2
            b[x][y] = b[x][y + 1] = true
            nx, ny = find_next(b, x, y, n)
            if nx
                ret += dfs(b, nx, ny,rest - 2, n)
            end
            b[x][y] = b[x][y + 1] = false
        end

        #vertical
        if b[x + 1][y] == false
            return 1 if rest == 2
            b[x][y] = b[x + 1][y] = true
            nx, ny = find_next(b, x, y, n)
            if nx
                ret += dfs(b, nx, ny, rest - 2, n)
            end
            b[x][y] = b[x + 1][y] = false
        end
        ret
    end

    #body
    n = b.size - 1
    rest = 0
    n.times{|i|n.times{|j|rest += 1 unless b[i][j]}}
    x,y = find_next(b, 0, 0, n)
    dfs(b, x, y, rest, n)
end

p f(board) # => 0

Cracking the Code Interview 16.19 Pond Sizes

もう1題は深さ優先探索の練習問題。長方形の区画の高さ情報(0は水面)が与えられるので全ての池を求めるというもの。池は上下左右斜めで繋がっているという定義。深さ優先探索再帰で書くと簡単だけど、たまにスタックがいっぱいになったりするので注意が必要。いつも思うのは、チェック先セルが範囲内かをチェックするのにRangeを使っているけど遅い気がするんだよなあ。不等号の方が速いはず。Ruby配列には範囲外を指定するとnilが返る仕様なんだけど、多次元だとnil[4]とかでmethod missingエラーになって処理が美しくないんだよね。Nilクラスにメソッド追加してnil返すようにすればいいんだけど。まあ、周りを壁で囲えば気にしなくていいんだけど、配列操作がRubyは非常に面倒くさいのでやりたくないしindex -1で最後にアクセスできるので、与えられる配列の最後に2つ番兵入れるだけだけどね。不等号と言えば、Enumerable#minも2値の場合は遅いと思う。ループの最深では不等号にしないとTLE。せっかく短く書けるからRuby使っているのに、冗長な書き方しないといけないのは本末転倒なんだけど。時間制限がある場合はしようがない。

def pond_sizes(pond)
    def dfs(x,y,pond)
        ret = 1
        pond[x][y]=-1
        [[1,0],[0,1],[-1,0],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]].each{|dx,dy|
            nx,ny = x+dx, y+dy
            next unless (0...pond.size)===nx
            next unless (0...pond.first.size)===ny
            ret += dfs(nx,ny,pond) if pond[nx][ny]==0
        }
        ret
    end

    h=pond.size
    w=pond.first.size
    ret=[]
    h.times{|i|w.times{|j|ret << dfs(i,j,pond) if pond[i][j]==0}}
    ret
end

if __FILE__==$0
    #text example
    pond=[[0,2,1,0],[0,1,0,1],[1,1,0,1],[0,1,0,1]]
    p pond_sizes(pond) #=> [2,4,1]
    
    pond =[[0]]
    p pond_sizes(pond) #=> [1]

    pond =[[1,0]*50,[0,1]*50]
    p pond_sizes(pond) #=> [100]
end

Cracking the Code Interview 17.21 Volume Of Histogram

「世界で闘うプログラミング力を鍛える本」の最新版の翻訳が出たとのことで暇つぶしに眺めていたら面白い問題を見つけた。ヒストグラム地形が与えられるので雨が降った時に貯まる水の量を求めるというもの。例えば、3,1,5 という入力だと、3と5の間に高さ2の水たまりが出来るから2を出力すると言った具合。2,0,1,0,3だと5、基本0以上の数値が与えられる。 山頂を境として右と左に水たまりが出来ることは明らかだ。漢字の「山」という字の右左のくぼみに水が貯まるイメージ。つまり、左から山頂までの水たまりの体積が分かったら、今度は右から同じことをすればOK。従って、まず山頂を求め、そこで左右に分割し、右は反転し、vol_of_slopeメソッドにあとは計算を任せる。vol_of_slopeは一番最後に最高峰の壁が出てくることになっているので、配列を読みながら逐次現在までの最高点の更新と、最高点以下の地形が出てきたらその差分が水で埋まるので加えていく。

def volume_of_histgram(a)
    max_hight = max_idx = 0
    a.each_with_index{|h, idx|
        if h > max_hight
            max_hight = h
            max_idx = idx
        end
    }
    vol_of_slope(a[0..max_idx]) + vol_of_slope(a[max_idx..-1].reverse)
end

#the rightmost must be the highest
def vol_of_slope(a)
    ret = 0
    prev_highest = 0
    a.each{|h|
        if h > prev_highest
            prev_highest = h
        elsif h < prev_highest
            ret += prev_highest - h
        end
    }
    ret
end

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")
}