【Perl】paizaオンラインハッカソンVol.1にてきとうに挑戦した結果
-- 2013/12/15 15:43
paizaオンラインハッカソンVol.1「新人女子プログラマの書いたコードを直すだけの簡単なお仕事です!」ってのがあったのでてきとうにPerlをかいてみた。
大体最初にぱっと思いつく感じのアルゴリズムの組み合わせ数を減らす程度の最適化を施したかんじのやつを提出。
結果、ケース1で0.5秒くらい、その他はタイムアップという結果。
まあしょうがないね。
-- 追記
その後深く考えずに以下のように入力を一括で読むようにいじくったり、はてまた全部ourにしてみたりしたけどタイムは全く変わらなかったので、アルゴリズムの限界がこのタイムらしい。
大体最初にぱっと思いつく感じのアルゴリズムの組み合わせ数を減らす程度の最適化を施したかんじのやつを提出。
my @price_for_item;
my @price_in_period;
my ($item_num, $period_num) = map {chomp;$_} split / /, <STDIN>;
for my $i (0 .. $item_num - 1){
push @price_for_item, map {chomp;$_} scalar <STDIN>;
}
@price_for_item = sort {$a <=> $b} @price_for_item;
for my $p (0 .. $period_num - 1){
push @price_in_period, map {chomp;$_} scalar <STDIN>;
}
my $str = '';
for my $p (0 .. $#price_in_period){
my $max_price = $price_in_period[$p];
my @price_for_item_use;
my $is_last;
for my $i (0 .. $#price_for_item){
if($price_for_item[$i] > $max_price){
@price_for_item_use = @price_for_item[0 .. $i - 1];
$is_last = 1;
last;
}
}
if(! $is_last){
@price_for_item_use = @price_for_item;
}
if(! @price_for_item_use){
$str .= "0\n";
next;
}
my $max_price_can = 0;
my $minimum_index = 0;
for my $i (reverse 0 .. $#price_for_item_use){
my $base = $price_for_item_use[$i];
my $max_price_append = $max_price - $base;
my $max_price_can_append = $max_price_can - $base;
for my $j (grep {$i != $_} $minimum_index .. $#price_for_item_use){
my $append = $price_for_item_use[$j];
if($max_price_can_append > $append){
$minimum_index = $j;
next;
}
if($max_price_append < $append){last}
$max_price_can = $base + $append;
}
}
$str .= $max_price_can . "\n";
}
print $str;
結果、ケース1で0.5秒くらい、その他はタイムアップという結果。
まあしょうがないね。
-- 追記
その後深く考えずに以下のように入力を一括で読むようにいじくったり、はてまた全部ourにしてみたりしたけどタイムは全く変わらなかったので、アルゴリズムの限界がこのタイムらしい。
our @price_for_item;
our @price_in_period;
local $/ = undef;
our $stdin = <STDIN>;
$stdin =~ s/^(\d+) (\d+)\n//;
our ($item_num, $period_num) = ($1, $2);
our @prices = $stdin =~ m/(\d+)[\r\n]*/g;
@price_in_period = @prices[$item_num .. $item_num + $period_num - 1];
@price_for_item = sort {$a <=> $b} @prices[0 .. $item_num - 1];
our $str = '';
for our $p (0 .. $#price_in_period){
our $max_price = $price_in_period[$p];
our @price_for_item_use = ();
our $is_last = 0;
for our $i (0 .. $#price_for_item){
if($price_for_item[$i] > $max_price){
@price_for_item_use = @price_for_item[0 .. $i - 1];
$is_last = 1;
last;
}
}
if(! $is_last){
@price_for_item_use = @price_for_item;
}
if(! @price_for_item_use){
$str .= "0\n";
next;
}
our $max_price_can = 0;
our $minimum_index = 0;
for our $i (reverse 0 .. $#price_for_item_use){
our $base = $price_for_item_use[$i];
our $max_price_append = $max_price - $base;
our $max_price_can_append = $max_price_can - $base;
for our $j (grep {$i != $_} $minimum_index .. $#price_for_item_use){
our $append = $price_for_item_use[$j];
if($max_price_can_append > $append){
$minimum_index = $j;
next;
}
if($max_price_append < $append){last}
$max_price_can = $base + $append;
}
}
$str .= $max_price_can . "\n";
}
print $str;
- 関連記事
-
-
Cで改行まで任意文字数の読み込みをする+改行削除 2014/11/08
-
プログラミングとブログ 2014/06/29
-
【Perl】paizaオンラインハッカソンVol.1にてきとうに挑戦した結果 2013/12/15
-
YAPC::Asia Tokyo 2013 終了 なので個人的まとめ 2013/09/22
-
YAPC::Asia Tokyo 2013 本番1日目 2013/09/21
-

コメント