今日は入籍1ヶ月記念。けど特に何もないな。庭いじりでもするか。

そういや式の前々日にdevfest2010のquizメールが来たので、
このタイミングかよ！と思いつつコーディングしてたのを思い出した。

問題の詳細は
無印吉澤 - Google DevFest 2010 Japan Quizの問題とその答えの一例（Rubyで解きました）
を見てください。

一応僕も全部解いたけど、結局落選でした。。。
てか、もっと難しくしないと誰でも解けちゃうからgoogle信者以外当選できねーだろー
って、そうでもなかったのかな。

当落ラインとかは以下に載ってた。
http://www.mdn.co.jp/di/newstopics/12541

てことで、もう旬を過ぎてますが、自分の酷いコードも晒しておきます。
ちなみに清書とか一切なしで、書き殴りでデバッグコード込みです。
シンボル名とかグローバルな感じの酷さはかなりの恥ずかしさですね。


漢字変換サーバ
cgiのあたりはどっかからコピペしてるな。
これは下と比べれば綺麗にかけた気もするけど、問題自体がシンプルなので当然か。
てか、この問題の配点の高さが不可解。

#!/usr/bin/ruby

#$x = ["", "一", "二", "三", "四", "五", "六", "七", "八", "九"] 
#$y = ["", "十", "百", "千"]
#$z = ["", "万", "億", "兆", "京"]
#$zero = "零"

$x = ["", "P", "R", "J", "B", "S", "Q", "D", "M", "Y"] 
$y = ["", "G", "K", "E"]
$z = ["", "F", "H", "N", "Z"]
$zero = "T"

# n 1以上の整数
def yonketa(n)
  r = ""

  for k in 0..3
    i = n % 10
    if i == 1 && $y[k] != ""
      r = $y[k] + r
    elsif i > 0
      r = $x[i] + $y[k] + r
    end
    n /= 10
  end
  r
end

def kansuuji(a)
  r = ""
  
  if a == 0
    r = $zero
  end
  
  k = 0
  while a > 0
    b = a % 10000
    if b > 0
      r = yonketa(b) + $z[k] + r
    end

    a = (a / 10000).to_i
    k += 1
  end
  r
end


require "cgi"
cgi = CGI.new
v = cgi['n'].to_i

print cgi.header({
                   "nph"        => false,
                   "status"     => "200 OK",  # == "200 OK"
                   "connection" => "close",
                   "type"       => "text/plain",
                   "charset"    => "utf-8",
                   "language"   => "ja"
                 })

print kansuuji(v)

パッチワーク
標準入力で突っ込むと標準出力でpでダンプされるので、その後s/,/\n/gとかして提出。
最初に思いついたのをそのまま組んだだけ。
非常に人間的なアルゴリズムで重く、提出問題ではさすがにちょっと時間がかかった。

綺麗にやる方法がすぐ思いつかなかったのだけど、
union findってアルゴリズムを使うのが正解だったようです。
http://algorithms.blog55.fc2.com/blog-entry-46.html

なるほどー、
こういうのを思いつきそうで思いつかないあたりが、頭が弱ってる証拠だなあ。
top coderやってる人だと瞬殺で最適アルゴリズムに辿り着くんだろうね。
僕なんかruby使ってる時点で弱いし、そもそもrubyの文法も忘れかけてて、
片っ端から文法を調べながら書いてたし、どうしようもないわ。
高橋直大先生とかだと何分で解けるんだろう。

#!/usr/bin/ruby

$k = Array.new

STDIN.each do |a|
  b = Array.new
  for i in 0..a.length-1
    c = a[i]
    if c == ?A
      b.push(1)
    elsif c == ?B
      b.push(2)
    else
      break
    end
  end
  $k.push(b)
end

p $k

def paint(x, y, z, c)
  r = 0
  
  if y >= 0 && x >= 0 && y < $k.length && x < $k[y].length && $k[y][x] == z
    $k[y][x] = c
    r = 1 + paint(x , y - 1, z, c) + paint(x, y + 1, z, c)
    r += paint(x - 1, y, z, c) + paint(x + 1, y, z, c)
  end
  r
end

$size = Array.new

for y in 0..$k.length-1
  for x in 0..$k[y].length-1
    c = $k[y][x]
    if c > 0
      $size.push([x, y, paint(x, y, c, -c)])
    end
  end
end

$size.sort! {|a,b| b[2] <=> a[2]}
p $size

$size.each do |a|
  if a[2] == $size[0][2]
    x, y = a
    paint(x, y, $k[y][x], 0)
  end
end

ret = Array.new

r = ""
for y in 0..$k.length-1
  s = 0
  for x in 0..$k[y].length-1
    c = $k[y][x]
    r += (c == -1) ? "A" : (c == -2) ? "B" : "_"
    s += c == 0 ? 1 : 0
  end
  r += "\n"
  ret.push(s)
end

print r
p ret