「 2019年06月 」一覧

Google Code Jam 2019 Qualification Round

Foregone Solution

問題

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

解法

与えられた整数Nを2つの整数(A+B)に分割する。この時、AとBのどの桁にも4が含まれ無いように分割するという問題。

Nの各桁を順次見ていき、4の場合は2と2、それ以外は0と元の数、のようにAとBに割り振る。

なお、答えを出力する際に、先頭の0は削除する必要がある点に注意する。

実装

N=gets.to_i
N.times do |i|
  n=gets.chomp.split("")
  a=[]
  b=[]
  n.each do |v|
    if v == '4'
      a << '2'
      b << '2'
    else
      a << '0'
      b << v
    end
  end
  printf("Case #%d: %s %s\n", i+1, a.join.gsub(/^0*/, ""), b.join)
end

You Can Go Your Own Way

問題

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

解法

NxNのマス目を北西から南東に移動する。移動は南(S)、東(E)の組み合わせのみで後戻りは無し。

テストケースで与えられた移動方法に対して、経路が重ならないような移動方法を1通り出力するという問題。

これは、与えられた移動方法(SとEの並び)に対して対象な移動方法(SならE、EならS)を作れば良いです。

例えば、SEEESSESならESSSEESE。

このようにすると、移動経路はマス目の北西から南東への対角線に対して対象な移動経路になるので、絶対に重なりません。

実装

T=gets.to_i
T.times do |i|
  n=gets
  s = []
  gets.chomp.split("").each do |v|
    s << (v == 'E' ? 'S' : 'E')
  end
  printf("Case #%d: %s\n", i+1, s.join)
end

Cryptopangrams

問題

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

解法

テストケースとして与えられる整数列は、元の文字列が対応する素数の積になっています。

例えばテストケースの整数列をEi、元の文字列の対応する素数をPiとすると、E0はP0xP1、E1はP1xP2です。

よって、E0とE1の最大公約数をとればP1が求まり、それでE0とE1を割ることでP0とP2も求めることが出来ます。

ここで注意点ですが、E0とE1が等しい場合、つまり、P0〜P2が同じ素数(=文字)の場合はこの方法では求めることが出来ません。(これに気づかずに最初WAをくらいました。。。)

よって、整数列を前から見ていき、隣り合う整数が最初に異なる場所に上記の方法を適用し、そこから前方、後方を見ていくことで全ての素数を求めることが出来ます。

素数が全て求まったらソートして小さい方からアルファベットを割り当てていき、元の文字列に戻すことが出来ます。

実装

def gcd(a,b)
  return a if b == 0
  gcd(b,a%b)
end

T=gets.to_i
T.times do |i|
  n,l=gets.chomp.split.map(&:to_i)

  enc = gets.chomp.split.map(&:to_i)
  pn=Hash.new(0)
  dec = Array.new(l+1)
  pos = 0
  0.upto(l-2) do |j|
    if enc[j] != enc[j+1]
      dec[j+1] = gcd(enc[j],enc[j+1])
      pn[dec[j+1]] += 1
      pos=j+1
      break
    end
  end

  (pos-1).downto(0) do |j|
    dec[j] = enc[j] / dec[j+1]
    pn[dec[j]] += 1
  end

  (pos+1).upto(l) do |j|
    dec[j] = enc[j-1] / dec[j-1]
    pn[dec[j]] += 1
  end

  m = {}
  pn.keys.sort.each_with_index do |v, i|
    m[v] = ('A'.ord+i).chr
  end
  ans=[]
  dec.each do |v|
    ans << m[v]
  end

  printf("Case #%d: %s\n",i+1,ans.join)
end

Dat Bae

問題

Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.

解法

N台のコンピュータのうちB台が壊れている。N個のビット列を与えたとき、壊れたコンピュータのビットは返ってこない。F回までビット列を投げることが出来る場合に、何台目のコンピュータが壊れているかを特定する方法を考えるという問題。

TestSet1のF=10の場合は結構簡単。というのも、Nの最大値が1024(=2^10)なので、0〜1023までの数字を各コンピュータに割り当てて、1回目の問い合わせは1ビット目、2回目の問い合わせは2ビット目、・・・というように10ビット目まで投げてやる。その結果、返ってきた回答を繋げて10進数に戻してやった場合に、欠けている数字が壊れているコンピュータの位置になります。

TestSet2のF=5の場合は少し工夫が必要です。2^5=32なので、5回の問い合わせで作れるビット列は0〜31になります。例えば、N=1024の場合、0台目から順にサイクリックに0〜31を割り当てます。すると、0〜31、0〜31、・・・、0〜31が32回繰り返されることになります。問題の制約として、壊れているコンピュータは最大15台までなので、抜けている数字の位置によってどのコンピュータが壊れているか一意に特定することが出来ます。

より厳密にはBが最大31までであれば大丈夫だと思います。32以上になると、例えば連続する0〜31が抜けていた場合に何番目の0〜31が抜けているのかが特定できない、ということになります。

実装

T=gets.to_i

def solve
  n,b,f=gets.chomp.split.map(&:to_i)

  r = Array.new(n-b).map { Array.new }
  f.times do |i|
    q = []

    j = 0
    n.times do
      t = j >> i
      q << (t & 1)
      j += 1
      j = 0 if j == 16
    end
    puts q.join
    STDOUT.flush

    gets.chomp.split("").each_with_index do |v, i|
      r[i] << v
    end
  end

  i = 0
  j = 0
  ans = []
  r.each do |v|
    if i == v.reverse.join.to_i(2)
    else
      while(i != v.reverse.join.to_i(2))
        ans << j
        j += 1
        i += 1
        i = 0 if i == 16
      end
    end
    i += 1
    i = 0 if i == 16
    j += 1
  end

  while(j != n)
    ans << j
    j += 1
  end
  puts ans.join(" ")
  STDOUT.flush
  gets.to_i
end

T.times do
  solve
end

AtCoder: ABC122

A – Double Helix

問題

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

解法

入力に対応する塩基を出力するだけ。

実装

とりあえずcaseで実装。

case gets.chomp
when 'A'
  puts 'T'
when 'T'
  puts 'A'
when 'G'
  puts 'C'
when 'C'
  puts 'G'
end

B – ATCoder

問題

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

解法

文字を一文字ずつ読み込み、ATGCのいずれかであれば部分文字列の長さを1増やし、それ以外であれば部分文字列の長さを0にもどす。各部分文字列の最大値を記憶・更新しておいて、最後に出力すれば良い。

実装

S=gets.chomp.split("")
ans = 0
tmp = 0
S.each do |c|
  if "ATGC".include?(c)
    tmp += 1
  else
    ans = [tmp,ans].max
    tmp = 0
  end
end
ans = [tmp,ans].max

C – GeT AC

問題

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

解法

累積和の変形問題という感じ。

最初に1文字目からn文字目までの’AC’の出現回数の数列を用意しておく(Cnとする)
そして、各l、rについては、C[r]-C[l]を計算すれば定数時間で計算可能。

実装

N,Q=gets.chomp.split.map(&:to_i)
S=gets.chomp
csum = [0,0]
0.upto(N-2) do |i|
  if S[i,2] == 'AC'
    csum[i+2] = csum[i+1] + 1
  else
    csum[i+2] = csum[i+1]
  end
end

Q.times do
  l,r=gets.chomp.split.map(&:to_i)
  puts csum[r]-csum[l]
end

D – We Like AGC

問題

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

解法

DPで解ける。

DP[直前の3文字][n]: 文字列の長さがnでの直前の3文字毎の文字列の数

とすると、nが3の場合が初期値となり、以下の通りとなる。

DP[‘AGC’][3] = 0
DP[‘GAC’][3] = 0 (1文字目と2文字目を入れ替えるとAGCになるので)
DP[‘ACG’][3] = 0 (2文字目と3文字目を入れ替えるとAGCになるので)
DP[上記以外][3] = 1

4文字目以降については、直前の4文字に着目して条件に一致する場合だけ数え上げて行けば良い。

実装

N=gets.to_i
ACGT=['A','C','G','T']
MOD=10**9+7
dp = {}
ACGT.each do |c1|
  ACGT.each do |c2|
    ACGT.each do |c3|
      c = c1+c2+c3
      dp = [0]*102
      if c == 'AGC' || c == 'ACG' || c == 'GAC'
      else
        dp[3] = 1
      end
    end
  end
end
4.upto(N) do |i|
  ACGT.each do |c1|
    ACGT.each do |c2|
      ACGT.each do |c3|
        ACGT.each do |c4|
          c = c1+c2+c3+c4
          if c.match(/AGC/) || c.match(/GAC/) || c.match(/ACG/) || c.match(/A.GC/) || c.match(/AG.C/)
          else
            dp[c2+c3+c4][i] += dp[c1+c2+c3][i-1]
            dp[c2+c3+c4][i] %= MOD
          end
        end
      end
    end
  end
end
ans = 0
dp.each_key do |k|
  ans += dp[k][N]
end
puts ans%MOD

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

AtCoder: ABC124

A – Buttons

問題

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

解法

2個のボタンのサイズが等しい時は、A+Bが解。
等しくないときは、大きい方 x 2 – 1 が解。

実装

入力を読み取る際にソートして、B >= A にしておく。

A,B=gets.chomp.split.map(&:to_i).sort
puts A==B ? 2*B : 2*B-1

B – Great Ocean View

問題

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

解法

海が見えるのは、「自分より西側の山の高さが全て自分以下の時」なので、その時点の最大の高さを保持しながら西の山から順に見ていき、

・これまでの最大の高さ以上の時:解を1増やす&最大の高さを更新する
・これまでの最大の高さ未満の時:何もしない

というループをまわせば良い。

実装

N=gets.to_i
H=gets.chomp.split.map(&:to_i)
min=0
ans=0
H.each do |h|
  if h >= min
    ans += 1
    min = h
  end
end
puts ans

C – Coloring Colorfully

問題

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

解法

黒白2色しなかいので、隣り合うタイルが異なる色となるタイルの並べ方は以下の2通りしかない。

黒白黒白黒白黒白・・・・
白黒白黒白黒白黒・・・・

よって、両方のケースについて何枚塗り替える必要があるかをそれぞれカウントし、小さい方が解となる。

実装

S=gets.chomp.split("")
ans1,ans2=0,0
S.each_with_index do |s,i|
  if i.even? && s=='0' || i.odd? && s=='1'
    ans1+=1
  end
  if i.odd? && s=='0' || i.even? && s=='1'
    ans2+=1
  end
end
puts [ans1,ans2].min

D – Handstand

問題

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

解法

ある一定の区間の0、1を反転させることを繰り返し、連続する1をどれだけ長く出来るか、という問題です。

基本的に1を反転させる意味は無いので、出来るだけ長い1の連続を作るには、1回の操作で連続する0の区間を反転させていけば良いことが分かります。

ここで、連続する0の区間がK個以下であれば、全てを1に出来るので解はNになります。

問題となるのは、連続する0の区間の数がKより多い場合です。

仮に連続する0の区間がL個だとすると、K個からL個選ぶことになるので、全探索だと間に合いそうに無いです。

そこで、次のように考えます。

なるべく1の連続を長くするには、反転させる連続する0の区間は連続していた方が良いです。

例えば、以下のような並びについてK=3で考えた場合、連続する0の区間は5カ所ですが、選び方は3通りしかありません。

よって、しゃくとり法などを使って前から順に見ていけば、O(N)で解くことが出来ます。

実装

N,K=gets.chomp.split.map(&:to_i)
S=gets.chomp.split("")
prev=S[0]
ss = []
ss << 0 if prev=='0'

cnt = 1
1.upto(N-1) do |i|
  if prev == S[i]
    cnt += 1
  else
    ss << cnt
    prev = S[i]
    cnt = 1
  end
end
ss << cnt
ss << 0 if S[-1] == '0'

if ss.size/2 <= K
  puts N
  exit
end

tmp = 0
0.step(2*K) do |i|
  tmp += ss[i]
end
ans = tmp
(2*K+1).step(ss.size-2,2) do |i|
  tmp = tmp + ss[i] + ss[i+1] - ss[i-2*K-1] - ss[i-2*K]
  ans = tmp if tmp > ans
end
puts ans