SuperCON2002

スーパーコンピュータコンテストの予選問題の考察。の前に、去年のプログラムは見事に間違っていた。ごめんなさい。

ということで今回はリベンジなのである。リベンジという言葉も廃れてしまった感はあるが。問題についてはここを参照していただきたい。みていただければ分かると思うが、問題としては非常に簡単である。ということでいきなりプログラム。

f(n,m)=f(n-1,m+1)+f(n-2,m+2)/2というふうに再帰的に定義されている為、素直に再起呼び出しを行っている。しかし、nの数が増えると計算数が(まさに)鼠算式に増えていくのでとてもじゃないが実用的ではない。PentiumIII700MHzでは、f(35,35)までは数秒で計算できるが、f(70,70)では数分経っても終らなかった。

ここで最初に立ち戻って、この計算の性質について考えてみる。例として、f(35,35)を用いることにしよう(nとかmとか記号で考えるのが苦手なのだ)。上記の式にあてはめると以下のようになる。

f(35,35)=f(34,36)+f(33,37)/2={f(33,37)+f(32,38)}+{f(32,38)+f(31,38)/2}/2=.......

と人間にとっては無限とも思えるほど続くのだが、最近のパソコンだとこれが数秒で終ってしまうのだ。すごいなぁ。とそういう話ではない。まず各々の関数の引数に注目していただきたい。すべて35+35=70になっている。式の定義から言えばあたりまえだが。これを最後まで展開するとどうなるかというと、f(0,70)もしくはf(1,69)にそれぞれ係数がかかったものが沢山(そりゃもう嫌になるほど沢山)並んでいるはずである。ここまできてようやくfを数字に変換することができるのだが、なんとまぁf(0,70)=f(1,69)=70となり、f(0,70)だろうがf(1,69)だろうが関係ないことが分かる。これを一般的な表記で表すとこうなる。f(n,m)=x(n+m)(但しxは適当な係数)。ここまでくれば何とかなりそうだ。

次に、任意のn,mについて考える。以下f(n,m)をFn、f(0,m+n)をF0と表すことにする。このとき、F0,F1について考えると、

F0=f(0,m+n)=m+n

F1=f(1,m+n-1)=m+n

となり、先ほどの考察とも一致している。どんどん行こう。

F2=f(2,m+n-2)=f(1,m+n-1)+f(0,m+n)/2=(m+n)+(m+n)/2=3(m+n)/2

F3=f(3,m+n-3)=f(2,m+n-2)+f(1,m+n-1)/2=3(m+n)/2+(m+n)/2=2(n+m)

これがFnまで続くわけだが、これくらい書けばもういいだろう。ようはfor文書けばどうにかなるのである(投げ遣り)。ということでプログラム。ポイントとしては2個前の答えが必要となるので、buf[2]でバッファリングしているところ。f(35,35)について先ほどのプログラムと答え合わせしたので間違ってはいないと思うのだけど。というかこんな簡単なプログラムでいいのか？

俺メモ

既にできているものを変更することによるコストは高いというのは認めるけど、変更せずに追加することによっていびつになった構造をいつまで経っても引きずりつづけることによるコストの方が高いと思うけど、どうよ？

商品券ゲット

理由はわからないけど(ぉぃ)、会社から商品券を三万円分貰う。こういうあぶく銭はすぐ使うに限るのだけど、商品券なのでつかえる場所が限定されている。帰りに寄れるのは有隣堂ぐらい。さすがに三万円分も本は買えないしなぁ。

東急ハンズでお買い物

商品券は東急ハンズで全部使い切ることに決定。当然ながらお釣りがもらえないので、一回で三万円ぴったりを目指す予定。フロア移動が面倒な気もするけどまあいいや。

以下一応ほしいものリスト。

• さいふ

↓ほしいもの補完リスト

CDを整理する

今の場所に引っ越した時にAudioCDをダンボールに入れたまま押入れに入れていたのだけど、そろそろなんとかしようということで、アマゾンさんで160枚収納できるバッグを2つ買ってそこに全部放り込むことにした。ジャケットとケースは全て破棄。ブックレットは少し迷ったけど、これも場所をとるので破棄することに。最近はCDをプレイヤーで聴く機会もほとんど無く、メディア自体破棄してもなんの問題もないような気がしたけど、メディアだけなら場所を取らないだろうということで残しておくことにした。

メディアをバッグに移すのと同時に、昔MP3、128kbpsでリッピングしていたものはAACの256kbpsでリッピングし直すことに。これも前々からやろうとは思っていたんだけど、その面倒さに躊躇していた。

まずはCDケースを分解し、プラと紙を分別。CDをリッピングの待ち行列にスタックし、CDのリッピングを行う。iTunesで同じCDと判定されると、再生回数やレーティングを引き継いで置き換えてくれる。たまにアルバム名や曲名が変わっていたりして*1、そういう場合には手動で以前のデータを削除する必要がある。

CDの読み取り速度が昔よりも速くなっているとはいえ、それなりに時間がかかるので、ゴミの分別作業はほぼほぼ済んだけど、リッピングの待ち行列はだいぶ賑わっている状態で昨日の作業は終了。これが終わったら、PS、DCのゲーム、ケースは捨てても構わないDVD-Videoもケースに収納する予定。