本履歴

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

競技プログラミング

昨日参加できなかったAtcoder#014の問題をRubyで解いたので。全部解けたのは初めてかも。

A. 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう

偶奇性を問われてる。ワンライナーで。

puts gets.to_i%2<1 ? "Blue" : "Red"

B. あの日したしりとりの結果を僕達はまだ知らない。

しりとりを判定。単語のおしりと次の単語のあたまが等しいか、と既出でないかをハッシュでチェック。

turn=0
words={}
pre_word=""
gets.to_i.times{
  word=gets.chomp
  if words[word] || ((pre_word!="") && pre_word[-1]!=word[0])
    puts turn<1 ? "LOSE" : "WIN"
    exit
  end
  words[word]=true
  pre_word=word
  turn=1-turn
}
puts "DRAW"

C. 魂の還る場所

また偶奇性を問われた。最初の2個の起き方は重要でないのと、どんな4つのRGBパターンが来ても連鎖で消して2個にできるから、それ以降も連鎖で消せるとダメ元で出したら通った。

gets(p)
puts [?R,?G,?B].map{|c|$_.count(c)%2}.inject(:+)

D. grepマスター

x=y=0の時を考えてみて、次に空いている間隔を考えて、それらがx+yのサイズで埋まるかどうかを考えていたら、間隔の集合をソートして二分探索すればよさげに気づいた。x+yより大きい間隔はx+yすべて使えるから。
次に、x+yで間隔全体をカバーできてしまう場合に、間隔の小さい順から足していくことが必要だったので、DPでメモっておいた。

#find the smallest idx s.t. key<=ary[i] for all idx<=i
def bsearch(ary,key,l,r)
  return nil if ary[r]<key
  return nil if l>r
  ret=r
  m=(l+r)/2
  if key<=ary[m]
    temp=bsearch(ary,key,l,m-1)
    ret=temp ? temp : m
  else
    temp=bsearch(ary,key,m+1,r)
    ret=temp if temp
  end
  ret
end

all,n,m=gets.split.map(&:to_i)
l=n.times.map{gets.to_i}
ary=l.each_cons(2).map{|l1,l2|l2-l1-1}.sort
dp=[ary.first]
1.upto(ary.size-1){|i|dp << dp.last+ary[i]}

m.times{
  x,y=gets.split.map(&:to_i)
  pre=[x,l.first-1].min
  post=[y,all-l.last].min
  middle=n
  unless ary.empty?
    idx=bsearch(ary,x+y,0,ary.size-1)
    if idx
      middle+=(x+y)*(ary.size-idx)
      middle+=dp[idx-1] if idx>0
    else
      middle+=l.last-l.first+1-n
    end
  end
  puts pre+middle+post
}