はじめに

えっとまあタイトルの通り。一度やってみようかな、ということで、英語ニガテですが問題を読み読み、GCJに初参加しました。無事全完できたので簡単な解説を。まあ公式の解説はあるのですが。なお、全てRubyで実装しています。

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 を出力する、となります。

実装

いやもう、ベタに倍数をあげて桁を記録する ( 10bitで ) という方法で実装しました。

gets
$<.each_with_index{|s,i|
  n=s.to_i
  j=t=0
  puts "Case ##{i+1}: "+
    (n<1?:INSOMNIA: loop{
      (j+=n).to_s.bytes{|c|t|=1<<c-48}
      t<1023or break j
    }).to_s
}

B. Revenge of the Pancakes

問題

+ と - からなる文字列に以下の操作を行って全て + にするための最少手順数を出力する問題です。

その操作とは、先頭の数文字 ( 1文字～全部 ) を逆転させて、+ と - を交換するので1手順です。例えば、+++--+++ の先頭4文字を対象とした場合、1手順で +++--+++ → -++++++ → +---+++ と変化します。

最低手順数としては、次のようになります。

+++ → 既に全て + なので手順自体が不要で 0 手。
--+++---- → 2文字、5文字、全部と順に選択 ( --+++---- → +++++---- → --------- → +++++++++ ) の3手が最少。

実装

結局、同じ文字種の塊が幾つあるか ( ただし末尾の + の塊は除外 ) なので、…。…。まあ、塊の数を数えるコードなんですが、なんでこう実装したのか自分でも良く分かりません。

gets
$<.each_with_index{|s,i|
  n=0
  n+=1while s.sub!(/\+*$/,"").tr!("-+","+-")
  puts "Case ##{i+1}: #{n}"
}

文字数重視なら、Perlで次のように実装すれば良かったのでは、的な。

<>;s/\+*$//,print"Case#",++$i,": ",0+s/(.)\1*//g,$/for<>

C. Coin Jam

問題

自然数 n,j に対して、1 で始まり 1 で終わる、0,1 計 n 文字の文字列の中で、2進数～10進数いずれと解釈しても非素数 ( 1 ではないので自然と合成数に ) となるものを何でも良いので j 個出力します。なお、出力する際は 2進数～10進数それぞれの解釈での約数 ( 1 と自身以外、任意に1つずつ ) を10進数で付け加えます。

実装

100…001 から小さい順に調べ上げ、素数の小さい順で試し割りするというゴリっとした実装です。ただし、素数であることが確定するまでやると時間がかかるので ( 別にテキトーに捨てても良いので )、試し割りする素数に上限を設けています。

require 'prime'
gets
n,j=gets.split.map &:to_i
puts "Case #1:"
i=2**(n-1)-1
u=999
while j>0
  s=(i+=2).to_s(2)
  a=(2..10).map{|b|
    x=s.to_i(b)
    Prime.each(u){|q|break if q*q>x;break q if x%q <1 }or break
  } and (
    puts [s,*a]*" "
    j-=1
  )
end

実は各ケースのnは偶数なので、特定のパターンは試し割りするまでもなく合成数と分かるのですが…。ウカツ!!

D. Fractiles

問題

自然数 k,c に対し、フラクタル的な性質を持つ、G,L の2種 k^c 枚のパネルを考えます。「フラクタル的」とは

c=1 であれば、G,Lの配置は任意
c＞1 の場合、c=1 の時の配置から始めて、
- L は c=1 の時の配置 k 枚に置き換える
- G は k 枚の G に置き換える

というものを指します。例えば、k=c=3 の場合、LLG → LLG-LLG-GGG → LLG-LLG-GGG-LLG-LLG-GGG-GGG-GGG-GGG という推移ができるので、LLGLLGGGGLLGLLGGGGGGGGGGGGG というのはこの「フラクタル的」に該当します。

ここで、一部分 ( 上限 s 枚 ) のパネルだけを調べて、G の存在 ( 1枚でもあれば「存在」) を判定できるかどうか、判定できるなら調べるパネルの位置のリスト ( 先頭を 1 とし、s枚以下であれば冗長でも良い ) を何か1組、判定できない ( 場合がある ) なら IMPOSSIBLE を出力します。

実装

実は small ケースの場合、s≧k なので、先頭の k 枚を調べれば必ず判定できるのですが。large では s がもっと小さい場合があるので、それでは不十分です。で、次のように実装しました。

gets
$<.each_with_index{|l,i|
  k,c,s=l.split.map &:to_i
  a=(0..k-1).each_slice(c).map{|r|r.inject(0){|t,e|t*k+e}+1}
  puts "Case ##{i+1}: "+(a.size>s ? "IMPOSSIBLE": a*" ")
}

フラクタル的な推移をした場合、L となるパネルの位置 ( 0開始とする ) の k 進法表記には興味深い性質があるのですね、実は。例えば、k=4 で LGGL から始めた場合。

c=1: LGGL → Lの位置は 0,3
c=2: LGGLGGGGGGGGLGGL → Lの位置は 0,3,12,15 4進表記で 00,03,30,33
c=3: LGGLGGGGGGGGLGGLGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGLGGLGGGGGGGGLGGL → Lの位置は4進表記で 000,003,030,033,300,303,330,333
…

というように、c=1 の時の L の位置の数だけで構成される、c 桁の k 進数になります。
ということは、k=4,c≧4 であれば 4進数で0…0123番目のパネルを調べれば事足りると分かります。これが L なら c=1 の時、0～3番目、すなわち全てが L だったということで、逆に G なら c=1 の時、いずれかに G が存在したということになるからです。

c が小さい時 ( k未満の時 ) は 1枚では足りませんが、0～k-1を c桁ずつ区切って k 進数を作れば済むと分かります。s枚で足りるかどうかもtrivialですね。

終わりに

アルゴリズムというより、問題の性質を読み解ければ…という感じの出題かなあ、という感想です。ラウンドが進むとどうなるんでしょうね。まあ初参加なので気楽にいってみようと思います。

ange1のブログ

GCJ ( Google Code Jam ) Qualification Round に参加しました