RubyでAtCoder 版！蟻本 (初級編)を解いていく

# 前置き

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

引用元: [AtCoder 版！蟻本 (初級編)](https://qiita.com/drken/items/e77685614f3c6bf86f44)


# 問題と解答

#### 例題 1-1-1　くじびき

+ [JOI 2007 本選 C ダーツ](https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_c)

```rb

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
```

##### 【参考リンク】

+ [Ruby Arrayの組み合わせ系メソッドまとめ](https://qiita.com/shshimamo/items/5a458ecc88e7c24d5112)
+ [アルゴリズム for Ruby サーチ バイナリサーチ](http://tomikura.s2.xrea.com/ruby/algorithm/search.html#binary)
+ [instance method Array#bsearch
](https://docs.ruby-lang.org/ja/latest/method/Array/i/bsearch.html)


#### 例題 1-6-1　三角形



+ [ARC 004 A 2点間距離の最大値](https://atcoder.jp/contests/arc004/tasks/arc004_1)

```rb
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
```

+ [ABC 051 B Sum of Three Integers](https://atcoder.jp/contests/abc051/tasks/abc051_b)

```rb
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
```

##### 【別解（微妙かも）】

```rb
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}
```

+ [ABC 085 C Otoshidama](https://atcoder.jp/contests/abc085/tasks/abc085_c)


```rb
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)](http://poj.org/problem?id=1852)**

+ [AGC 013 C Ants on a Circle](https://atcoder.jp/contests/agc013/tasks/agc013_c)

[Atcoder Grand Contest 013 解説 C Ants on a Circle](https://img.atcoder.jp/agc013/editorial.pdf) より

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

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

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

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

+ [ABC 154 D Dice in Line](https://atcoder.jp/contests/abc154/tasks/abc154_d)

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

##### 【累積和解法】

```rb
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
```

##### 【しゃくとり法解法】

```rb
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
```

##### 【参考リンク】

+ [【累積和、しゃくとり法】初級者でも解るアルゴリズム図解 - paiza開発日誌](https://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF%E7%A9%8D%E5%92%8C%E3%80%81%E3%81%97%E3%82%83%E3%81%8F%E3%81%A8%E3%82%8A%E6%B3%95%E3%80%91%E5%88%9D%E7%B4%9A%E8%80%85%E3%81%A7%E3%82%82%E8%A7%A3%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4)
+ [和の期待値は期待値の和 - 高校数学の美しい物語](https://mathtrain.jp/expectation)
+ [サイコロ（１個、n個）の期待値、分散、標準偏差 - 具体例で学ぶ数学](https://mathwords.net/saikorokitaichi)

-----

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

+ [ABC 045 C - たくさんの数式](https://atcoder.jp/contests/arc061/tasks/arc061_a)　

##### 【bit全探索解法】

```rb
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
```

##### 【再帰関数解法】

```rb
# 再帰関数
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)
```


**【参考リンク】**

+ [Rubyでbit全探索](https://qiita.com/hiroyuki-nagata/items/5b0ff1a6776e0ee36f61)
+ [instance method Array#repeated_permutation
](https://docs.ruby-lang.org/ja/latest/method/Array/i/repeated_permutation.html)
+ [ARC 061 提出 #9727748](https://atcoder.jp/contests/arc061/submissions/9727748)


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

+ [ATC 001 A 深さ優先探索](https://atcoder.jp/contests/atc001/tasks/dfs_a)

##### 【再帰関数解法】

```rb
# デバッグ用: 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
```

##### 【スタック解法】

```rb
# デバッグ用: 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](https://atcoder.jp/contests/atc001/submissions/10024151)
+ [Rubyで全探索（深さ優先探索、幅優先探索）を実装してみた
](https://qiita.com/ha4gu/items/ecd540355d453862a729)
+ [DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】](https://qiita.com/drken/items/4a7869c5e304883f539b)
+ [DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】](https://qiita.com/drken/items/a803d4fc4a727e02f7ba)
+ [深さ優先探索と幅優先探索 | 高校数学の美しい物語](https://mathtrain.jp/dfsbfs)

#### 例題 2-1-3　幅優先探索

```rb
# デバッグ用: 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](https://atcoder.jp/contests/abc007/submissions/10238551)
+ [ABC 007 C 提出 #10387210](https://atcoder.jp/contests/abc007/submissions/10387210)
+ [Rubyで全探索（深さ優先探索、幅優先探索）を実装してみた
](https://qiita.com/ha4gu/items/ecd540355d453862a729)
+ [BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜](https://qiita.com/drken/items/996d80bcae64649a6580)
+ [深さ優先探索と幅優先探索 | 高校数学の美しい物語](https://mathtrain.jp/dfsbfs)


-----
...
略
...
-----

#### 例題 2-4-3　食物連鎖 (POJ No.1182)

+ [ATC 001 B Union Find](https://atcoder.jp/contests/atc001/tasks/unionfind_a)　(とりあえず Union-Find 木を verify する問題です)
+ [ABC 177 D Friends](https://atcoder.jp/contests/abc177/tasks/abc177_d)（最近の問題 2020/8/29）

```rb
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
}
```

+ [ATC 001 B 提出 #572252](https://atcoder.jp/contests/atc001/submissions/572252)