Web、サーバ、ソフトウェア、バグ・脆弱性 などの情報を何人かで集まって書いていく IT/Web情報系ブログ

paizaの10万登録ありがとうキャンペーン問題 提出コードと解説(Perl:86, PHP:309)

投稿日:   最終更新日:2017/05/30  投稿者:xx2zz

paizaの10万登録ありがとうスペシャルWキャンペーンのPHPとPerlだけランキング上位に挑戦したので、提出したコードと簡単な解説を書く。
最後に提出したコードはPerlが86バイト、PHPが309バイト。
2017/05/20更新のランキングでは1位だが、最終的な順位は不明。

(vivibit_net_evilがランクインしているのは他の言語でPerlのコードを呼び出して遊んでいただけなので気にしないでください)

スポンサーリンク

最初に思いついたコードとアルゴリズム

最初に全テストケース0.01秒を出せたコードがこれ。

$M = int <>;
@s = <>;
%h = ();
@p = sort {$a<=>$b} grep(!$h{$_}++, map {int $_} splice @s, $M);
splice @p, 0, 1 if $p[0] == 0;

@t = ($p[0])x($p[$#p]+1);
my $l = 0;
for $p (@p) {
    @t[$l+1..$p+1] = ($p)x($p-$l);
    $l = $p;
}

for my $s (@s) {
    $r = 1e7;
    $c = sqrt($s);
    for $p (@p) {
        my $q = int($s/$p) + ($s%$p ? 1 : 0);
        next unless $t[$q];
        my $m = $p * $t[$q];
        $r = $m - $s if $m - $s < $r;
        last if $p > $c;
    }
    print $r,$/;
}

アルゴリズムとしては、
1. 箱の大きさを材料の長さで割って小数点以下を切り上げた数をインデックスとしたときに掛けて箱の大きさ以上になる最小の材料の長さが得られる配列を作る
2. 切り上げた値が1の配列の範囲にあり、インデックス*配列から得た値-箱の大きさ が$r(初期値:1000000)より小さければ$rを更新する
3. 箱の大きさの√より材料の長さが大きければループを抜けて、$rが答え

splice @p, 0, 1 if $p[0] == 0;は、テストケース1で空行かなにかがあって0が入るのを回避するため。

このコードを元に、無くてもテスト通る条件分岐を削ったり、ゴルフイディオムを使って適当に縮めていき、もうこのアルゴリズムではこれ以上厳しそうというところまでいったのが以下のコード。

map{push@t,($_)x($_-$#t)for@t||`sort -n`;$r=1e7;for$p(@t[1..1+sqrt]){$r=$"if($"=$t[$_/$p+0.99]*$p)<$r}print$r-$_,$/}map<>+0,1..<>

1の配列@tを、3の√箱の大きさまで達したときに終わらせるためとテストケース1で0が混じることを防ぐためにも使っている。
割って切り上げた数が@tの範囲を超えるケースがないのでその条件分岐も削っている。+0.99も本当はだめだけどテストケース通るし・・・。

letrangerさんの$%-=$-=$%-$_*$^を使うと124Bになるみたい。
$-なんて便利な変数あったの知らんかった・・・。

PHPも同じアルゴリズムで309Bまで縮んだが、実行時間が安定しないクソ仕様のせいでこれ以上バイト数削る気が失せたので309Bのコードすら手元に残っていない。
仕方ないので、312Bのコードを貼っておく。

<?php $i=fgets(STDIN)-0;while($i!==0){$s[]=fgets(STDIN)-0;--$i;}while($x=fgets(STDIN))$p[]=$x-0;sort($p,1);foreach($p as$q){$i=count($t)-1;while(++$i<=$q)$t[]=$q;}$y=count($t);foreach($s as$d){$r=[];$w=sqrt($d);foreach($p as$q){$i=$d/$q+0.99;if($q!==0&&$i<$y)$r[]=$t[$i]*$q-$d;if($q>$w)break;}echo min($r),'
';}

paizaは改行コードをLFで投げてやればちゃんと1バイト扱いになったはずだけど、めんどうなのでやっていない。

テストケースの不備

上のアルゴリズムではこれ以上縮む気がせず放置気味だったが、ふと気になってテストケースの箱や材料の最大値を調べてみた。

まず、こんなのを0.01sで通るコードにつけて箱の大きさの最大値が(10進数で)何桁あるか調べた。

@ss = sort {$b<=>$a} @s;
sleep log($ss[0])/log(10);


なんと、全ケース1000未満である。

ちなみに、材料の場合は以下。

ということは、材料を√1000ぐらいまでに絞って予め全組み合わせの積を配列なりに入れておくアルゴリズムで平均0.01sを出せそうな感じがする。
ちょっとこれはテストケースがぬるすぎるのではと思うが、129Bの時点で既に正攻法からかけ離れていたので、遠慮なく不備を突かせていただくことにした。

最終的に提出したPerlコード

そして、最終的に出来上がったPerlのコードがこれ。

map{/^..?$/&&map$t[$_*$&]++,@"for@"=<>;$n=0;$n++until$t[$_++];print$n,$/}map<>+0,1..<>

これといって見所のないコードになった。
正規表現で上限(99)による分岐と値のコピー($&)を同時にやっているとこぐらいだろうか。
個人的には最初のコード(アルゴリズム)のほうが好き。

2017-05-28 13:35 追記
このコードをPHPに移植したらクソ遅くなってしまったので、PHPのコードは最初のアルゴリズムのままになっている。

2017-05-30 04:38 追記
letrangerさんにより、更に3バイト縮み83Bになった!

map{/^..?$/?map$t[$_*$&]++,@":<>for@"=<>;$.++until$t[$_++];print$.,$/}map<>+0,1..<>

感想

1週間ぐらい暇を潰せてよかった。
あと、letrangerさんのコードを見るとずるなしで121Bだったのでなんか申し訳ない気持ち。(実質負けてる)

- PHP, Perl , , ,

Comment

  1. nk_evil より:

    コードゴルフに情けは無用ってGolfScriptが教えてくれた

  2. nk_evil より:

    最初のアルゴリズムは
    push@t,($_)x($_-$#t)for@t||`sort -n`;
    ここが最高に機能美

  3. letranger より:

    ハジメマシテ。$n=0;の部分がどうにかならないかなーと考えてみたら3b縮みました。
    map{/^..?$/?map$t[$_*$&]++,@”:for@”=;$.++until$t[$_++];print$.,$/}map+0,1..

    標準入力を最後まで読み込んだ後、更に読み込もうとすると$.(最後にアクセスされたファイルハンドルの現在の行番号)に0が代入されるのを利用してます。
    といっても元の86b解でも既に2ループ目以降は for@”= で$.に0が代入されるようになっているので、1ループ目のテーブル構築中にを通るようにしてるだけです。&&を三項演算子に書き換えたことで暗号成分増してますね……
    ちなみに3桁の材料がない場合1ループ目に誤った回答を吐くので、なんと提出前チェックに通りません。

    Perlで一気に二桁まで縮められたのを見た時は二度目してしまいました。ゴルフ奥が深すぎる……。

  4. letranger より:

    っとと、コードの一部がタグとして認識されてる?
    これで通じるでしょうか。
    map{/^..?$/?map$t[$_*$&]++,@”:<>for@”=<>;$.++until$t[$_++];print$.,$/}map<>+0,1..<>

    • xx2zz より:

      letrangerさん、コメントありがとうございます。

      これはすごい!
      $-を使ったテクニックにも驚かされましたが、この部分も短くしてしまうとは・・・。

      最初のコードの$r=$”if($”=$t[$_/$p+0.99]*$p)<$rの部分もそうでしたが、 $n=0;もゴルフ的に美しくないのでどうにかしたいと思っていろいろ試して、 結局よい方法を見つけられずに諦めていた部分でした。 $.の存在自体は知っていましたが、$.を使えないかという発想自体なく、試してもいませんでした。 たしかにこれだと提出前チェックは通らないですね。おもしろい。 記事に追記させていただきました。

Message

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事