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

本履歴

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

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のフレンド登録よろしこ!