Rubyの練習

見直すと結構無駄があったので、Rubyの練習をかねてGCJ2008のQualification Roundを改めて解いてみる。実行時間を犠牲にしてもコードは短く書いてる。Ruby使ってみるかなとか思ってたけど、比較してみるとさほどありがたいものではなかった。Pythonも試してみるかな。

問題Cはなんかうまくいかない。あきらめて強引に積分しようとしたけど、答えは合わず。。。

A. Saving the Universe

#!/usr/bin/ruby

# the number of cases
n = $stdin.gets.chomp!.to_i
n.times do |i|

  # the number of search engines
  s = $stdin.gets.chomp!.to_i
  engines = {}
  s.times do
    engine = $stdin.gets.chomp!
    engines = 0;
  end

  # the number of incomming queries
  q = $stdin.gets.chomp!.to_i
  switch = 0
  count = 0
  q.times do
    query = $stdin.gets.chomp!
    if engines.include?(query) && engines == switch
      engines = switch + 1
      count += 1
    end
    if count == s
      count = 1
      switch += 1
      engines = switch + 1
    end
  end
  printf("Case #%d: %d\n", i + 1, switch)
end

Rubyだと、インクリメント、デクリメント演算子が使えない！

ちなみにPerlで書いたもの

#!/usr/bin/perl

use strict;

my $N = <STDIN>;

foreach my $i (0 .. $N - 1) {
    my $switch = 0;
    my $S = <STDIN>;
    my %engines;
    foreach my $j (0 .. $S - 1) {
	my $engine = <STDIN>;
	chomp($engine);
	$engines{$engine} = 0;
    }
    my $count = 0;

    my $Q = <STDIN>;
    foreach (0 .. $Q - 1) {
	my $query = <STDIN>;
	chomp($query);
	if (exists($engines{$query}) && $engines{$query} == $switch) {
	    $count++;
	    $engines{$query} = $switch + 1;
	}
	if ($count == $S) {
	    $count = 1;
	    $engines{$query} = ++$switch + 1;
	}
    }
    printf "Case #%d: %d\n", $i + 1, $switch;
}
exit(0);

B. Train Timetable

構造体かオブジェクトを使いたい問題。

#!/usr/bin/ruby

class TrainSchedule
  def initialize(dept, arrv, from)
    @dept = dept                # deperture time
    @arrv = arrv                # arrival time
    @from = from                # deperture station
  end
  def dept
    return @dept
  end
  def arrv
    return @arrv
  end
  def from
    return @from
  end
end

# The number of cases
n = $stdin.gets.chomp!.to_i
n.times do |i|
  t = $stdin.gets.chomp!.to_i
  (na, nb) = $stdin.gets.chomp!.split(/ /)
  na = na.to_i
  nb = nb.to_i
  schedule = <>
  na.times do
    line = $stdin.gets.chomp!
    /(\d{2}):(\d{2}) (\d{2}):(\d{2})/ =~ line
    dept = $1.to_i * 60 + $2.to_i
    arrv = $3.to_i * 60 + $4.to_i
    schedule.push(TrainSchedule.new(dept, arrv, 'A'))
  end
  nb.times do
    line = $stdin.gets.chomp!
    /(\d{2}):(\d{2}) (\d{2}):(\d{2})/ =~ line
    dept = $1.to_i * 60 + $2.to_i
    arrv = $3.to_i * 60 + $4.to_i
    schedule.push(TrainSchedule.new(dept, arrv, 'B'))
  end
  schedule.sort!{ |o1,o2| o1.dept <=> o2.dept }

  trainA = 0
  trainB = 0
  poolA = <>
  poolB = <>
  for train in schedule
    n_dept = train.arrv + t
    if train.from == 'A'
      if (poolA.size > 0 && train.dept >= poolA<0>)
        poolA.shift
      else
        trainA += 1
      end
      poolB.push(n_dept)
      poolB.sort!
    elsif train.from == 'B'
      if (poolB.size > 0 && train.dept >= poolB<0>)
        poolB.shift
      else
        trainB += 1
      end
      poolA.push(n_dept)
      poolA.sort!
    end
  end
  printf("Case #%d: %d %d\n", i + 1, trainA, trainB)
end

ハッシュでカバーしてみたけど。

#!/usr/bin/perl

use strict;

my $N = <STDIN>;
foreach my $i (0 .. $N - 1) {
    my $T = <STDIN>;
    $_ = <STDIN>;
    my ($NA, $NB) = (/^(\d+)\s+(\d+)$/);

    my @tables;
    for my $j (0 .. $NA + $NB - 1) {
	$_ = <STDIN>;
	chomp;
	my ($h1, $m1, $h2, $m2) = (/^0?(\d+):0?(\d+) 0?(\d+):0?(\d+)$/);
	$m1 += $h1 * 60;
	$m2 += $h2 * 60;
	my %entry;
	$entry{'dept'} = $m1;
	$entry{'arrv'} = $m2;
	$entry{'term'} = ($j < $NA);
	$tables<$j> = \%entry;
    }
    @tables = sort {${$a}{'dept'} <=> ${$b}{'dept'}} @tables;
    my @poolA;
    my @poolB;
    my $trainA = 0;
    my $trainB = 0;

    while ($#tables >= 0) {
	my $p = shift(@tables);
	my %table = %{$p};
	my $ready = $table{'arrv'} + $T;
	if ($table{'term'}) {
	    if ($#poolA >= 0 && $poolA<0> <= $table{'dept'}) {
		shift(@poolA);
	    } else {
		$trainA++;

	    }
	    push(@poolB, $ready);
	    @poolB = sort {$a <=> $b} @poolB;
	} else {
	    if ($#poolB >= 0 && $poolB<0> <= $table{'dept'}) {
		shift(@poolB);
	    } else {
		$trainB++;
	    }
	    push(@poolA, $ready);
	    @poolA = sort {$a <=> $b} @poolA;
	}
    }
    printf "Case #%d: %d %d\n", $i + 1, $trainA, $trainB;
}
exit(0);

正攻法で解いたけどもっと早く解けるよなー。

#!/usr/bin/perl -w

use strict;

my $N = ;
foreach my $i (0 .. $N - 1) {
    my $T = ;
    $_ = ;
    my ($NA, $NB) = (/^(\d+)\s+(\d+)$/);

    my @tablesA;
    my @tablesB;
    for my $j (0 .. $NA + $NB - 1) {
	$_ = ;
	chomp;
	my ($h1, $m1, $h2, $m2) = (/^0?(\d+):0?(\d+) 0?(\d+):0?(\d+)$/);
	my $dept = $h1 * 60 + $m1;
	my $arrv = $h2 * 60 + $m2;
	my %entry1;
	my %entry2;
	$entry1{'time'} = $dept;
	$entry1{'dept'} = 1;
	$entry2{'time'} = $arrv + $T - 0.5;
	$entry2{'dept'} = 0;
	if ($j < $NA) {
	    $tablesA<$j> = \%entry1;
	    $tablesB<$j> = \%entry2;
	} else {
	    $tablesB<$j> = \%entry1;
	    $tablesA<$j> = \%entry2;
	}
    }
    @tablesA = sort {${$a}{'time'} <=> ${$b}{'time'}} @tablesA;
    @tablesB = sort {${$a}{'time'} <=> ${$b}{'time'}} @tablesB;

    my $trainA = 0;
    my $trainB = 0;
    my ($poolA, $poolB) = (0, 0);
    foreach my $ref (@tablesA) {
	if ($$ref{'dept'} > 0) {
	    if ($poolA > 0) {
		$poolA--;
	    } else {
		$trainA++;
	    }
	} else {
	    $poolA++;
	}
    }
    foreach my $ref (@tablesB) {
	if ($$ref{'dept'} > 0) {
	    if ($poolB > 0) {
		$poolB--;
	    } else {
		$trainB++;
	    }
	} else {
	    $poolB++;
	}
    }

    printf("Case #%d: %d %d\n", $i + 1, $trainA, $trainB);
}
exit(0);

んなもんか、複数の値を考慮したソートってどう書くんがいいんかな？