AtCoder: ACB125

A – Biscuit Generator

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

A秒ごとにB枚のビスケットが生産されるの、T+0.5秒後なら(T/A)xB枚

実装

a,b,t=gets.chomp.split.map(&:to_i)
puts (t/a)*b

B – Resale

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

手に入れた宝石の価値の合計から支払ったコストの合計を引いた値が最大になるような宝石の選び方を考えれば良い。

宝石はいくつ選んでも良いので、各宝石の「価値−コスト」が正になるものは全て選んで良いことになる。

よって、「価値−コスト」が正になるものを加算していけばよい。

実装

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

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

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

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

整数列のうち、隣り合う任意の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

シェアする

  • このエントリーをはてなブックマークに追加

フォローする