読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

数式を $$ で囲んで書いてますが面倒くさいので、いちいち、はてな書式にしたりしません

Google Code Jam 2016 - Qualification Round

GCJ 2016 予選

解法

  • A: シミュレーション
  • B: 数える
  • C: 力技 (乱択)
  • D: 読んでない

A. Counting Sheep

0がINSOMNIAなのは自明. 1-2000で手元で実験. どれも最大 75step で終了するので、2000より大きな数字もみんなそんな感じで、短いステップで終了すると信じてシミュレーションする.

gets.to_i.times {|cx|
  n = gets.to_i
  if n == 0
    puts "Case ##{cx+1}: INSOMNIA"
  else
    memo = [false] * 10
    k=0
    i=1
    while k < 10 do
      (n*i).to_s.chars.each{|s|
        kc = s.ord - '0'.ord
        if memo[kc] == false
          memo[kc] = true
          k += 1
        end
      }
      if k == 10
        puts "Case ##{cx+1}: #{n*i}"
      end
      i += 1
    end
  end
}

B. Revenge of the Pancakes

連続した +- をひと塊に扱って良い. 例えば -+++--+- と同様に扱え、こちらだけを考える. ボトムが - で長さが n...-+-end_with_minus(n) ボトムが + で長さが n...+-+end_with_plus(n) と呼ぶ.

問題が求めるものを f とする.

でまあ、なんか適当に考察すると

  • f(end_with_plus(n)) = n-1
  • f(end_with_minus(n)) = n

である.

  • f(end_with_plus(n)) = f(end_with_minus(n-1))
    • ..-+ \rightarrow^* ..++
  • f(end_with_minus(n)) = f(end_with_plus(n-2)) + 2
    • ..-+- \rightarrow^* ..++- \rightarrow ..--- \rightarrow ..+++

みたいな感じ.

def nub(xs)
  ys = []
  if !xs.empty?
    for x in xs do
      ys << x if ys[-1] != x
    end
  end
  ys
end

gets.to_i.times {|cx|
  xs = nub gets.chomp.chars.map{|s| s == '+'}
  ans = xs.length
  ans -= 1 if xs[-1]
  puts "Case ##{cx+1}: #{ans}"
}

C. Coin Jam

smallは32桁、largeは64桁の二進数であって、最上位ビットと最下位ビットが1のものを、ランダムに生成して、素数かどうかをチェックした.

次は実際に用いた、1個の数を生成して、jam coin なら、求められる出力をするだけのものだけど、本当はよくない.

require 'prime'

N = 64

def powmod(a,k,m)
  return 1 if k == 0
  t = powmod(a,k/2,m)
  t = (t * t) % m
  t = (t * a) % m if k%2==1
  t
end

def test(n)
  return false if n<2
  return true if n<4
  return false if n%2==0
  d = n-1
  while d%2 == 0
    d /= 2
  end
  100.times {
    a = rand(n-1) + 1
    y = powmod(a, d, n)
    t = d
    while t != n-1 && y!=1 && y!=n-1
      y = (y * y) % n
      t *= 2
    end
    return false if y!=n-1 && (t%2==0)
  }
  true
end

def factor(x)
  i = 2
  while i * i <= x
    return i if x % i == 0
    i += 1
  end
  return 1
end

s = "1#{(1..(N-2)).map{|_|rand(2)==0?'0':'1'} * ''}1"
ok = true
evi = []
(2..10).each{|b|
  x = s.to_i(b)
  if test(x)
    ok = false
    exit 0
  end
  evi << factor(x)
}
if ok
  puts "#{s} #{evi * ' '}"
end

素数の判定はミラーラビン法を用いてるのに、因数を求めるのに、試し割りを行っているので、たまに、なかなか終わらないことがある. 上のコードをを main.rb として次を実行する.

: > out
for _ in `seq 500`; do
  timeout 2s ruby main.rb >> out
done

重複がないかをチェックして正しく欲しい個数が得られたのを確認したら、頭に Case #1: を付けて提出.

2-100 くらいで試し割りして、割り切れなかったら素数であると保守的に判定する. 合成数のときは因数も得られる.

smallで作った32bitを並べればいい. 因数もsmallでのそれを使える.

D. Fractiles

読んでない