人材募集企画 2011年版に応募した

人生を書き換える者すらいた。: 人材募集企画 2011年版
これに応募した，今日の24時以降にブログに答えとか書くの解禁なので一応書く.かなり適当なんで間違ってたらすみません．

第一問
f(unsigned int x)はx<=2^nとなる最小の2^nを返す．ただしunsigned intのサイズがが32bitなら，x>2^31のとき0が返る．

アロケータとかでメモリ再確保のサイズ決めるのに使ったりするのかな？適当に値入れて確かめてもだいたい推定できるし，32bitの範囲程度ならテストパターン全部書いて総当たりしても確かめれる．
3行目から7行目の処理で，3行目で一番左側で1になってるビットがどう広がるかに注目すれば理解できると思う．

第二問
以下rubyのソースコード．落下をcompact!で，探索の外枠を配列の-1番目の要素が最後の要素を指す事を使ってる．単純な再帰．

$H = 14   #最上段数
$W = 6

#外枠代わりのnilを追加
def add_nil(puyo)
  puyo.each{|a| a[$H] = nil}
  puyo[$W] = []
  return puyo
end

#空のゲームを生成
def form
  puyo = []
  $W.times{|i| puyo << []}
  return add_nil(puyo)
end

#ゲーム表示
def print_puyo(puyo)
  $H.times do |h|
    h = $H - h - 1
    $W.times{|w| print puyo[w][h]? puyo[w][h] : '*'}
    puts ''
  end
end

#4つ以上の同色を消して自由落下させる
#一組でも消えるぷよがあるならtrue，全然消えないときはfalseを返す
def step(puyo)
  def search(puyo, sc, w, h, c = puyo[w][h])
    return 0 if puyo[w][h].nil?
    return 0 if sc.key?([w, h])
    return 0 if c != puyo[w][h]
    sc[[w, h]] = true
    res = 1
    res += search(puyo, sc, w-1, h, c)
    res += search(puyo, sc, w+1, h, c)
    res += search(puyo, sc, w, h-1, c)
    res += search(puyo, sc, w, h+1, c)
    return res
  end
  
  def clear(puyo, sc)
    sc.each_key{|k| puyo[k[0]][k[1]] = nil}
  end
  
  def fall(puyo)
    puyo.each{|r| r.compact!}
    return add_nil(puyo)
  end
  
  res = false
  $H.times do |h| $W.times do |w|
    if puyo[w][h]
      sc = {}
      count = search(puyo, sc, w, h)
      if count >= 4
        clear(puyo, sc)
        res = true
      end
    end
  end end
  fall(puyo) if res
  return res
end

def read_puyo(str)
  puyo = form
  inv = str.split("\n").reverse.map{|e| e.split(//)}
  h = 0
  inv.each do |e|
    $W.times{|w| puyo[w][h] = inv[h][w] == ' ' ? nil : inv[h][w]}
    h += 1
  end
  return puyo
end


str = <<EOS
GGR
YGG
EOS

puyo = read_puyo(str)
chain = 0

begin
  puts "#{chain}chain"
  print_puyo(puyo)
  puts ''
  chain += 1
end while step(puyo)

第三問
これ書く意味ないと思うけどいちおう．
自分が選択したのは(a)．投機は投資と同じ市場に影響を与える点で賭博と明確な違いがある．
賭博が現在違法なのはトラブル防止のためで，自分は理にかなってると思う．