ABC015

rubyのお勉強をしてました。

• -

A : 高橋くんの研修

• 終了後に書きなおした版。本番はCライクなコードだった。

print [gets, gets].max_by(&:size)

B : 高橋くんの集計

• 本番で出したコードそのまま。
• 0を除くのにselectを使ってみたけど、配列の引き算でもいけるらしくてこわい。

N = gets
a = gets.chomp.split.map(&:to_i).select { |i| i > 0 }
puts (a.reduce(:+)+a.size-1)/a.size

C : 高橋くんのバグ探し

• 本番で書いたものをtimesとか3項演算子とか使って整理した。

N, K = gets.chomp.split.map(&:to_i)
dp = Array.new(N+1){Array.new(128){0}}
dp[0][0] = 1
N.times { |i|
	gets.chomp.split.map(&:to_i).each { |val|
		128.times { |j| dp[i+1][j^val] |= dp[i][j] }
	}
}
puts dp[N][0] == 0 ? "Nothing" : "Found"

D : 高橋くんの苦悩

• 本番ではTLE不可避だったのでカッとなってC++を使って通した。82ms。
• sune2さんが優先度をキーにすると良いと仰ってたので従ったらrubyでも通った。761ms。
• aとbの最小値を取るのは [a,b].min より a

W = gets.chomp.to_i
N, K = gets.chomp.split.map(&:to_i)
dp = Array.new(K+1){Array.new(5001){W+1}}
dp[0][0] = 0
res = 0
sum = 0
N.times { |k|
	A, B = gets.chomp.split.map(&:to_i)
	[K-1, k].min.downto(0) { |i|
		sum.downto(0) { |j|
			dp[i+1][j+B] = dp[i+1][j+B] < dp[i][j] + A ? dp[i+1][j+B] : dp[i][j]+A
		}
	}
	sum += B
}
5001.times { |j| (K+1).times { |i| res = j if dp[i][j] <= W } }
puts res

• -

記事が短く済んで良いですね(白目)