Google Code Jam 2011 Qualification Round

そういえば書き忘れてた。Google Code JamのQualification Roundに挑戦していたのでした。Perlで。
一応A, B, Cが通って無事通過できていたらしい。Dは問題の意味を理解出来ぬまま寝てしまった…。

A. Bot Trust

片方が動いている間にもう片方が並行して次の目標に移動、というのを上手く表現できず非常に苦労した。絶対もっと上手いやり方があるはずなのであとで他の人のコード見て復習しよう…。

#!/usr/bin/env perl
use strict;
use warnings;
use List::Util 'max';

chomp(my $T = <>);
for my $i (1 .. $T) {
    chomp(my $line = <>);
    my $answer = solve(split / /, $line);
    printf "Case #%d: %d\n", ($i, $answer);
}

sub solve {
    my @array = @_;

    my $a = 0;
    my $bot = +{
        O => 1,
        B => 1,
    };
    my $prev = '';
    my $buff = 0;
    my $N = shift @array;
    for (1 .. $N) {
        my ($R, $P) = splice @array, 0, 2;
        my $move;
        if ($prev eq $R || $prev eq '') {
            $move = abs($bot->{$R} - $P);
            $buff += $move + 1;
        }
        else {
            $move = max(0, abs($bot->{$R} - $P) - $buff);
            $buff = $move + 1;
        }
        $a += $move + 1;
        $bot->{$R} = $P;
        $prev = $R;
    }

    return $a;
}

B. Magicka

問題の意味を理解するのに時間がかかったが、とにかくそのまま条件通りに配列操作するコードを素直に書いた。条件の判定部分が汚い…。

#!/usr/bin/env perl
use strict;
use warnings;

chomp(my $T = <>);
for my $i (1 .. $T) {
    chomp(my $line = <>);
    my @answer = solve(split / /, $line);
    printf "Case #%d: [%s]\n", ($i, join ', ', @answer);
}

sub solve {
    my @array = @_;

    my @combines = ();
    my @opposes  = ();

    my $C = shift @array;
    for (1 .. $C) {
        push @combines, [ split //, shift @array ];
    }

    my $D = shift @array;
    for (1 .. $D) {
        push @opposes, [ split //, shift @array ];
    }

    my $N = shift @array;
    my @elements = split //, shift @array;

    my @answer = ();
    die if $N != scalar @elements;

  INVOKE:
    for (1 .. $N) {
        my $last = $answer[-1];
        my $elem = shift @elements;
        push @answer, $elem;
        if (scalar @answer > 1) {
            for my $combine (@combines) {
                if (($elem eq $combine->[0] && $last eq $combine->[1]) ||
                        ($elem eq $combine->[1] && $last eq $combine->[0])) {
                    splice @answer, scalar @answer - 2, 2, $combine->[2];
                    next INVOKE;
                }
            }
        }
        for my $oppose (@opposes) {
            if ($elem eq $oppose->[0] || $elem eq $oppose->[1]) {
                for my $c (@answer) {
                    if (($c eq $oppose->[0] && $elem eq $oppose->[1]) ||
                            ($c eq $oppose->[1] && $elem eq $oppose->[0])) {
                        @answer = ();
                    }
                }
            }
        }
    }

    return @answer;
}

C. Candy Splitting

結構スッキリ書けたんじゃないかと思う。

#!/usr/bin/env perl
use strict;
use warnings;
use List::Util qw/min sum reduce/;

chomp(my $T = <>);
for my $i (1 .. $T) {
    chomp(my $N = <>);
    chomp(my $line = <>);
    my $answer = solve($N, split / /, $line);
    printf "Case #%d: %s\n", ($i, $answer);
}

sub solve {
    my ($N, @C) = @_;

    return 'NO' if reduce { our ($a, $b); ($a + 0) ^ ($b + 0) } @C;
    return sum(@C) - min(@C);
}

感想

勉強と経験と練習が必要だなぁ、と感じた。時間制限のある次のRound以降は残れない気がする…。