「 CodeJam 」一覧

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

GCJ 2017 Qualification Round B: Tidy Numbers

問題

与えられた整数Nについて、N以下で数字が左から昇順に並ぶ最大の数を求める。

例えば、132であれば、129が132以下で数字が1,2,9と昇順に並ぶ最大の数となる。

https://code.google.com/codejam/contest/3264486/dashboard#s=p1

方針

Nから順にデクリメントして条件にあうかチェック、、、みたいな実装だとSmallはクリアできてもlargeは時間がかかりすぎてしまう。

よって、単なる数字の並びの規則性という観点でロジックを考えると、

・左から数字をチェックしていき、降順になる箇所が見つかった場合、前の数字を一つ小さくし、以降の数字を全て9に変更する
 例:14548 -> 14499
・上記操作によりさらに一つ前の数字との大小関係が変わる場合は、同様の処理をもう一つ前の数字についても行う。これを繰り返す。
 例:14438 -> 14399 -> 13999

となる。

実装

gets
n = 1
STDIN.each_line do |line|
    digits =  line.chomp.chars.map(&:to_i)
    prev = digits[0]
    for i in 1..(digits.size-1)
        if digits[i-1] > digits[i] then
            digits[i] = 9
            digits[i-1] -= 1
            j = i - 1
            while(j > 0) do
                if digits[j-1] > digits[j] then
                    digits[j] = 9
                    digits[j-1] -= 1
                end
                j -= 1
            end

            for j in (i+1)..(digits.size-1)
                digits[j] = 9
            end
            break
        end
    end
    printf "Case #%d: ", n
    digits.select{|c| c > 0}.each  do |c|
        print c
    end
    printf "\n"
    n += 1
end

GCJ 2016 Qualification Round B: Revenge of the Pancakes

問題

+ と – からなる文字列Sが与えられる。以下の操作を繰り返して、+ のみの文字列に変換するための最小回数を求める。

・文字列Sのi番目までの+と-を反転させて、なおかつ、逆順にする。

例: 文字列Sが ++–+ でi=3の場合、++- を反転(–+)して逆順(+–)にする。
 その結果、文字列Sは +—+ になる。

https://code.google.com/codejam/contest/6254486/dashboard#s=p1

方針

操作の制約として、必ず先頭から指定した範囲の文字列を反転させることになるので、最後の操作の直前の状態は、以下のように「-の連続と+の連続」または「-のみ」の状態になる。

----++++ (-の連続と+の連続)
-------- (-のみ)

つまり、文字列の前の方から順番に+や-が連続する状態を作っていくようにする。

・先頭が+の場合、順番に文字をチェックしていき、-が出現したら直前までの文字列に対して操作を行う

+++--++
↓ 先頭が+なので4番目に-を見つけた時点で3番目までを操作対象にする
-----++

・先頭が-の場合、上記の逆の操作をする

以上を繰り返すと、文字列の前半が+の連続、-の連続を交互に繰り返すことになり、最終的に+のみになったら処理終了となる。

実装

最初は文字列を実際に反転させる処理を実装し、毎回文字列を先頭からチェックするような実装にしていた。(計算量は O(N^2))

しかしながら、動作確認をしていて、i番目までを処理した時点でそれより前の文字列は + or – の連続になっていることは分かっているので、先頭に戻らずそのままi番目以降の文字をチェックすれば良いことに気づいた。(計算量は O(N))

def solve(cakes)
    n = cakes.size
    return 0 if cakes.count{|c|  c == "+" } == n

    c = cakes[0]
    count = 0
    i = 1
    while(i < n)
        if cakes[i] != c then
            count += 1
            c = (c == "+" ? "-" : "+")
        end
        i += 1
    end
    count += 1 if c == "-" 
    return count
end

i = 1
STDIN.gets
STDIN.each_line do |line|
    line.chomp!
    cakes = Array.new
    line.chars {|c| cakes.push(c)}

    printf("Case #%d: %d\n", i, solve(cakes))
    i += 1
end

GCJ 2016 Qualification Round A: Counting Sheep

問題

与えられた非負整数Nについて、N×1,N×2,…とNの倍数をあげていく。その数の10進表記で見た場合の桁が0~9全て出そろった時の最後の数を出力する。(そろわない場合は”INSOMNIA”を出力)

例:N=2の場合、2×1=2,2×2=4,…,2×35=70,…,2×44=88,2×45=90 で0~9が全て出そろうので、結果は 90 となる。

https://code.google.com/codejam/contest/6254486/dashboard

方針

特に最適な解法というのが思いつかなかったので、単純にNの倍数を上げていきチェックする方法をとった。

なお、INSOMNIA になる条件は N=0 の場合とした。

実装

require 'set'

def solve(n)
    return 0 if n == 0

    digits = Set.new
    i = n
    while(true)
        i.to_s(10).chars { |c| digits.add(c) }
        return i if digits.size == 10
        i += n
    end
end

STDIN.gets

i = 1
STDIN.each_line {|line|
    ret = solve(line.to_i)
    if ret == 0 then
        printf "Case #%d: INSOMNIA\n", i
    else
        printf "Case #%d: %d\n", i, ret
    end
    i += 1
}

Code Jam Japan 2011 決勝 問題A. アンテナ修復

Code Jam Japan 2011の決勝の問題Aを解いてみた。

■ 考え方

・最大になる組み合わせを総当たりで計算した場合、間違いなくLargeが解けないので、何らかの法則を見つける必要がある

・まずは三角形の面積について、基本的な計算方法を明確にする。隣り合うエレメントが作る三角形の面積は、各エレメントの長さをa、bとすると、次のようになる

 a * b * sin(2π/K) / 2

・よって、エレメントの並び順が(X1, X2,・・, Xk)の場合、三角形の面積の合計は、次のようになる

 (X1 * X2 + X2 * X3 + ・・ + Xk * X1) * sin(2π/K) / 2

つまり、(X1 * X2 + X2 * X3 + ・・ + Xk * X1) の部分が最大になる並べ方を求めれば、それでPを求めることが出来る

・上記の値が最大になるのは、X1~Xkを降順にソートした結果をY1~Ykとすると、Y1を基準にY2以降を左右に順に並べていけばよいことになる

 ・・・, Y7, Y5, Y3, Y1, Y2, Y4, Y6, ・・・

■ プログラム

use Math::Trig qw( pi );
sub solve{
my @list = @{$_&#091;0]};
my $size = @list;
my @sorted = sort {$b &#060;=&#062; $a} @list;
my @list2 = ();
$element_list&#091;0] = $sorted&#091;0];
my $x = 1;
my $y = $size - 1;
for(my $i = 1; $i &#060; $size; $i++){
if($i % 2 == 0){
$element_list&#091;$y] = $sorted&#091;$i];
$y--;
}else{
$element_list&#091;$x] = $sorted&#091;$i];
$x++;
}
}
my $result = $element_list&#091;0] &#042; $element_list&#091;$size - 1];
for(my $i = 1; $i &#060; $size; $i++){
$result += $element_list&#091;$i] &#042; $element_list&#091;$i - 1];
}
return ($result / 2 &#042; sin(2&#042;pi()/$size));
}
$count = 0;
while(&#060;&#062;){
chop;
if($count&#062;0){
my $size = $_;
$_ = &#060;&#062;;
chop;
my @list = split(/ /, $_);
printf &#034;Case #%d: %.9f&#092;n&#034;, $count, solve(&#092;@list);
}
$count++;
}