Help us understand the problem. What is going on with this article?

RubyでAtCoder 版!蟻本 (初級編)を解いてみた

前置き

業務での実装力を高めようと、AtCoderをやっています。
AB問題の過去問を200問以上解いたのですが、なかなか灰コーダーから抜け出せないため、また、C++やPythonで取り組む人に比べるとRubyでAtCoderに取り組んでいる人は少ないかなと思い、初見で解けなかった問題も解説や他の解答見て作ることで残していきます。

引用元: AtCoder 版!蟻本 (初級編)


例題 1-1-1 くじびき

n,m=gets.split.map &:to_i
p=n.times.map{gets.to_i}+[0]
# 半分全列挙
a=p.repeated_combination(2).to_a.map{|i|i.inject(:+)}.sort.reverse
s=0
# 全探索
a.each do |left|
  # 二分探索
  right=a.bsearch{|r|r+left<=m}
  s=[s,left+right].max unless right.nil?
end
puts s

【参考リンク】

例題 1-6-1 三角形

N=gets.to_i
xy=N.times.map{gets.split.map &:to_i}
ans=0
# 全探索 (二重の for 文)
N.times do |i|
  N.times do |j|
    next if i==j
    x1=xy[i][0]
    y1=xy[i][1]
    x2=xy[j][0]
    y2=xy[j][1]
    # 三角形の成立条件
    res=((x1-x2)**2+(y1-y2)**2)**0.5
    ans = [ans, res].max
  end
end
puts ans
k,s=gets.split.map &:to_i
l=k+1
a=0
l.times do |x|
  l.times do |y|   
    z=s-x-y
    a+=1 if z>=0 && z<=k
  end
end
puts a

【別解(微妙かも)】

k,s=gets.split.map &:to_i
puts [*0..k].repeated_permutation(2).map{|a,b|a+b}.select{|i|i<=s}.count{|xy|(z=s-xy)>=0 && z<=k}
N,Y=gets.split.map &:to_i
n=N+1
f=false
n.times do |x|
  n.times do |y|
    break if x+y>N
    z=(Y-10000*x-5000*y)/1000
    if x+y+z===N && z>=0
      puts "#{x} #{y} #{z}"
      f=true
      break
    end
  end
  break if f
end
puts "-1 -1 -1" unless f

例題 1-6-2 Ants (POJ No.1852)

Atcoder Grand Contest 013 解説 C Ants on a Circle より

ここは分かった。

T 秒後にゼッケンのある座標の集合は、当然、T 秒後に蟻のいる座標の集合と同じなので、T 秒後にそれぞれの蟻がどこにいるかを求めると、番号は分からないが、どの座標にゼッケンがあるのかが分かります。

それ以外は解説読んでもコードに起こせない。

二つの蟻がゼッケンを交換する時、時計回りに歩いてる蟻のゼッケンの番号は 1 増え、反時計回りに歩いている蟻のゼッケンの番号は 1 減ります。ある二つの蟻が T 秒間にすれ違う回数は、O(1)で求めることができます。よって、最初に 1 のゼッケンをつけていた蟻が、T 秒間に他の蟻とすれ違う回数の合計は、O(N) で分かります

例題おまけ 累積和・しゃくとり法

つい先日のABC。頻出らしいのでついでに載せておく。

【累積和解法】

N,K=gets.split.map &:to_i
# 期待値の前計算
p=gets.split.map{|i|(i.to_f+1)*0.5}
# 累積和の計算
a=[0]
N.times do |i|
  a[i+1]=a[i]+p[i]
end
# 隣接するK項の和の計算
s=0
(N-K+1).times do |i|
  r=a[i+K]-a[i]
  s=[s,r].max
end
puts s

【しゃくとり法解法】

N,K=gets.split.map &:to_i
# 期待値の前計算
p=gets.split.map{|i|(i.to_f+1)*0.5}
# しゃくとり法・隣接するK項の和の計算
r=s=p[0..K-1].inject(:+)
(N-K).times do |i|
  r+=p[i+K]-p[i]
  s=[s,r].max
end
puts s

【参考リンク】


例題 2-1-1 部分和問題

【bit全探索解法】

s=gets.chomp.chars
n=s.size
a=0
# bit全探索
['', '+'].repeated_permutation(n-1) do |i|
  t=s.zip(i).join
  if t.include?('+')
    # "+"をto_iすると0になる
    a+=t.split('+').map(&:to_i).inject(:+)
  else
    a+=t.to_i
  end
end
puts a

【再帰関数解法】

# 再帰関数
def calc(s,num)
  if num==0
    arr=s.split('+')
    sum=0
    arr.each do |a|
      sum+=a.to_i
    end
    return sum
  end
  return calc(s.clone.insert(num,'+'),num-1) + calc(s,num-1)
end

s=gets.chomp
num=s.size()

puts calc(s,num-1)

【参考リンク】

例題 2-1-2 深さ優先探索

H,W=gets.split.map &:to_i
FIELD=H.times.map{gets.chomp.chars}
DX=[1,0,-1,0]
DY=[0,1,0,-1]
sh=0
sw=0
gh=0
gw=0

H.times do |h|
  W.times do |w|
    sh,sw=[h,w] if FIELD[h][w]=='s'
    gh,gw=[h,w] if FIELD[h][w]=='g'
  end
end

seen=Array.new(H){Array.new(W, false)}
seen[sh][sw] = true
queue=[[sh,sw]]

while !queue.empty?
  h,w=queue.shift
  4.times do |dir|
    nh=h+DX[dir]
    nw=w+DY[dir]
    next if nh<0 || nh>=H || nw< 0 || nw>=W
    next if seen[nh][nw]
    next if FIELD[nh][nw]=='#'
    seen[nh][nw]=true
    queue.push([nh,nw])
  end
end

puts seen[gh][gw] ? 'Yes' : 'No'

yokoto
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした