前置き
業務での実装力を高めようと、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 深さ優先探索
【再帰関数解法】
# デバッグ用: gridの現在の状態を出力
# def print_grid(grid)
# grid.each { |row| puts row }
# puts
# end
def depth_first_search(grid, current_x, current_y, height, width)
# 迷路の範囲外、壁、訪問済みの場合は探索終了
return false if current_x < 0 || current_y < 0 || current_x >= width || current_y >= height || grid[current_y][current_x] == "#" || grid[current_y][current_x] == "x"
# ゴールに到達した場合
return true if grid[current_y][current_x] == "g"
# 訪問済みにマーク
grid[current_y][current_x] = "x"
# デバッグ用: gridの現在の状態を出力
# puts "Current grid state:"
# print_grid(grid)
# 上下左右のマスを探索
return depth_first_search(grid, current_x, current_y - 1, height, width) ||
depth_first_search(grid, current_x, current_y + 1, height, width) ||
depth_first_search(grid, current_x - 1, current_y, height, width) ||
depth_first_search(grid, current_x + 1, current_y, height, width)
end
# 入力
height, width = gets.split.map(&:to_i)
# 迷路の状態を表す二次元配列を作成
grid = []
start_x = start_y = 0
height.times do |i|
row = gets.chomp
if row.include?("s")
start_y = i
start_x = row.index("s")
end
grid << row
end
# 深さ優先探索
if depth_first_search(grid, start_x, start_y, height, width)
puts "Yes"
else
puts "No"
end
【スタック解法】
# デバッグ用: gridの現在の状態を出力
# def print_grid(grid)
# grid.each { |row| puts row }
# puts
# end
def depth_first_search_stack(grid, start_x, start_y, height, width)
stack = [[start_x, start_y]]
while !stack.empty?
x, y = stack.pop
# 迷路の範囲外、壁、訪問済みの場合はスキップ
next if x < 0 || y < 0 || x >= width || y >= height || grid[y][x] == "#" || grid[y][x] == "x"
# ゴールに到達した場合
return true if grid[y][x] == "g"
# 訪問済みにマーク
grid[y][x] = "x"
# 上下左右のマスをスタックに追加
stack.push([x, y - 1], [x, y + 1], [x - 1, y], [x + 1, y])
# デバッグ用: gridの現在の状態を出力
# puts "Current grid state:"
# print_grid(grid)
# デバッグ用: スタックの現在の状態を出力
# puts "Current stack state: #{stack.inspect}"
# puts
end
false
end
# 入力
height, width = gets.split.map(&:to_i)
grid = []
start_x = start_y = 0
height.times do |i|
row = gets.chomp
if row.include?("s")
start_y = i
start_x = row.index("s")
end
grid << row
end
# 深さ優先探索
if depth_first_search_stack(grid, start_x, start_y, height, width)
puts "Yes"
else
puts "No"
end
- ATC 001 A 提出 #10024151
- Rubyで全探索（深さ優先探索、幅優先探索）を実装してみた
- DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】
- DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】
- 深さ優先探索と幅優先探索 | 高校数学の美しい物語
例題 2-1-3 幅優先探索
# デバッグ用: gridの現在の状態を出力
# def print_grid(grid)
# grid.each { |row| puts row }
# puts
# end
def bfs(grid, start_x, start_y, goal_x, goal_y, height, width)
visited = Array.new(height) { Array.new(width, false) }
visited[start_y][start_x] = true
queue = [[start_x, start_y, 0]]
while !queue.empty?
x, y, depth = queue.shift
if x == goal_x && y == goal_y
return depth
end
[[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dx, dy|
next_x = x + dx
next_y = y + dy
if next_x >= 0 && next_y >= 0 && next_x < width && next_y < height && !visited[next_y][next_x] && grid[next_y][next_x] != "#"
visited[next_y][next_x] = true
queue.push([next_x, next_y, depth + 1])
# デバッグ用: gridの現在の状態を出力
# puts "Visiting (#{next_x}, #{next_y}), depth: #{depth + 1}"
# print_grid(grid)
# puts "Queue state: #{queue.inspect}"
# puts
end
end
end
-1
end
# 入力
height, width = gets.split.map(&:to_i)
start_y, start_x = gets.split.map(&:to_i).map { |x| x - 1 }
goal_y, goal_x = gets.split.map(&:to_i).map { |x| x - 1 }
grid = height.times.map { gets.chomp }
# 幅優先探索
steps = bfs(grid, start_x, start_y, goal_x, goal_y, height, width)
puts steps
- 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
}