はじめに
ABC337に参加しました。
今回はA~Eの5問完答できたのでE問題までメモを残します。
A - Scoreboard
スコアの合計から勝敗を求める問題。
入力を合計して大小を比べるだけなので素直に実装する。
自分の回答
n = gets.to_i
t = 0
a = 0
n.times do
tt, aa = gets.split.map(&:to_i)
t += tt
a += aa
end
if t > a
puts "Takahashi"
elsif t == a
puts "Draw"
else
puts "Aoki"
end
B - Extended ABC
Aからなる文字列+Bからなる文字列+Cからなる文字列、であることを判定する問題。
A→B→Cの順番でそれぞれ0文字以上並んでいればよいので、正規表現を利用するのが簡単。
自分の回答
s = gets.chomp
puts s.match?(/^A*B*C*$/) ? "Yes" : "No"
C - Lining Up 2
N人が並んでる列の並び順を求める問題。
先頭の人以外は前にいる人の番号がわかっているので、人iが並んでるときに前にいるのがiの人となる人を求められるようにすると人iの後ろに並んでる人が求められる。
先頭の人は-1となっているので、先頭から後ろに並んでいる人を順番に求めていけばよい。
自分の回答
n = gets.to_i
arr = gets.split.map(&:to_i)
# key: 人iの一つ前に並んでいる人の番号, value: 人i
hash = {}
ind = 0
arr.each_with_index do |a, i|
hash[a] = i + 1
# 先頭の人の番号を保存しておく
ind = i + 1 if a == -1
end
# 先頭から順に一つ後ろ並んでいる人を求める
ans = [ind]
while hash[ind]
ans << hash[ind]
ind = hash[ind]
end
puts ans.join(" ")
D - Cheating Gomoku Narabe
H行W列のグリッド上に縦または横方向に連続するK個のマスにo, .のみになるものがあるか、あるなら.の数が一番少ない個所を求める問題。
.はすべてoに置換できるので、.のマスはoと同じものとみなす。
この時、連続するK個のマスがすべてoであることは、o, .のみからなることと、さらに言えばxが含まれないことと同値である。
そのうえで、.をoに置換する操作数を最小となるのは上記を満たすK個のうち.の数が最小となるものとなる。
よって、それぞれのグリッド上のマスから縦、横方向それぞれK個のマスを確認して、xを含むかどうか、.の個数を確認すれば答えになる。
ただし、そのまま実装すると計算量がO(HWK)となり時間内に収まらないのでどこかを効率化する必要がある。
マス(i, j)とマス(i+1, j)からそれぞれ横方向にK個連続するマスに含まれるo, x, .の個数はマス(i, j)とマス(i+K, j)の文字を入れ替えたものと一致する。
そのため、各マスに対して毎回Kマスの文字を確認する必要はないため計算量をO(HW)に抑えることができる。
連続するKマスがoまたは.であり、.の個数が最小となる値を求めればよいので、oまたは.の連続している個数とそのうち.の個数を持って置き、連続するマスが超えたらKを現在のマスの文字を文字をKマス前の文字と入れ替え、xが出てきたらリセットしてあげることで答えを求められる。
自分の回答
h, w, k = gets.split.map(&:to_i)
arr = []
h.times do
arr << gets.chomp + "x"
end
arr << "x" * (w + 1)
# すべてoにできる場所がある場合の`.`の個数の最小値
min = k
# すべてoにできる場所があるかどうかのフラグ
flag = false
# 横方向
h.times do |i|
len = 0
dots = 0
f = false
w.times do |j|
c = arr[i][j]
if c.nil?
# グリッドの範囲外に出たので終了
break
elsif c == "x"
# xが出たのでリセット
len = 0
dots = 0
next
elsif c == "."
len += 1
dots += 1
else
len += 1
end
# 長さがK以上になったらK個前の文字と入れ替え
if len > k
len -= 1
dots -= 1 if arr[i][j - len] == "."
end
# 長さがKになる場所があったら.の数の最小値を求める
if len >= k
flag = true
min = [min, dots].min
end
end
end
# 縦方向
w.times do |j|
len = 0
dots = 0
f = false
h.times do |i|
c = arr[i][j]
if c.nil?
break
elsif c == "x"
len = 0
dots = 0
next
elsif c == "."
len += 1
dots += 1
else
len += 1
end
if len > k
len -= 1
dots -= 1 if arr[i - len][j] == "."
end
if len >= k
flag = true
min = [min, dots].min
end
end
end
puts flag ? min : -1
E - Bad Juice
腐ったワインをできるだけ少ない人数で見分ける問題。
この問題では例として以下のように3つのワインを与えている。
| ワイン | 1 | 2 | 3 |
|---|---|---|---|
| 友人1 | o | o | |
| 友人2 | o |
この時、友人1だけがお腹を壊しているためワイン1が腐っていることがわかる。
もし仮に、友人1, 2両方ともお腹を壊した場合はワイン2が、どちらもお腹を壊さなければワイン3が腐っていたことがわかるので、3つのワインに対して必ず腐っているものがわかるようになっている。
ワインの数を5つに友人の数を3人に増やして、仮に以下のようにワインを与えるとする。
| ワイン | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 友人1 | o | o | |||
| 友人2 | o | o | o | ||
| 友人3 | o | o |
この場合は、お腹を壊した友人と腐ったワインの対応は以下のようになる。
| お腹を壊した友人 | 腐ったワイン |
|---|---|
| 友人1のみ | ワイン1 |
| 友人2のみ | ワイン2 |
| 友人3のみ | ワイン3 |
| 友人1と友人2 | ワイン4 |
| 友人2と友人3 | ワイン5 |
ただ単にお腹を壊した友人にだけ与えたワインと対応しているだけだが、同じ友人の組み合わせで与えたワインがなければお腹を壊した友人の組み合わせとワインが1対1対応する。
そのため、重複がないようにワインを与える組み合わせのパターンがあればよい。
友人がM人いるとしたときの1つのワインの与え方のパターン数は、与える/与えないの2パターンをM人に対して持っているため2^Mパターンとなる。
よって、ワインの種類数N以上となる求めたい友人の人数となる。
次に各友人へのワインの与え方についてだが、ワイン1~Nを2進数表記にして各桁のビットを友人にワインを与えるかどうかのフラグにすると重複なく与え方を用意できる。(実際には0=誰にも与えないを含めたほうが良いのでワインの番号-1を2進数表記にするとよい。)
こうするとお腹を壊した人の文字列をもらったときに、2進数として数値に直すとそのままワインの番号と対応できるので楽ができる。
自分の回答
n = gets.to_i
m = (n - 1).to_s(2).length
# 友人iに飲ませるワインの番号のリスト
arr = Array.new(m) { [] }
n.times do |i|
# 友人1を一番左の桁にするため0埋めしてm桁の2進数文字列にする
("%0.#{m}b" % i).each_char.with_index do |c, j|
arr[j] << i + 1 if c == "1"
end
end
puts m
arr.each do |a|
puts "#{a.length} #{a.join(" ")}"
end
STDOUT.flush
puts gets.to_i(2) + 1