Paiza プログラミング彼女の解法と不満

プログラミング

TOP
Old Archives
Paiza プログラミング彼女の解法と不満

めがね
- その1
- その2
水着
Paizaへの不満

Paizaで展開している、「プログラミング彼女」というサブコンテンツ。

めがね

Paiza B級。

ビットマップマッチングだが、値は

のような文字列で与えられる。マッチングパターンも同様だ。

結構馬鹿馬鹿しい。

その1

ip = []
tp = []

gets.chomp.to_i.times {|n| ip << gets.delete(" ") }
gets.chomp.to_i.times {|n| tp << gets.chomp.delete(" ") }
tp[0] = Regexp.new(tp[0])

ip.each_with_index do |ips, ipi|
  ips.scan(tp.first) do
    offset = $`.length
    if tp[1 .. -1].each.with_index.all? do |tpp, tpi|
                                          ip[ipi + (tpi + 1)][offset, tpp.length] == tpp
                                        end
      print "#{ipi} #{offset}"
      exit 0
    end
  end
end

これが通過しなかった。

手元でテストする限り、これで通過しないケースは発見できなかったのだが、case4で0.11secでこけてしまう。

これは納得できないところだ。

文字列の正規表現マッチングを行っているため、かなり魔術的に見えるだろう。しかし、実はそうでもない。

「文字列」というが、Rubyの場合は文字列はバイト列も含む。バイナリ検索にしてもバイトパターンのマッチングは普通なので、別にそのために文字列検索を行ってもなんら問題はない。

本来は多重配列を用いたマトリックスを求めていたのだろうけれども、Rubyの能力を考えれば配列よりも文字列のほうがはるかに扱いやすいし速いので、ちょっと魔術的でもこちらのほうが良いと考えた。

その2

matched = Array.new
base = Array.new
target = Array.new

gets.chomp.to_i.times { base << gets.chomp.delete(" ") }
gets.chomp.to_i.times { target << gets.chomp.delete(" ") }


target.each do |ts|
  matched << ( l = Hash.new )
  base.each_with_index do |x, i|
    o = -1
    while o = x.index(ts, (o + 1))
      l["#{i} #{o}"] = [i, o]
    end
  end
end

print(matched.first.keys.select do |k| 
  y, x = *matched.first[k]
  matched.length.times do |n|
    unless matched[n]["#{y + n} #{x}"]
      break nil
    end
  end
end.first)

ダメだと言われたので改修してみた。各パターンにおいてマッチするメトリックをハッシュに格納し、マッチ側パターンの行数縦に連続するものをマッチとみなす。速度的にも効率的にも悪くない。これで通過

水着

Paiza A級。

階乗の、末尾0を除いた末尾9桁を出力せよ、という問題。本来はInteger Overflow対策が求められるのだろうが、RubyはBignumがあるため、そこは不要。

しかし、実効速度に伴うタイムアウトという壁が立ちふさがった。

その1

def fact(n)
    if n <= 1
        n
    else
        n * fact(n - 1)
    end
end

base_n = gets.chomp.to_i
ret_n = fact(base_n).to_s
ret_n =~ (/(.{0,8}[^0])0*$/)
print $1.sub(/^0*/, "")

理論上はOKで、実際テストではOKだったが、Case3でコケる。おそらくはコールスタック枯渇。

その2

num = (1 .. gets.chomp.to_i).inject {|x, sum| x * sum }
print num.to_s.sub(/0*$/, "")[-9 .. -1]

コールスタックが枯渇しないように、Enumerable#injectを使ったループに変更した。だが、Case4で15.00secで失敗する。おそらくはタイムアウト。

その3の1

print((1 .. gets.chomp.to_i).inject {|x, sum| (x * sum).to_s.sub(/0*$/, "").to_i % 1000000000 })

タイムアウトを避けるため、常に9桁に抑制することにした。

このコード、計算結果が1000000000だった場合に、商余が0になってしまうため失敗するが、事前に0を除いているために起こりえない。

だが、これはあっさり失敗してしまう。手元では通過していたため、失敗理由がわからなかった。

その3の2(通過)

print((1 .. gets.chomp.to_i).inject {|x, sum| (x * sum).to_s.sub(/0*$/, "").to_i % 1000000000000 } % 1000000000)

計算桁を増やして最後に9桁に落とすようにした。これで通過したが、計算桁はなんとなく増やしているだけなので、理論的には失敗しうる。

その3についての検証

r = (1 .. gets.to_i).inject([1, 1]) do |sum, x|
  puts "---" + x.to_s
  puts( a = (( x * sum[0] ).to_s.sub(/0*$/, "").to_i % 1000000000) )
  puts( b = (( x * sum[1] ).to_s.sub(/0*$/, "").to_i % 100000000000) )
  sum = [a, b]
end

puts "**ANSWER"
puts r[0]
puts r[1] % 1000000000

puts "*****"

p(137921024 * 50)
p(83137921024 * 50)
p((137921024 * 50).to_s.sub(/0*$/, "").to_i)
p((83137921024 * 50).to_s.sub(/0*$/, "").to_i)
p((137921024 * 50).to_s.sub(/0*$/, "").to_i % 1000000000)
p((83137921024 * 50).to_s.sub(/0*$/, "").to_i % 100000000000)

なんとなく想像はついたが、検証してみた。

!50の結果が変わってしまう。これは、!49の時点では

137921024
83137921024

と9桁/11桁で正しいが、!50になると

68960512
41568960512

と8桁/11桁になってしまう。0を除く前の時点で

6896051200
4156896051200

1桁増えているが、0が末尾に2つ増えており、0を除くことで2桁減る。結果として1桁減ってしまうことになる。

計算を続けていくと、この誤差は消滅するが（桁上がりすれば良い）、与えられた数によっては失敗することになる。これを考慮すると正しくは

print((1 .. gets.chomp.to_i).inject {|x, sum| (x * sum).to_s.sub(/0*$/, "").to_i % (1000000000 * (10 ** ($&.length.zero? ? 1 : $&.length) ) ) } % 1000000000)

とすれば良いはず。

Paizaへの不満

条件が予測できない

条件は一応書かれてはいるが、それ以外の条件が多すぎる。

コールスタックの枯渇は予測できるからいいとしても、タイムアウトという条件は記載されていないし、めがねのその1が失敗する理由もわからない。

これで技術を評価されるというのはとても不満だし、だいたい大した機能もない開発環境で、妥当性検証の方法も単一のサンプル、それもどのような入力かを明確にしないままであり、入力の仕様も（業界では一般的な形式なのかもしれないが）非常にわかりにくい。

デバッグできない

失敗した場合でもなぜ失敗したのか分からない。そのためデバッグすることができない。

提出前に失敗した場合でも、全体出力を見ることができず、かつデバッグせずに提出することを前提としているためデバッグはかなり難しい。

私はこうしたことは不毛だと思っている。プログラムはちゃんと磨き上げて動くコードにするものだろう。そして間違いなく動くことが確認されて、はじめてリリースだ。

確認もデバッグもできないままということで、一度しか提出チャンスがないということにも強い違和感を覚える。

いつからこんなつまらない業界になったのか

これはPaizaに限った話ではないけれど、IT業界が、まず履歴書、そして業務履歴書なんてつまらない業界になってしまったのはいつからなんだろう。

少なくとも、私がお呼ばれした時には能力さえあればいいという空気があった。その時点でコンピュータを使うこなせる人間なんて変人が多かったし、型なしの掟破りという印象が強い。

だが、近年は、他業界よりもさらに「即戦力」ばかり求められ、経験がなければやらせないというところばかりで、「経験はどこでつめますか？」という状態。結局そのために経歴の捏造が横行しているわけだ。

年齢も経歴も関係なしの実力次第の世界だと思うのに、そこまで経歴に固執するのは一体なぜなのだろう。

折角、コードを直接みることができるPaizaであるにも関わらず、そのフォーマットを要求するのはいかがなものか。さらに「趣味/1年未満」というくくりは一体なんなのか。そして、定型的な業務におけるカテゴリしか用意していないのもなんなのか。実際はもっと多様で、能力とは直結していないはずなのだが。