「paizaの10万登録ありがとうキャンペーン問題」での自分の提出コード(perl:146, C++:192)

paizaの10万登録ありがとうスペシャルWキャンペーン
で自分が使用したC++&perlのコードとその解説を載せる

はじめに

この記事は以下の記事を読みながら書かれているので、
まず、以下の記事を読んでほしい。
paizaの10万登録ありがとうキャンペーン問題で使用したアルゴリズムと提出コード

大まかな解法

C++, perlかかわらず、大まかには

1. 一度箱の大きさのパターンを全部計算・保存
2. 配列的なものを用いて Memo[x*y]=true 的な処理でメモ
3. 場合によっては何らかの方法速度向上のためのハックをする
4. メモから、ある品物の数以上の面積パターンを線形探索して、出力

という方法を用いた。

回答コード

C++での回答

以下のようなコードを提出した。192文字だったらしい

#include<iostream>
int*p,M['}}'],*L,*C=M-1,R['}}'],A;
int main(){
    for(;std::cin>>*++C;)
        for(L=M+2+*M,p=C;p>L;A<9999&&R[A]++)A=*C**p--;
    for(p=M+2;p<L;)for(A=*p;!R[A]||!printf("%d\n",A-*p++);++A);
}

###大まかな処理
入力を読み込みながら箱の面積のパターンを計算して、R[計算して求めた面積] を0以外の値に変更。
最後に　各品物の数からRを探索して0以外になったら出力

###解説

• M['}}'] なんか大きい配列。4byteで9999より大きな配列が作れる。
• for(;std::cin>>*++C;) 入力を終わりまで読み込んでいく。
• L=M+2+*M 長さに関する情報の始まりをメモる。 *Mは問題文のMのこと
• p=C;p>L;
• 今まで読み込んだ長さの部分を読み込む。後ろから前に読み込んでいくことになる。
• C>Lが満たすようになるまでは、つまり入力で品物の数情報を読み込んでる間はここでのメイン処理を行わない
• A<9999&&R[A]++
• 掛け算でヒットした部分のフラグを（インクリメントして）0以外にする。
• R[A]=1じゃないのは演算子の優先速度的な関係。
• A<9999で大きすぎる値をはじいてるのはこれ入れるとなんか処理が早くなるから。キャッシュとか効いてるんじゃないですかね(適当)。9999ではじいていい理由は……なんか通ったから。通るんだからしゃーない
• for(A=*p;!R[A]||!printf(
  • 各品物の値*pからスタートしてR[A] !=0になるまでAをインクリメント
  • そして出力

perlでの回答

以下のようなコードを提出した。146文字だったらしい。

$M=<>+0;$R=$0x999;@I=<>;
@L=sort{$a<=>$b}@I[$M..$#I];
for$i(@L){$t=$i*$_,$t>6x4?last:substr$R,$t,1,1for@L}
print index($R,1,$_)-$_,"\n"for@I[0..$M-1]

###大まかな処理
できるだけ大きな文字列を確保。面積の計算結果のメモ空間とする
入力を読み込み、各長さ*長さに対し 計算して求めた面積 文字目を1に上書き
index関数で文字れるの何文字目に1があるかを求め、差をとり出力
###解説

• <>+0 "M N"を数値に変換してMを取り出す
• $R=$0x999 計算結果のメモ用にできるだけ大きな文字列を作る。$0は(たぶん)"Main.pl"で7文字。x999なので7000文字くらい
• $t>6x4 C++と大体同様に、なんかこれで計算打ち切ってもなんかうまくいくので打ち切って速度を稼ぐ
• index($R,1,$_)-$_, $_文字目以降の1=$_以上の最小の存在する面積を取得し、 $_と差をとって出力する

#反省点

C++&perl共通

• 「まず面積を全部求め」という処理を疑えなかったこと
  • 「毎回探索したらO(M*N^2)になって遅くなるに決まってるだろ！」と考えていた

C++

#perl
http://qiita.com/letranger/items/c8d023bd6f781dd3ba4c#perl を見ながら

• perlに対する知識が足りない
  • $/を改行記号として見れなかった
  • 0..<>とかが思いつけなかった
  • シェルコマンドを使う方法は考えはしたが、なぜかtail -n +$M *di*|sort -nって書いてあり、遅いと書かれていた

おまけ

一番最初に書いたコード

とりあえず問題を解くために書いたコード in c++
存在する面積のリストを作ってlower_boundで頑張る

#include<algorithm>
#include<iostream>

int main(){
    // 入力
    int M,N;
    std::cin>>M>>N;
    std::vector<int> nums(M),lens(N);
    for(auto&x:nums)std::cin>>x;
    for(auto&x:lens)std::cin>>x;

    // 全パターン計算してメモ化
    std::vector<int> areas;
    for(auto&x:lens)
        for(auto&y:lens)
            areas.push_back(x*y);

    // 各品物の数に対し探索して出力
    std::sort(areas.begin(),areas.end());   //lowerboundのためにsort
    for(auto&x:nums)
        std::cout<< *std::lower_bound(areas.begin(),areas.end(),x)-x<<"\n";
}