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

シェアする

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

フォローする