本履歴

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

競技プログラミング

最近codechefサボってたんだけど、GCJ(Google Code Jam 2013)が開催中なので、腕試しに出てみたら五問解けた。あれあれ?簡単になってる??
Rubyで解くよう頑張った。

Matchsticks(http://www.codechef.com/MAY13/problems/MSTICK)

今月の中ではMatchsticksが一番面白かった。10^5個要素の配列Aがあって、A[x..y]の最大値(最小値)は?という問い(10^5個)に答えられればOK。
RMQ(wikipedia:en:Range_Minimum_Query)というのを使えたのだが、なんと自分自身これが初めての実装。蟻本を参考にコーディング。再帰的に処理するんだけど、これがうまく動くことが分かって、しばし感動した。
46.03secの解答。危なすぎるなあ。

MIN=0
MAX=1<<30

_n=gets.to_i
n=1
n*=2 until n>=_n
lb=n-1
#construct segment tree
$min_seg_tree=Array.new(4*n,MAX)
$max_seg_tree=Array.new(4*n,MIN)

gets.split.map(&:to_i).each_with_index{|b,i|
  $min_seg_tree[i+lb]=b
	$max_seg_tree[i+lb]=b
}

(lb-1).step(0,-1){|k|
	$min_seg_tree[k]=
    $min_seg_tree[k*2+1]<$min_seg_tree[k*2+2] ? $min_seg_tree[k*2+1] : $min_seg_tree[k*2+2]
	$max_seg_tree[k]=
    $max_seg_tree[k*2+1]<$max_seg_tree[k*2+2] ? $max_seg_tree[k*2+2] : $max_seg_tree[k*2+1]
}

#p $min_seg_tree
def find_min(a,b,k,l,r)
  return MAX if r<=a||b<=l
  if a<=l&&r<=b
    return $min_seg_tree[k]
  else
    vl=find_min(a,b,k*2+1,l,(l+r)/2)
    vr=find_min(a,b,k*2+2,(l+r)/2,r)
    return vl<vr ? vl : vr
  end
end

def find_max(a,b,k,l,r)
  return MIN if r<=a||b<=l
  if a<=l&&r<=b
    return $max_seg_tree[k]
  else
    vl=find_max(a,b,k*2+1,l,(l+r)/2)
    vr=find_max(a,b,k*2+2,(l+r)/2,r)
    return vl<vr ? vr : vl
  end
end

q=gets.to_i
q.times{
  l,r=gets.split.map(&:to_i)
  to_rear_min_time=find_min(l,r+1,0,0,n)
  to_rear_max_time=find_max(l,r+1,0,0,n)

  from_rear_max_time=0
  if 0<l
    from_rear_max_time=[from_rear_max_time,find_max(0,l,0,0,n)].max
  end
  if r<n-1
    from_rear_max_time=[from_rear_max_time,find_max(r+1,n+1,0,0,n)].max
  end

  burn_down_time=to_rear_min_time+[(to_rear_max_time-to_rear_min_time)/2.0,from_rear_max_time].max
  puts "%.1f"%burn_down_time
}

Witua and Math(http://www.codechef.com/MAY13/problems/WITMATH)

nが与えられた時、2..nの中でphi(i)/iを最大にするiを出力する問題。
オイラーのファイ関数へのwikipediaがあるので、結局n以下の最大の素数を見つけることと同値であることが分かる。nが10^18とでかいので、正確に求めると時間がかかりすぎるはずで、確率的に求めればよさげ。ということでwikipedia:ミラー-ラビン素数判定法を使って通った。4^-50の確率で間違ってしまうけど、宝くじに当たるより難しいはず、うむ。nが素数である確率は1/ln(n)なので10^18だと50個に1個くらいの確率で素数になるはずだから、余裕で間に合うのかな。計算量とかは全く考えなかったけど、出題者が合成数が長く続く区間を選択してきたらどうなるんだろう、とは思った。2..10^18までで合成数が続く区間で最長のものや如何?

def modpow(base, power, mod)
  result = 1
  while power > 0
    result = (result * base) % mod if power & 1 == 1
    base = (base * base) % mod
    power >>= 1
  end
  result
end

def prime?(n)
  return true if n==2
  return false if n%2==0
  return true if n==3
  return false if n%3==0
  return true if n==5
  return false if n%5==0
  return true if n==7
  return false if n%7==0

  n1 = d = n-1
  d >>= 1 while d & 1 == 0
  50.times{
    a = rand(n-2) + 1
    t = d
    y = modpow(a,t,n)
    while t != n1 && y != 1 && y != n1
      y = (y * y) % n
      t <<= 1
    end
    return false if y != n1 && t & 1 == 0
  }
  return true
end

gets.to_i.times{
  n=gets.to_i
  n.step(2,-1){|m|
    if prime?(m)
      puts m
      break
    end
  }
}