Google Code Jam Japan 2011 予選

Perl

Google Code Jam Japan 2011
C問題だけなんとか通った。
与えられた整数を2つの整数の和で表した場合にそれぞれの整数値で立っているビット数の総和の最大値を求める、というもの。

#!/usr/bin/perl
use strict;
use warnings;
use Math::BigInt;

my $T = <>;
for my $X (1 .. $T) {
    my $line = <>;
    my $a = solve($line);
    printf "Case #%d: %d\n", $X, $a;
}

sub solve {
    my $N = Math::BigInt->new($_[0]);
    my $b = $N->as_bin;
    if ($b =~ /^0b1+$/) {
        return $b =~ tr/1/1/;
    }
    my $c = Math::BigInt->from_bin('0b' . ('1' x (length($b) - 3)));
    return ($c->as_bin =~ tr/1/1/) + ($N->bsub($c)->as_bin =~ tr/1/1/);
};

とりあえず与えられた数値に最も近い2^n-1とで分ければ総和が最大になるような気がしたので…(ちゃんと検証していない


A問題も挑戦してみて愚直にカードを模した配列をその通りに動かしてsmallは通ったけど当然のようにlargeでメモリ足りなくなって死んだ orz ターゲットのカードの位置の移動だけを逆から追っていくのが良かったのかな…？