2007年09月

昔書いたコードを書きなおしてるけど結構時間食うなぁ．２４時間くらい続けてるけどまだ半分か．これから先の部分に山場があることを考えると頭が痛い…

人が少しコンビニに行って帰ってくる間に来ていたとは．もう遅いので受け取りは明日だな．

このモデルから W も 965 になったようなので買い替え確定．ついでにメモリも SO-DIMM 対応なので増設しやすい．でも，何故か W7B だけ発売日が一カ月遅れの 11月半ば…　とりあえずどこで買うか悩むとしよう．生協で安く買えるといいなぁ．

またとちった．

250点問題：BigInteger で舜殺可能．

500点問題：よくあるDPだけど微妙に形を間違え…　さらに事前のソート処理が必要なのをあとで思い出したが挿入位置を間違え…　なんてやってたら時間無くなった．

1000点問題：DAGから枝を抜いてけばいいのだけどどうやって抜いていけばよいのやら？

研究室に人が来ない．昼すぎても来ない．たまたまなのかいつもどおりなのか？

どうやら g++ は varargs な関数を展開できないらしい．

#include <iostream>
 
struct h {};
struct k : h {};
 
namespace g {
  inline bool f(...) { return false; }
  inline bool f(h* ) { return true;  }
}
namespace v {
  template <typename A>
  inline bool f(A)   { return false; }
  inline bool f(h* ) { return true;  }
}
 
int main(int argc, char *argv[])
{
  h *ph; k *pk; int *pi;
  std::cout << g::f(pi) << std::endl;
  std::cout << g::f(ph) << std::endl;
  std::cout << g::f(pk) << std::endl;
  std::cout << v::f(pi) << std::endl;
  std::cout << v::f(ph) << std::endl;
  std::cout << v::f(pk) << std::endl;
}

g::f(pi) は inline bool f(int* ) なので展開される．g::f(h()) は inline bool f(...) なので展開されない．他は全部展開．ついでに，(...) を使わずに単純にテンプレート変数を一つ用意すればいいかなと思ったけど(...)とテンプレートを用いた場合とでオーバーロードの解決優先度が違うのでだめらしい．

古いソースだとbool boost::detail::function::has_empty_targetはvarargsを使ってないのになぜ最近の実装では varargs を使うようになったのだろう？

インライン展開失敗するなぁ．

#include <iostream>
#include <boost/function.hpp>
 
struct F_t {
  double operator()(const double & x) const { return 1.5 * x; }
} F;
 
inline double G(const double & x) { return 1.5 * x; }
 
int main(int argc, char *argv[])
{
  boost::function <double(const double &)> f = F;
  boost::function <double(const double &)> g = G;
  std::cout << f(2.0) << std::endl;
  std::cout << g(2.0) << std::endl;
}

ただの関数 g の場合はインライン展開されるけど関数オブジェクト f のときは bool boost::detail::function::has_empty_target(...) が展開できないといわれる．さてどうしたものか？

とりあえず霊夢の封印装備以外はすべてノーマルをクリア．魔理沙の魔法使い装備でオプション固定解除のタイムラグが大きくなってて戸惑った．オプション固定したまま素早く動けるようになったのはありがたいのだけど．次はExtraにでもチャレンジしてみやう．

昨日から委託販売されてた気がするので風神録を買ってくる．ついでに GUNDEMONIUM RECOLLECTION も購入．とりあえずノーマルを頑張るか．

エスケープの仕方を変えてみたら小さくなった．スコア 17 ．

                ;
               ;;;
              s|^|\
             DDDh;s\
            /[BnD]//\
           g;y/bcde/B\
          BBnDE/CDDx;s\
         /$/BB/mg;s/^/;\
        Bn;;;BnsE^E/CD:;\
       s/^[^DBn]*BnB(DB+B\
      )/DB1B0/m;tCs/.$/E/p\
     ;x;s/[`-Bx66]/BUB0/gDD\
    DD;                     |
   h;s/[\n ]//g;y/BCDE/\\\n |/
  x;s/$/\\/mg;s/^/;\n;;;\ns|^|/
 :;s/^[^ \n]*\n\( \+\)/ \1\0/m;t
s/.$/|/p;x;s/[`-\x66]/\U\0/g    ;

ソース：pyramid-quine.17.sed

真中に空白があるのでまだ小さくなりそう．

無駄を省いて小さくしてみた．スコア 19 ．

                  ;
                 ;;;
                s|^|\
               QQh;s/\
              $/YY/mg;\
             s/^/;Yn;;;\
            YnsP^P/NQSs/\
           Y([^Yn]*YnY)Y(\
          SY+Y)/SY2Y1Y2/;N\
         Qs//SY2Y1Y2/;s//SY\
        2Y1Y2/;s/.$/P/p;NSx;\
       s/YnYPS//g;s/Yx59/YY/g\
      ;s/Yx53/S/gNs/Yx4E/Yn/g;\
     s/Yx50/P/g;s/Yx51/Q/gQ;   |
    h;s/$/\\/mg;s/^/;\n;;;\ns|^|/
   s/\([^\n]*\n\)\( \+\)/ \2\1\2/;
  s// \2\1\2/;s// \2\1\2/;s/.$/|/p;
 x;s/\n\| //g;s/\x59/\\/g;s/\x53/ /g
s/\x4E/\n/g;s/\x50/|/g;s/\x51/  /g  ;

ソース：pyramid-quine.19.sed　動かすには echo で改行だけ入れてやる必要あり．

 echo | sed -f pyramid-quine.19.sed | diff - pyramid-quine.19.sed

その他ソース：loose-expand.sed，cloose-omp.sed，reformatter.sed

合宿のときに時間がなくて作れなかったのを思い出したので作ってみた．かなりの無駄をしているのでスコアは 38 とのこと．

                                     ;
                                    ;;;
                                   s|^|\
                                  SSSSSS\
                                 SSs/%yn%\
                                y%pS//g;h;\
                               s/^/S/;x;s/^\
                              /%P%yn/;s/^%P/\
                             %a%a%a%a%a%a/;:1\
                            ;s/%P*/%a%yn%a/;:N\
                           SSSSSSS/^%P/{s///;x;\
                          /S%y(.%y)/!{G;s/%y(.*%\
                         y)%yn%P.*/%y1/;s/%P%y%pS\
                        %yn/S/g;s/$/%p/NSSSSSSb2};\
                       s//%y1S/;x;b};s/^%yn/%P%P/;x\
                      ;s/S/%y%y%ynS/;/S$/{s/..S$/%p/\
                     ;b2};x;b1NSSSSS:2;s/^/;%yn;;;%yn\
                    s%p^%p%y%y%yn/;;:3;/%y(.*%y)%yn/!b\
                   4;s//%y1%P/;s/^/S/mg;b3;:4NSSSSs/%P/\
                  %yn/g;s/^/SSSSSSSSS/mgp;x;s/%P*%yn%P*%\
                 yn//;s/$/%P/;s/%P$/%a%a%a%a%a/;:BSSS;NSS\
                S/^%P%y{5%y}/{s///;bA};/^%%P%y(.*%y)/{s//%\
               y1%P/;bB};/^%%s%y(.*%y)/{s//%y1%s/;bB}SS;NSS\
              /^%s%y(.*%y)/{s//%y1S/;bB};/^%%%N%y(.*%y)/{s//\
             %y1%N/;bB};/^%N%y(.*%y)/{s//%y1%yn/;bB};NS/^%%p%\
            y(.*%y)/{s//%y1%p/;bB};/^%%y%y(.*%y)/{s//%y1%y%y/;\
           bB};/^%%%%%y(.*%y)/{s//%y1%%/;bB};N/^%%a%y(.*%y)/{s/\
          /%y1%y%a/;bB};/^%%i%y(.*%y)/{s//%y1/;bB};s/%y(.%y)%y(.\
         *%y)/%y2%y1/;tB;:AS;                                    |
        s/\n\| //g;h;s/^/ /;x;s/^/#\n/;s/^#/&&&&&&/;:1;s/#*/&\n&/;:
       /^#/{s///;x;/ \(.\)/!{G;s/\(.*\)\n#.*/\1/;s/#\| \n/ /g;s/$/|/
      b2};s//\1 /;x;b};s/^\n/##/;x;s/ /\\\n /;/ $/{s/.. $/|/;b2};x;b1
     :2;s/^/;\n;;;\ns|^|\\\n/;;:3;/\(.*\)\n/!b4;s//\1#/;s/^/ /mg;b3;:4
    s/#/\n/g;s/^/         /mgp;x;s/#*\n#*\n//;s/$/#/;s/#$/&&&&&/;:B   ;
   /^#\{5\}/{s///;bA};/^%P\(.*\)/{s//\1#/;bB};/^%s\(.*\)/{s//\1S/;bB}  ;
  /^S\(.*\)/{s//\1 /;bB};/^%N\(.*\)/{s//\1N/;bB};/^N\(.*\)/{s//\1\n/;bB};
 /^%p\(.*\)/{s//\1|/;bB};/^%y\(.*\)/{s//\1\\/;bB};/^%%\(.*\)/{s//\1%/;bB};
/^%a\(.*\)/{s//\1\&/;bB};/^%i\(.*\)/{s//\1/;bB};s/\(.\)\(.*\)/\2\1/;tB;:A ;

ソース：pyramid-quine.sed

動かすには echo で改行だけ入れてやる必要あり．

 echo | sed -f pyramid-quine.sed | diff - pyramid-quine.sed

作成メモ：　任意の文字列を改行・空白無し文字列に変換・復元するプログラムを書く．ついでに，s コマンドで特別な意味を持つ記号もエスケープしておく．ソース：expand.sed，comp.sed

次いで，エスケープされた文字列を三角に表示するプログラムを書く．ソース：formatter.sed

あとは，復元するプログラムと三角に表示するプログラムをくっつけたプログラムを作り，さらにそいつを変換して三角形に成形した文字列をそのプログラムの頭にくっつける．最後に形を微調整して出来上がり．

結構ナイーブに作ったのでいろいろと無駄が多いきがする．少なくとも，quine プログラム中では文字列が最初から三角形の形をしているので，文字列フォーマット部分を単純化することができるはず．あと，特定の文字を使わないとかいう縛りにしておくと復元部分が単純化できるはず．

command="COMMANDS" ssh-dss KEYSTRING...== COMMENT

みたいに各キーで認証したときに実行すべきコマンドを書いておけるのね．他にも no-port-forwarding をつけとくとフォワードさせないとかno-agent-forwarding でエージェント転送しないとか．ここら辺のオプションをつけられるってのをいまさらながら初めて知った．

とりあえず存在を忘れてたので飯を食べたり洗濯したりしながらの参加．でも久々にスコアを稼いだ気がする…　でも500点問題で無駄に凝ったことしようとして時間食い過ぎたのはよくなかった．おかげで1000点問題を解こうとする時間がなかった．やれやれ．

250点問題：普通にDPで 1000x50 くらいの表を埋めるだけ．

500点問題：総当たりで2^10試せば終わる．あとは適当に辞書順でソートとか．

1000点問題：見てない．

http://java.sun.com/docs/books/tutorial/uiswing/dnd/intro.html

をざっと読んだが以下のようになるのだろうか？

TransferHandler とやらがD&Dやクリップボードへのコピー時のデータの受け渡しを受け持つ．データは，Transferable というインターフェースを継承したものに包まれる．具体的なデータ形式の変換はTransferable にデータ型を表す DataFlavor を指定し変換させる．

つーことで，ここらの３つを実装しつつ，ドラッグの開始を担当するリスナを作っておけばよいと．リスナは単に TransferHandler#exportAsDrag(JComponent c, InputEvent e, int action) を呼べばいいらしい．

3/4日くらい寝ていたような…

Swing コンポーネントにはデフォルトの D&D の動作が実装されている．が，JTree に関しては用意されている機能が少なすぎる…　というより，JTreeのアイテムをドラッグ(コピー)することはできるけど，構造を変化させるドロップ（ペースト）動作が実装されていない．ついでに，そのコピーもサブツリーのコピーではなくノード一個のみな気がする．そのため，木の構造を変えるようなD&D操作は自前で実装しないとならんみたい．めんどくさ．

昨日あたりから風邪をひいたらしく鼻がおかしい…　つーかビタミン不足だらうか？

あが～　　零点…

300点問題：r^2 の約数を素でループまわして時間がない．r の約数を求めて掛け合わせたものが r^2 の約数だっちゅうに．

500点問題：アルゴリズム間違ってない．速度も本来なら問題ない．だが，デバッグ出力の行を消し忘れてて時間オーバーでシステムテストでけられた．いやぁ，Java の String って遅いねぇ．ちくしょー

1000点問題：トポロジカルソート＋αでできるかなと思ったけどだめらしい．よく考えると結構面倒だよなぁ，辞書順で最小って．

まあ，あほな結果だなぁ．

新宿のミラノ１で夕方に見たのだけどまだ結構な人数が見に来るのね．んで，ぶっちゃけ赤かったなぁと．赤い海と使徒がやられたときの血の雨．ま，大きく変わった部分ではあるのだけど前半はその程度の変化しかない？　ヤシマ作戦からは結構別物になってきてたなぁ．ラミエル変形してるし．それでもストーリーの変化はないのでここまでは焼きなおしかと．最後のカヲルと予告は全く別物になっていたので次の破の公開が待ち遠しい．

出張のための費用を自前のクレジットカードで払っていたのでその清算処理のためにカードの明細を提出する必要があった．で，自分のカードは明細をWeb上で確認するようにしている．ということで Web上で手に入る情報を印刷して持っていったのだが…　Web ページに table でべた書きなものだから印刷結果が汚い．せめて PDF を生成するようにシステムを変えられないものかねぇ．UFJカードの方は PDF が取れるのに三井住友のは無理みたい．お客様のご意見とかで送ってみようかな？

久々にリアルの本屋で重たい本を買ってみた．とりあえず気になっていたものを３つ．

　ゲームで極める シェルスクリプトスーパーテクニック

　デバッガによるx86プログラム解析入門―コンピュータとプログラムの仕組みを覗く

　Short Coding ~職人達の技法~

もう一冊買おうと思っていたものがあったのだけど思い出せなかったので無視．で，後になって気付いたのは生協で買えば一割引きだったこと…　昼飯代くらいにはなっていたのに残念．

今日は研究室のある建物が停電になる日だった．今日は休日なので入口でゲートカードによる認証が必要だった．カードリーダは電気がないと唯の箱だった．

結論：私は今日研究室に入れなかった．

最終的には作業中のおっちゃんの後についてって中に入れたけど停電は痛い．ところで研究室の冷蔵庫の中身はどうなったのでしょう？

半日以上寝てたらしい．とりあえず出張中の出費を整理してみた．会議の参加費と飛行機とTGVは抜きで一人頭１２万くらいだった．１０泊だったのでこんなもんといえばこんなもんではあるけれど．基本的に外食なので食費がかさんだきもする．というよりユーロたけーよ．円がんばれ．

朝早くリオンからパリに移動．着いたのはパリにあるリオン駅．わかりやすいような気もするけど紛らわしい名前の付け方な気がする．

んで，飛行機は夜なので昼過ぎからルーヴル美術館を見学．サモトラケのニケ，ミロのヴィーナス，モナリザあたりの実物がみられた．モナリザは想像より小さかったなぁという印象．そしてミロのヴィーナスは見る方向で大分印象が違うなぁと．ま，飾ってあったのが本物かどうかは知らんけど．モナリザも写真撮影禁止の張り紙が伏せられてたしなぁ．ともあれ，やたらと広かったので迷った挙句に全部を回る体力は残ってなかった…　結局３時間弱歩き回っただけ．また機会があれば全部をまわりたいところ．

あとは飛行機に乗って寝て起きたら午後三時には帰国してましたとさ．金曜日は短かったなぁ．

昨日のシフトアルゴリズムの証明を追い終えた．木の重さが単調に増えるという条件を多少緩められるといいのだけど…　「最大の重さを持つ木」に関する性質がアルゴリズムの中心にあるのでこの点の改良は結構大変そう．ポテンシャル突っ込んだら終了とかいう簡単な解決が出来ると楽なんだけど．

Tree Partitioning の話が出る：「木のノードに非負の重みがつけられている．木から k-1 本の片を取り除いて k 個の木に分割する．分割された木の重さを，それに含まれるノードの重みの和とする．このとき，分割された木の重さの最大を最小にする分割を求めよ．」

最後の部分は最小を最大にするとか，最小ないし最大を制限するとかの派生がある．んで，この問題自体は多項式ないし線形オーダーのアルゴリズムがあるらしい．多項式のやつに関してはセパレータを適当にシフトしてくだけでよいらしい．max-min は簡単なシフトのみ， min-max は二種類のシフトを使うとのこと．証明追ってるけどシフトのみでいけるってのは面白いなぁ．

ENS Lyon にある研究室を訪問．とりあえず自分の研究を発表．一応これにて今回の旅の自分の仕事は終了．あとは共同研究のお話を聞く．んで，夕食はレストランでご馳走になる．とりあえず生の馬肉を食らう．刺身でなくハンバーグの焼く前のような状態．面白い味ではあったのだが量が多すぎて後半味がしない．やっぱりこっちの料理は量が多すぎる．消化は問題ないけどしばらく飯イラネ．

日曜日なので Lyon を巡ってみた．

とりあえずフルヴィエール（Fourvière）の丘 ローマ劇場と教会に行き町の全貌を眺める．丘を上るのが一苦労だけど眺めは良い．それだけといえばそれだけだけど．

んで，ものすごく長い階段を下って街中へ移動．途中，インラインスケートでレース中の選手を大量に発見．どうらやこれが混雑の原因らしい．

んで，最後に Part-Dieu のショッピングセンターにたどり着いたのだが…　日曜日なので全部の店が閉まってた．残念．

あとはレストラン街に行って飯を食う．大量に並んだ店で込み具合に差がありすぎることが印象的だった．うちらの入った店は外の席に秋がないほど埋まっていたのに隣の店は客が誰もいないとか．ま，人が多いほうが入りやすいので今日はたまたまそうなったのでしょう．連続して観測できたら面白かったかもしれない．

TGVにてパリを経由しつつ Lyon へ移動．高めのホテルに泊まりつつ夕飯はスーパーへ買出しにでた．いやはやパンがうまい．ついでに安いし．そういやチーズもだいぶ安い．んで，ハムとパンとオレンジジュースとワインとチーズで夕飯とする．なんとなく野菜不足なきがするなぁ．

そういや，フランスのドアはキーを左に回してロックをはずし，そこからさらに左にキーをひねってあける（ノブを回すのでなく）．んで，なぜか知らんけど３軒のホテル全てでドアを開けるのに悪戦苦闘．ロックは外れるが最後のひねりでドアを開けるのに少々手間取る．最後に引っ込むべきストッパーがドア枠の穴に引っかかって動かないのが原因らしい．なのでドアをちょっと引いてみたりすれば開けられるのだが…　これを学習するまでに結構な時間をドア前の不審者としてすごした気がする．またフランスに来るときには気をつけよう．

発表終わった．ふたつほど質問がうまく聞き取れなかった…　というか，想像範囲外からの質問は英語がうまく聞き取れん．話し手が親切だと聞き取りやすい英語を話してくれるので楽なのだが．なにはともあれ仕事も半分終了．明日はLyonへ．