A – Biscuit Generator
問題
解法
A秒ごとにB枚のビスケットが生産されるの、T+0.5秒後なら(T/A)xB枚
実装
a,b,t=gets.chomp.split.map(&:to_i) puts (t/a)*b
B – Resale
問題
解法
手に入れた宝石の価値の合計から支払ったコストの合計を引いた値が最大になるような宝石の選び方を考えれば良い。
宝石はいくつ選んでも良いので、各宝石の「価値−コスト」が正になるものは全て選んで良いことになる。
よって、「価値−コスト」が正になるものを加算していけばよい。
実装
N=gets.to_i v=gets.chomp.split.map(&:to_i) c=gets.chomp.split.map(&:to_i) ans=0 N.times do |i| ans += v[i]-c[i] if v[i]-c[i] > 0 end puts ans
C – GCD on Blackboard
問題
解法
N個の整数のうち1つだけ好きな整数に書き換えた後の最大公約数をなるべく大きくするためには、1つの整数を他の整数のうち一つと同じにすればよい。これは、その整数を取り除くのと同じ意味になる。
つまり、N個のうち1つを取り除いた残りのN-1個の最大公約数の最大値を求めれば良い。
2つの数の最大公約数はlogAで求まるので、N-1個の最大公約数はO(NlogA)となり、これをN通り試すと間に合わない。
そこで以下のような工夫をする。
Aiを取り除いた場合の最大公約数は、A1〜Ai-1の最大公約数とAi+1〜ANの最大公約数になる。
よって、あらかじめA1〜A2、A1〜A3・・・のように左から順番に整数を追加した最大公約数とAN-1〜AN、AN-2〜AN・・・のように右から順番に整数を追加した最大公約数を求めておくことで、i番目を取り除いた場合の最大公約数をlogAで求めることが出来る。
こうすれば、全体の計算量はO(NlogA)で収まるので間に合う。
実装
def gcd(a,b) return a if b == 0 gcd(b,a%b) end N=gets.to_i a=gets.chomp.split.map(&:to_i) l=[0] r=[0] a.each_with_index do |v| l << gcd(v,l[-1]) end a.reverse.each_with_index do |v| r << gcd(v,r[-1]) end ans=0 0.upto(N) do |i| tmp = gcd(l[i],r[N-1-i]) ans = tmp if ans < tmp end puts ans
D – Handstand
問題
解法
整数列のうち、隣り合う任意の2枚の正負を反転させることが何回でも出来る。
操作後の整数列の総和の最大はいくつになるか、という問題。
これは、以下のルールに気づけばすぐに解ける。
AiとAj（i<j）の正負を反転させたい場合、「iとi+1」、「i+1とi+2」、「i+2とi+3」・・・・「j-1とj」のように隣り合う2つを順次反転させていけば良い。
→ 任意の2個の正負を反転させることが可能
→ 偶数個であれば好きなように正負を反転させることが可能（奇数は不可）
よって、整数列の初期状態において、負が偶数個であれば全て正にすることが出来る。つまり絶対値の総和をとれば良い。
負が奇数個の場合、（初期状態が正のものも含めて）絶対値が最も小さいものを最終的に負としてそれ以外を正にすれば良い。
実装
N=gets.to_i
A=gets.chomp.split.map(&:to_i)
m_cnt=0
sum=0
min=Float::INFINITY
A.each do |a|
if a < 0
m_cnt += 1
end
if min > a.abs
min = a.abs
end
sum+=a.abs
end
if m_cnt.even?
puts sum
else
puts sum - 2 * min
end
コメント