No Such Blog or Diary

Ethereal の続き．http://www.wireshark.org/ より入手可能．一年半くらい前に名前が変わったそうだけど今まで気づいてなかったのでメモ．アイコンが派手になった以外見た目も何も変わらない．

図解アリエナイ理科ノ工作 とかいうものを思わず買って読んでみた．マジで作るには結構根性要りそうなものばかり．そして使うには覚悟と根性が要るものばかり．オートクレーブあたりは面白そうだけど暴発が非常に恐い．どれぐらい吹っ飛ぶんだろう？

「エクセルでひぐらしのなく頃に解OP」とかいう動画を見てしまったのでおもむろにVBAを勉強したい気分．ところで VBA からアクセスできるオブジェクトの情報ってどこにあるんだろう？　MSDNのライブラリ覗きにいけばあるのだろうか？

ちゃんと資料を追わなかったので分からんのだけど，元の式の対称性を使って変数を減らしたときに正定値条件は必要十分でカバーできるけど目的関数の最適性って保存されるのだろうか？　変数を減らすプロセスに目的関数の係数行列ってでてきてたっけ？　気になってきたのでそのうち確認しよう．

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

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);
    }

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

別に痛くないけど気になる部分があるのでいってみた．とりあえず気になった部分は虫歯＋前の詰め物が少しとがっていたと判明．そして余計なものもいくつか見つかった．一番面倒そうなのが左上親知らずの外側の生え際の虫歯．なんとなく前からなんか違和感あると思っていたら虫歯だったと．とりあえずどうなるかわからんけど全部片付けるのに一ヶ月～一ヵ月半くらいらしい．