前置き
業務での実装力を高めようと、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'
