Google Code Jam Japan 2011 の練習問題にチャレンジしてみた
最近、仕事の時間のほとんどが CakePHP のプログラミングだったり、PostgreSQL のチューニングだったりと、すっかりエンジニア生活に戻ってきました。といっても、この数年間、仕事でコードを書く機会がめっきり減っていたので、腕を磨くべく、時間を見つけては、いろいろコードを読んだり書いたりしているのですが、そんなときに、Google が毎年運営しているプログラミングコンテストの Google Code Jam が今回は日本語で挑戦できる、と聞きまして、頭の体操になるかな、とサイトを見にいってみました。
本番の 10/1 を前に練習問題が公開されていたので、無謀とはおもいつつ、ちょっと挑戦。自分の頭の足らなさ加減がバレてしまうのですが、わたしのアプローチを紹介してみたいと思います。腕に覚えのある方は答えを見るまえに、小一時間ほと練習問題にチャレンジすることをおすすめします。
実行は、手元の Macbook Air (2010 Later) で、コードは今回はなんとなく Perl で書いてみました。テストに通ればよし、のプログラムなのでいろいろ手抜きです。
スイッチの状態を愚直に実装しようかと一瞬思ったのですが、すぐに面倒になり、コードにとりかかる前に問題をよく理解しようと、素直に紙で N=1..3 のケースをやってみました。 コツコツ、カチカチとスイッチの状態をひとつずつ、紙に書いてみると、2N-1回目に点灯、2N回で初期状態になりました。ということで、点灯条件と周期が判明、あとはコードに落としこんで完成です。
#! /usr/bin/perl
use strict;
use bigint;
my @RESULT = ('OFF', 'ON');
my $T = <>;
for (my $i = 1; $i <= $T; $i++) {
my ($N, $K) = split(/\s/, <>);
my $r = (($K % 2**$N) == (2**$N -1)) ? 1 : 0;
printf "Case #%d: %s\n", $i, $RESULT[$r];
}
1;
あっけなく完成して拍子抜けしました。これは他の問題も簡単に解けるかも、と一瞬思ったのですが、それは大きな間違いでした。
最初、文章の意味がいまいちつかみきれなくてサンプルと格闘、素因数分解をしてグルーピングする、という意味をようやく理解しました。素数計算とか素因数分解なんてもう何年やっていないんだろう、ということで、まずは必要になりそうなすべての素数をあらかじめ計算した上で素因数分解をし、愚直にグループ分けするコードを作成してみました。サンプルはすんなり通りましたが、small で分単位、これじゃまずいだろうなあ、と思いつつ large にチャレンジしてみましたが、案の定、最初に素数を求めるところで時間切れ。最適化を模索しはじめました。
素数表のつくりかたを工夫してみたり、もともと、素数表を作成する範囲を B までにしていましたが、素因数分解するときには sqrt (B) までの素数で割るだけでいいはず、というのを思いだして、まず計算する範囲を減らそうと、素因数分解する範囲と素数を求める範囲を sqrt(B) にしてみたりしました。これで small を2分を切りました。しかし、これだと当たり前に large だと最初の素数の算出でやっぱり時間切れ。素数表を作るコストも大きいのですが、素因数分解にも時間がかかりすぎ。そもそものアプローチを変えないとダメですね。ここでギブアップしました。
#! /usr/bin/perl
use strict;
use bigint;
my $T = <>;
my @TEST;
my $max_B = 0;
my $min_P = 10**12;
my $RESULT;
for (my $i = 1; $i <= $T; $i++) {
my ($A, $B, $P) = split /\s+/, <>;
push @TEST, [$A, $B, $P];
$max_B = max($max_B, $B) + 0;
$min_P = min($min_P, $P) + 0;
}
my (@base, @primes);
my $max = sqrt($max_B) + 1;
for (my $i = 3; $i < $max; $i+=2) {
next if ($i % 3 == 0);
next if ($i % 5 == 0);
next if ($i % 7 == 0);
push @base, $i;
}
push @primes, (2,3,5,7);
my $i = 7;
while ($i < sqrt($max)) {
for (my $j = 0; $j < scalar(@base); $j++) {
if ($base[$j] % $i == 0) {
splice(@base, $j, 1);
}
}
($i) = shift @base;
push @primes, $i;
}
@primes = (@primes, @base);
for (my $i = 1; $i <= $T; $i++) {
my $q = shift @TEST;
$RESULT = solve(@$q);
printf "Case #%d: %d\n", $i, $RESULT;
}
sub solve {
my ($A, $B, $P) = @_;
my %FACTORS;
my %GROUP;
my $ANSWER = 0;
my $DELETE = 0;
for (my $i = $A; $i <= $B; $i++) {
my $x = $i;
my $g = -1;
for (my $j = 0; $j < scalar(@primes); $j++) {
last if $primes[$j] > $x;
if ((($x % $primes[$j]) == 0) or ($primes[$j] > int(sqrt($i)))) {
my $p = (($x % $primes[$j]) == 0) ? $primes[$j] : $x;
while ($x % $primes[$j] == 0) {
$x = $x / $primes[$j];
}
next if $p < $P;
if ($g == -1) {
if (defined($FACTORS{$p})) {
$g = $FACTORS{$p};
} else {
$g = $ANSWER++;
$FACTORS{$p} = $g;
$GROUP{$g} = [$p];
}
} else {
if (defined($FACTORS{$p})) {
my $gg = $FACTORS{$p};
if ($g != $gg) {
foreach (@{$GROUP{$gg}}) {
$FACTORS{$_} = $g;
}
$GROUP{$g} = [@{$GROUP{$g}}, @{$GROUP{$gg}}];
delete $GROUP{$gg};
$DELETE++;
}
} else {
$FACTORS{$p} = $g;
push @{$GROUP{$g}}, $p;
}
}
last if $x == 1;
if ($primes[$j] > int(sqrt($i))) {
last;
}
}
}
if ($x > 1) {
add_prime($x);
}
if ($g < 0) {
$g = $ANSWER++;
$FACTORS{$i} = $g;
$GROUP{$g} = [$i];
}
}
return scalar(keys %GROUP);
}
sub max {
my ($a, $b) = @_;
return ($a > $b) ? $a : $b;
}
sub min {
my ($a, $b) = @_;
return ($a < $b) ? $a : $b;
}
sub add_prime {
my $p = shift @_;
my $c = $#primes;
if ($p > $primes[$c-1]) {
push @primes, $p;
return;
}
for (my $i = 0; $i < $c; $i++) {
last if ($primes[$i] == $p);
if ($primes[$i] > $p) {
splice(@primes, $i, 1, ($primes[$i], $p));
last;
}
}
return;
}
1;
わたしはジェットコースターは大嫌いなのですが、それはひとまずおいておいて、とりあえず、並んでいる人数を配列にいれて愚直にジェットコースターに載せてはカウントするだけのプログラムを書いてみました。shift しては push するという、乱暴なコードを書いてみたのですが、サンプルは 1秒未満。small でも意外にも30秒もかかりませんでした。
#! /usr/bin/perl
use strict;
use bigint;
my $T = <>;
for (my $case = 1; $case <= $T; $case++) {
my ($R, $k, $N) = split /\s+/, <>;
my @g = split / /, <>;
my $sales = 0;
for (my $i = 0; $i < $R; $i++) {
my $ride = 0;
for (my $j = 0; $j < $N; $j++) {
my $x = shift @g;
if ($ride + $x > $k) {
unshift @g, $x;
last;
}
$ride += $x;
push @g, $x;
last if $k == $ride;
}
$sales += $ride;
}
printf "Case #%d: %d\n", $case, $sales;
}
1;
しかし、large の問題でテストしてみると当たり前に時間切れ。さすがに愚直に足し算つづけるのはダメで、どこなに周期性がないかと、と考えてました。最初に思いついたのは最初の行列の一番前の人が、また一番最初に乗車する状態になったところでループになること。これをとりあえず実装してみましたが、あまり早くなりません。問題をみて、手であきらかに周期性のある列を手で最適化することも考えてみましたが、問題数50問だと、それも時間的にみて厳しいと思い断念。もうちょっと考えて、乗車を始めた列の位置で乗れる人数が決まるので、それを全部ストアしておけば二回目から計算いらない、ということに気がついて実装してみました。small で3秒を切るところまではできましたが、その程度だと、やっぱり large 全体で小一時間ほどかかりタイムアップ。一時間かけて出した答えが合っていることまでは確認しましたが、もっといい方法があるんだろうな、と思いつつ、ここでギブアップしました。
#! /usr/bin/perl
use strict;
use bigint;
my $T = <>;
for (my $case = 1; $case <= $T; $case++) {
my ($R, $k, $N) = split /\s+/, <>;
my @g = split / /, <>;
my $sales = 0;
my $p = 0;
my %s;
my %c;
for (my $i = 0; $i < $R; $i++) {
my $ride = 0;
my $sp = $p;
my $spn = $p%$N;
if (defined($s{$spn})) {
$ride = $s{$spn};
$p += $c{$spn};
} else {
for (my $j = 0; $j < $N; $j++) {
my $x = shift @g;
if ($ride + $x > $k) {
unshift @g, $x;
last;
}
$p++;
$ride += $x;
push @g, $x;
last if $k == $ride;
}
}
if (($p%$N) == $spn) {
$sales += $ride * ($R-$i);
last;
}
$sales += $ride;
$s{$spn} = $ride;
$c{$spn} = $p - $sp;
if (($i<$R/2) and ($p % $N == 0)) {
my $loop_sales = $sales;
my $c = $i + 1;
$sales = $loop_sales * int($R/$c);
my $orig_R = $R;
$R = $R % $c;
$i = -1;
}
}
printf "Case #%d: %d\n", $case, $sales;
}
1;
全体を通して
どの問題にも共通しているのは、小さい数字では簡単な問題が、数字が指数関数的に大きくなったときは難問になり、そういう状態にも対応できるアルゴリズムを考えつかないと small まではなんとか解けても large ではまったく歯がたたないところです。現実でも良く直面することですね。とても楽しく取り組むことができました。
日本語で問題が読めるのも楽でした。でも解けないのは悔しいですね。3つの練習問題のうち、本番の制限時間である8分以内に large を解けるコードを書けたのは 1つだけ。プログラミングもさることながら、エレガントな方法を思いつけるかどうかが、ポイントですね。
しかし、われながら、最初の問題以外は乱暴なコードです。高速化、最適化をしているようで、どんどんコードが複雑になっていっています。これではいけないですね。修行します...。
Comments