ACM プログラミングコンテスト 2004 国内予選開催
チーム名ばかり目立ってるようで。
例題は以下のURLだそうで。
ずいぶん簡単だなと思ったけど、Cのほうは下手すると計算量が爆発しますね。ちょっとrubyで解いてみる。
A.rb
def main()
while (committees = scan_committees())
puts committees.ok_date()
end
end
def scan_committees()
require 'scanf'
size_line = gets()
man_count, min_count = size_line.scanf("%d %d")
return nil if man_count == 0 and man_count == 0
commitees =
man_count.times do
line = gets()
dates = line.split()
dates.shift
commitees << dates
end
return Committees.new(commitees, min_count)
end
class Committees
def initialize(commitees, min_count)
@commitees = commitees
@min_count = min_count
@ok_date = 0
find_date()
end
attr :ok_date
def ok_date_list()
ok_dates =
@commitees.each do |commitee|
commitee.each do |date_text|
date = date_text.to_i
ok_dates[date] = 0 if ok_dates[date] == nil
ok_dates[date] += 1
end
end
return ok_dates
end
def find_date()
ok_dates = ok_date_list()
ok_max = 0
date = 0
ok_dates.each_index do |i|
next if ok_dates[i] == nil
if ok_dates[i] > ok_max
date = i
ok_max = ok_dates[i]
end
end
@ok_date = date if ok_max >= @min_count
end
end
main()
単純に配列に足して突っ込むだけ。そして条件に合う日付を見つける。速さだけを求めるなら、読み込みながら計算したり、中間結果を入れる配列をmapとかで工夫したりできるでしょう。
C.rb
def main()
while (matrix = scan_matrix())
secret_num = SecretNumber.new(matrix).secret()
puts secret_num
end
end
def scan_matrix()
require 'scanf'
size_line = gets()
width, height = size_line.scanf("%d %d")
if width == 0 and height == 0
return nil
end
matrix =
height.times do |i|
line = gets()
scanner = "%c" * width
matrix[i] = line.scanf(scanner)
end
return matrix
end
class SecretNumber
def initialize(matrix)
@matrix = matrix
@coded =
@matrix.each do |line|
@coded << Array.new(line.size, nil)
end
find_coded()
@secret = seek_secret_num()
end
attr :secret
def find_coded()
@matrix.size.times do |x|
@matrix[x].size.times do |y|
next if @coded[x][y]
find_coded_in_submatrix(x, y)
end
end
end
def seek_secret_num()
secret_num = 0
@coded.each do |line|
line.each do |coded_text|
if coded_text.size > 0
coded_num = coded_text.to_i
secret_num = coded_num if secret_num < coded_num
end
end
end
return secret_num
end
def find_coded_in_submatrix(start_x, start_y)
return "" if start_x >= @matrix.size or start_y >= @matrix[start_x].size
return @coded[start_x][start_y] if @coded[start_x][start_y]
char = get_char_at(start_x, start_y)
unless /\d/ =~ char
@coded[start_x][start_y] = ""
return ""
end
to_right = find_coded_in_submatrix(start_x + 1, start_y)
to_bottom = find_coded_in_submatrix(start_x, start_y + 1)
larger = max_as_num_text(to_right, to_bottom)
@coded[start_x][start_y] = char + larger
return @coded[start_x][start_y]
end
def get_char_at(x, y)
@matrix[x][y]
end
def max_as_num_text(a, b)
if a.size == b.size then
a.to_i > b.to_i ? a : b
else
a.size > b.size ? a : b
end
end
end
main()
部分行列で各セルに対しての最大数を求めていく。各セルは隣接セルのすでにある結果を使って最大数を保存しておく。その部分行列をどんな手段でもいいので、すべてのセルのコード数が判明するようにもと行列まで大きくしていく。これも行列の保持の仕方や部分行列の拡大の仕方の工夫で多少早くできるでしょう。
全部のセルでのコード数が求まったら全部トレースして、その中で最大のものを取り出せばよい*1
部分行列での計算結果を再利用せず、各セルごとに最大数を探していくと単純再帰のフィボナッチ数列みたく計算量が爆発するので注意。
追加：最大数を一緒に計算していく方法。やっぱりバッファは必要。最大数はバックトラック時に順次計算していけばよい。
def main()
while (matrix = scan_matrix())
secret_num = SecretNumber.new(matrix).secret().to_i
puts secret_num
end
end
def scan_matrix()
require 'scanf'
size_line = gets()
width, height = size_line.scanf("%d %d")
if width == 0 and height == 0
return nil
end
matrix =
height.times do |i|
line = gets()
scanner = "%c" * width
matrix[i] = line.scanf(scanner)
end
return matrix
end
class SecretNumber
def initialize(matrix)
@matrix = matrix
@coded =
@matrix.each do |line|
@coded << Array.new(line.size, nil)
end
@secret = 0
find_coded()
end
attr :secret
def find_coded()
find_coded_in_submatrix(0, 0)
end
def find_coded_in_submatrix(start_x, start_y)
return "" if start_x >= @matrix.size or start_y >= @matrix[start_x].size
return @coded[start_x][start_y] if @coded[start_x][start_y] != nil
char = get_char_at(start_x, start_y)
unless /\d/ =~ char
@coded[start_x][start_y] = ""
return @coded[start_x][start_y]
end
to_right = find_coded_in_submatrix(start_x + 1, start_y)
to_bottom = find_coded_in_submatrix(start_x, start_y + 1)
larger = max_as_num_text(to_right, to_bottom)
cel_code = char + larger
@coded[start_x][start_y] =cel_code
@secret = max_as_num(cel_code, @secret)
return @coded[start_x][start_y]
end
def get_char_at(x, y)
@matrix[x][y]
end
def max_as_num_text(a, b)
if a.size == b.size then
a.to_i > b.to_i ? a : b
else
a.size > b.size ? a : b
end
end
def max_as_num(a, b)
a.to_i > b.to_i ? a : b
end
end
main()
