No Such Blog or Diary

Project Eulerの問題を頭からいくらかといてみた．基本 Haskell 使ってるけど時々スタックがオーバーフローしたり遅かったりするので C++ を織り交ぜる．多倍長の演算とかはHaskelがとても楽でいい．まだまだ最初のほうなのであまり面白い問題ないけど順番にやっていこう．

目が覚めたので久々に参加．でも250点問題を即効で解いただけ．500点問題は計算量の見積もりが面倒になって寝た．

250点問題：素因数分解に含まれる素数が与えられた数以下であるような数を数え上げる．素数テーブルを持って割っていくのみ．６分で解いたらしい．

500点問題：グラフを何回被覆できるかという問題だけど…　被服のための基底を生成したあたりで計算量の見積もりが面倒になってやめた．どうやらメモ化したバックトラックでよかったらしい．

1000点問題：指定したハミング距離をもつ指定桁の１６進数のうち小さいほうから指定番目を返せと．エラー訂正のほうの理論使って簡単に出来ると面白いなぁ．

PCで受信しているメールを携帯でも受信したい．ただしパケット代が高いので，スパムは転送しない，添付ファイルはファイル名だけわかればいい，本文もある程度の長さで切れてしまえ，という仕様にしたい．

今回とった手段は，ひとまず Gmail に転送してスパムを高確率で殺す，そいつをレンタルサーバの転送専用メールアカウントに転送する，さらにそのアカウントで添付ファイルや本文の短縮の加工を行い携帯側へ転送する，とかいう摩訶不思議なリレー．

で，調べてみたらレンタルサーバのメール振り分けは maildrop とかいうのでやっているらしく，転送設定は通常の .forward ではなく.mailfilter とかいうものを書くらしい．つーことで，.mailfilter を転送用メールアカウントのディレクトリに置いて，中身を次のように指定．パーミッションを 600 とかにしておかないと動いてくれないので困る．

cc "| ../../mail_forwarding.pl"

そんで，次の転送用のプログラム mail_forwarding.pl を適当に配置．いわゆる .eml が添付されてきたときには再帰的に展開して本文にくっつけてしまう．他はテキスト以外の添付は切り捨て．

#!/usr/bin/perl
 
use MIME::Parser;
use MIME::Words qw(:all);
use Jcode;
#use encoding "7bit-jis";
 
$forward_addr = 'hugahoge_tekitou@docomo.ne.jp';
$sendmail = '/usr/sbin/sendmail';
$length_limit = 512;
 
 
sub extract_body {
    my ($entity) = @_;
    my $body = $entity->bodyhandle;
    my $head = $entity->head;
    my $type = $head->mime_type();
    my $str = "";
    my $nm = $head->recommended_filename;
 
    #print "type = $type\n";
    if( $type eq "multipart/mixed") {
    #if($entity->is_multipart()) {
            my $count = $entity->parts;
            for(my $i = 0; $i < $count; $i++){
                    my ($st, $n) = extract_body($entity->parts($i));
                    if($n ne "") {
                if($nm ne "") { $nm .= ", "; }
                           $nm .= $n;
            }
                    if($st ne "") { 
                if($str ne "") { $str .= "===\n"; }
                $str .= $st;
             }
            }
    } elsif( $type eq "text/plain") {
        $str = $body->as_string;
    } elsif( $type eq "text/html") {
        $str = $body->as_string;
    } elsif( $type eq "message/rfc822") {
        # should be recursively decoded
        my $io = $body->open("r");
           my $et = $parser->parse($io);
        my ($st, $n) = extract_body($et);   
        $str = $st;
                   if($n ne "") {
            if($nm ne "") { $nm .= ", "; }
                       $nm .= $n;
        }
    } else {
    }    
    return ($str, $nm);
}
 
sub extract {
    my ($head, $attr) = @_;
    my $dat = $head->get($attr);
    my @decs = decode_mimewords($dat);
    my $ret = "";
    foreach $data (@decs){
        my ($target,$charset) = @$data;
        if($charset ne "") {
            Jcode::convert(\$target, $charset, 'jis');
        }
        $target =~ s/\n//g;
        $ret .= $target
    }
    return $ret;
}
 
sub stlip_bracket {
    my ($dat) = @_;
    $dat =~ s/(^|,)[^>]*<([^<>]*)>/\1\2/g;
    return $dat;
}
 
$parser = new MIME::Parser;
$parser->output_to_core(1);
$parser->extract_nested_messages(0); 
 
$entity = $parser->parse(\*STDIN) or die "parse failed\n";
$head = $entity->head;
$from = &extract($head, 'From');
$to   = &extract($head, 'To');
$cc   = &extract($head, 'CC');
$subj = &extract($head, 'Subject');
 
$from = stlip_bracket($from);
$to = stlip_bracket($to);
$cc = stlip_bracket($cc);
 
$body = "";
($body, $files) = extract_body($entity);    
 
$mes = "";
$mes .= "From: $from\n";
$mes .= "To: $to\n";
if($cc ne "")    { $mes .= "CC: $cc\n"; }
$mes .= "Subj: $subj\n";
if($files ne "") { $mes .= "File: $files\n"; }
$mes .= "$body";
 
if(length $body > $length_limit) {
    $body = substr($body, 0, $length_limit);
}
 
$modbody = $body.($to ne "" ? "\nTo: ".$to : "").($cc ne "" ? "\nCC: ".$cc : "").($files ne "" ? "\nFs: ".$files : "");
 
#$esub = encode_mimeword($subj);
$top = MIME::Entity->build(Type    =>"text/plain",
                           From    => $from, 
                           To      => $forward_addr,
               Data    => $modbody,
                           Subject => $subj,
               Encoding => "7bit",
               Charset => "ISO-2022-JP",
                          # Subject => $esub);
              # CC      => $cc,
              # Encoding =>"quoted-printable",
            );
 
#print $mes;
$top->print(\*STDOUT);
#exit(0);
 
open(MAIL, "| $sendmail -t") or die "seinding a mail failed";
$top->print(\*MAIL);
print MAIL "\n\n.\n";
 
#$top->head->replace('To', 'debug_output@hugahoge_tekitou.com');
#open(MAILLOG, "| $sendmail -t") or die "seinding a mail failed";
#$top->print(\*MAILLOG);
#print MAILLOG "\n\n.\n";
 
 
 

とりあえず動いてるけど HTML メールのときにタグをなくしてテキスト化したいなぁ．そして perl で書いたけど別の言語で書いたほうが楽だったかなぁ．perl なんて久々に使ったから perl として普通のプログラムなのか怪しいし．

久々にやった．寝ぼけていた．500点問題の状態の取り方がおかしかった…

250点問題：単語の列をアンダースコア区切りできれいに指定幅に並べろと．端数分のアンダースコアを次の単語が小文字で始まるときに挿入するだけ．余り過ぎないように注意．

500点問題：部屋の回転つき迷路．状態空間を，現在位置と各行・各列の反転状態とにとれば，最大でも80万状態くらいしかない．後は普通に最短路を探索すりゃ終わる．でも状態のとり方を間違えて各行各列でなく全部を反転してた…．終了ちょっと前に間違いに気づいたけど直す時間なかった．

1000点問題：解の存在に必要な条件は最小公倍数だろうけど…　そこから先が面倒そう．よくわかりません．

問題読み間違えて 500点落とした．1000点は間に合わなかった．

250点：右方向にしか動けないナイトをチェス盤上でもっとも長く動かせと．ただし，四手以上動かす場合には四方向の動きを少なくとも一回ずつすべて使用すること．四手未満ならどんな組み合わせでもいい．盤面の高さが３以上で横幅が７以上なら　横幅－２　回動けてこれが最大．盤面が条件を満たさないなら面倒なのでDP．

500点：問題を読み間違えたけど作成するデッキ数の二分探索でおわる．指定数のデッキが作れるかどうかは，各カードに対してデッキ数に満たない分だけジョーカーを追加して，ジョーカーの使用枚数がデッキ数以下かどうかをチェックすればわかる．ショーカーの数がデッキ数以下ならジョーカーが重ならないので作成可能．

1000点：辺の小さいほうから順に，ひし形の短径の最大値と最小値を計算していくだけ．

もう少し頭使えよと言いたくなる結果．まあいいだろうとか考えて放っておいた部分が響いて正解なしに…

250点問題： price を最大までインクリメントしながらチェックしてたら時間オーバーだった．五千万位のループは大丈夫かと思ったけどだめみたい．馬鹿なことせずに与えられた配列内の値だけチェックすれば通っていたものを（誰かの max までは単調増加なので）．

500点問題：図形っぽいからパスした．直方体を２の冪のサイズの立方体で埋める問題．正解を見てわかったけど，２の冪しかないのでな 1x1 で埋めなければならない部分を埋めて再帰的に1/2サイズにした問題を解けばよかったらしい．

1000点問題：結局のところ行列式に (-1)^(N-1) を掛けたものが答えになる．理由は以下のとおり．まず，行列に吐き出し操作をしても答えは変わらない（自明）．そして，吐き出し後には，積が非ゼロになるドミノの選択は全てが対角要素である場合しかなく，その積は行列式に等しい．同時に，ドミノの連結グループ数は行列の大きさである N に等くなっているので，答えは行列式に(-1)^(N-1) を掛けたものに等しい（偶数なら符号反転）．ということで，行列式を求めればおわる．幸いなことに modulo 121547 の答えでよく 121547 が素数で有限体上の計算になるので普通のLU分解とかが使える．

以上を踏まえ，有限体の逆元を求めるための拡張ユークリッドの互除法を実装し，演算を有限体の演算に置換したピボットつき LU 分解を実装して提出したのだが…　正規化のためのルーチンを次のように書いていたため TLE 喰らった．

    int norm(long a) {
        while(a < 0) a+=P;
        return (int)(a % P);
    }

掛け算してんだから数万回ループすることもあるよなぁ．もう少し進化して下のように書いたら普通に通ったし．

    int norm(long a) {
        if(a<0) a -= (a/P-1)*P;
        return (int)(a % P);
    }

あー，もったいねぇ．解けてたのに…