RubyでAtCoder ABC302(A, B, C, D)を解いてみた

はじめに

Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC302のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。

A - Attack

a-302.rb

a, b = gets.split.map(&:to_i)
puts a % b == 0 ? a / b : a / b + 1

B - Find snuke

b-302.rb

h, w = gets.split.map(&:to_i)
array = Array.new(h){ gets.chomp }
directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
str = "nuke"
h.times do |i|
  w.times do |j|
    next if array[i][j] != "s"
    directions.each do |di, dj|
      ni = i + di * 4
      nj = j + dj * 4
      next unless ni >= 0 && ni < h && nj >= 0 && nj < w
      flag = true
      4.times do |k|
        if array[i + di * (k + 1)][j + dj * (k + 1)] != str[k]
          flag = false
          break
        end
      end
      if flag
        5.times do |l|
          puts "#{i + 1 + di * l} #{j + 1 + dj * l}"
        end
        exit
      end
    end
  end
end

解説

（他の方の提出結果を参考にしました）

最初に移動先の設定するための配列directionsを用意しておきます。そして、要素がsであれば、上下左右斜めの8通りで条件を満たす場合があるかを順に調べていくことで実装することができます。

C - Almost Equal

c-302.rb

# 修正前
n, m = gets.split.map(&:to_i)
array = Array.new(n){ gets.chomp }

array.permutation(n) do |na|
	flag = true
	(n - 1).times do |i|
		count = 0
		m.times do |j|
			count += 1 if na[i][j] != na[i + 1][j]
		end
		if count != 1
			flag = false
			break
		end
	end
	if flag
		puts "Yes"
		exit
	end
end
puts "No"

c-302.rb

# 修正後
n, m = gets.split.map(&:to_i)
array = Array.new(n){ gets.chomp.chars }

result = array.permutation(n).any? do |rearranged_array|
	rearranged_array.each_cons(2).all?{ |(pre_str, nxt_str)|
      pre_str.zip(nxt_str).count{ |c, nc| c != nc } == 1
    }
end
puts result ? "Yes" : "No"

解説

Nが８以下と小さいため、並べ替えについて全探索することができます。そして、並べ替え後の文字列について条件を満たすものがあればYesを出力して終了、最後までなければNoを出力します。

D - Impartial Gift

d-302.rb

n, m, d = gets.split.map(&:to_i)
a = gets.split.map(&:to_i).sort
b = gets.split.map(&:to_i)

ans = -1
b.each do |bb|
	i = a.bsearch_index{ |aa| aa > bb + d} || n
	i -= 1
	ans = [ans, a[i] + bb].max if i >= 0 && (a[i] - bb).abs <= d
end
puts ans

解説

（他の方の提出結果を参考にしました）

bsearch_indexメソッドを使って二分探索により差がd以下となる場所を求め、最大値を更新していくことで実装することができます。