前置き
業務での実装力を高めようと、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}
$seen=Array.new(H){Array.new(W, false)}
DX=[1,0,-1,0]
DY=[0,1,0,-1]
# 再帰DFS
def dfs(h,w)
$seen[h][w]=true
4.times do |dir|
nh=h+DX[dir]
nw=w+DY[dir]
next if nh<0 || nh>=H || nw< 0 || nw>=W
next if $FIELD[nh][nw]=='#'
next if $seen[nh][nw]
dfs(nh,nw)
end
end
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
dfs(sh,sw)
puts $seen[gh][gw] ? 'Yes' : 'No'
- ATC 001 A 提出 #10024151
- Rubyで全探索（深さ優先探索、幅優先探索）を実装してみた
- DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】
- DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】
- 深さ優先探索と幅優先探索 | 高校数学の美しい物語
例題 2-1-3 幅優先探索
R,C=gets.split.map &:to_i
sy,sx=gets.split.map{ |i| i.to_i - 1 }
gy,gx=gets.split.map{ |i| i.to_i - 1 }
FIELD=R.times.map { gets.chomp.chars }
DY=[-1, 0, 1, 0]
DX=[0, 1, 0, -1]
seen = Array.new(R){Array.new(C,-1)}
seen[sy][sx]=0
queue=[[sy,sx]]
while !queue.empty?
y,x=queue.shift
# ゴール地点の座標ならば抜ける
if y == gy && x == gx
puts seen[y][x]
exit
end
4.times do |i|
ny=y+DY[i]
nx=x+DX[i]
next if ny < 0 || nx < 0 || ny >= R || nx >= C
next if FIELD[ny][nx] == '#'
next if seen[ny][nx] != -1
seen[ny][nx] = seen[y][x] + 1
queue << [ny,nx]
end
end
- ABC 007 C 提出 #10238551
- ABC 007 C 提出 #10387210
- Rubyで全探索（深さ優先探索、幅優先探索）を実装してみた
- BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜
- 深さ優先探索と幅優先探索 | 高校数学の美しい物語
...
略
...
例題 2-4-3 食物連鎖 (POJ No.1182)
- ATC 001 B Union Find (とりあえず Union-Find 木を verify する問題です)
- ABC 177 D Friends（最近の問題 2020/8/29）
class UnionFind
def initialize(n)
@par = [*0...n]
@rnk = [0]*n
end
def find(x)
return x if @par[x] == x
@par[x] = find(@par[x])
end
def same(x,y)
find(x) == find(y)
end
def unite(x,y)
x=find(x);y=find(y)
return if x==y
if @rnk[x] < @rnk[y]
@par[x] = y
elsif
@par[y] = x
@rnk[x]+=1 if @rnk[x]==@rnk[y]
end
end
end
n,q = gets.chomp.split.map(&:to_i)
u = UnionFind.new(n)
1.upto(q){
p,a,b = gets.chomp.split.map(&:to_i)
if p==0
u.unite(a,b)
else
puts u.same(a,b) ? "Yes" : "No"
end
}
Comments