Project Euler 1252016年04月28日 00時24分42秒

https://projecteuler.net/problem=125
画像処理で使うインテグラルヒストグラムアルゴリズムを使うと、非常に高速に解ける。0.04秒。
但し出力に2個重複があるので注意。

Project Euler 662016年04月26日 08時46分10秒

x^2 - Dy^2 = 1, (x,y,Dは整数)を解くもの。
https://projecteuler.net/problem=66
Diophantine方程式の一種Pell方程式というものらしい。
naiveな方法でやっても全然計算が終わらず、解法を理解するのをさぼってずっとほったらかしていたのだが、最近腰をあげてやってみた。ただ、解けるまでに3回はまった。

1) √D≒x/y なので√Dを連分数近似するのはよいが、安直な、分子が1でなく、循環もしないd+e/(2d+e/(2d+...という連分数展開(d=floor(√D), e=D-d^2)では、解が得られない場合がある。ただこの場合も、x/yはちゃんと√Dに収束はするのだが。

2) 一般的な、分子が1で循環する連分数に展開すると解が求まる。ただ、√Dを含む分数を有理化するところで約分を随時入れないと分子分母が発散する(後述の多倍長整数を使えば大丈夫ではあるが)。

3) 64bit整数で解けるものと思い込んでいたのだが、全然違った。64bit整数でも解けたように見えてしまう(x^2-Dy^2=1になる)のでたちが悪い。
http://tieba.baidu.com/p/2972456090 (中国語読めないけど)
にあるのは、私と同じく64bitでやった、誤った結果である。

というわけで、GMPによる多倍長演算を使ってようやく正解にたどり着きました。やっとレベル5。とほほ。

Project Euler 3452015年09月21日 06時52分19秒

4か月くらいやってなかったが最近再開して10個ほど解いたが、まだ109問。先は長い。。。
https://projecteuler.net/problem=345
方針: 左の列(f=0)から右の列へ処理していく。
縦方向jをbit位置と考え、1ビット立っている数x(=1<<j)をmatsum[x][j]=mat[j][0]と初期化。
次いで、2ビット立っている数x(ここでは0..32767までなめて値が入っているところをピックアップ)での暫定最大値を、matsum[x][1]に入れていく。
既に値が入っていたら、そこでの和と比較して大きければ書き換える。
こうして2ビット、3ビット、・・・が立っている場合の最大値が逐次求まっていく。
最後にmasum[32767][14]に、15ビット立っている場合の最大値が入る。これが答え。
どの行列要素の組み合わせの結果なのかはわからないが答えは出る。
計算量はO(2^N * N)。Cで0.11秒。
コンパイルエラーは一回だけ(セミコロン忘れ)、一発正解。

メールサーバ2015年01月10日 09時29分41秒

正月4日頃から、自宅サーバ宛のメールが届かなくなった。
返送されるエラーメールには
(reason: 554 5.7.1 Service unavailable; Client host [xxlxx.co.jp] blocked using rhsbl.ahbl.org; List shut down. See: http://www.ahbl.org/content/last-notice-wildcarding-services-jan-1st)
と書いてあったがしばらく放置してしまっていた。結局は自宅のSMTPサーバの問題だったようで、postfixの設定ファイル
/etc/postfix/main.cf 内の
smtpd_client_restrictionsのオプションから
reject_rhsbl_client rhsbl.ahbl.org
を除いてservice postfix restart したところ、無事メールが入るようになった。設定をいじったのは3年ぶりで、サーバーがpostfixであることも忘れていた。。。。

フォント埋め込みPDF作成ではまったの巻2014年06月10日 18時24分02秒

ICIPの原稿提出期限ぎりぎりになってようやく原稿仕上げのやる気が出てきた。ただ、EDASのカメラレディPDFのアップロード時チェックは厳しく、フォントが埋め込まれていないと警告を発するため、かなり苦労した。
MS-Wordで原稿を書いているのだが、
・ネットのどこかで推奨されていたように、プリンタドライバとして"Adobe PDF"を選択して、品質を「プレス印刷」とすると、フォントは埋め込まれるが図で使っているベクトルグラフィックスがビットマップ化されてしまい、大変汚い。
・Primo PDFも同様で、ベクトルグラフィクスが非常に汚くなる。
・Word2013に最初からついてきたPDF/XPSアドインを使って、「名前を付けて保存」でPDFを選択する方法があり、保存時オプションで「ISO 19005-1に準拠」とすると、フォントは埋め込まれるが、ベクトルグラフィクスが妙に崩れる。そこでこのチェックを外してPDFを生成すると、ベクトルグラフィクスは文句なく綺麗になるが、フォントが一部埋め込まれない。
・仕方なく、この方法で生成されたPDFをAdobe Acrobatで開き、ツールの「文書テキストを編集」を選択し、PDF内の文字列を選択すると、その選択されたフォントは(ファイル保存時に)埋め込んでくれるようになる。問題は、すべてのフォント(Times New Roman, Italic, Bold, BoldItalicなど)を選択しなければならないこと(選択自体は、一フォントに一度文書内のどこかでするだけでよい)。
ただどう見てもArial Boldが見つからず、はまった。
これはなんと、箇条書きのインデント部分や、章番号の数字と文字列の間(!)などに存在することがわかった。空白なので全くわからなかった。
何とか目的は達成できたものの、Acrobatがなかったらどうしようもなかったヨ。。。

後日記: Symbolフォントの空白があると、上記でもうまくいかず、どうしてもSymbolだけが埋め込まれない(Σなどはよい)。Wordの「高度な検索」機能でワイルドカード検索とフォント指定(Symbolを指定)で見つけてTimes New Romanに変更した。