普通にメモ化するだけでいいのかなー、落とし穴でもあるんじゃなかろうか？なんて思ってたけどそんなものはなかった。
class InfiniteSequence {
map<long long, long long> cache;
long long acalc (long long n, int p, int q) {
if (n == 0) return 1;
if (cache.find(n) == cache.end()) {
cache[n] = acalc(n/p, p, q) + acalc(n/q, p, q);
}
return cache[n];
}
public:
long long calc(long long n, int p, int q) {
cache.clear();
return acalc(n,p,q);
}
};
最初手元のテストが通らなくて悩んでいたらキャッシュをクリアーしてなかった。
cache.clear()
覚えた。
06082008 life
あ、hyukiさんからスターをもらった。ありがとうございます。読むのが楽しみとか書いてたけど、週末に一気に読み切りました。
僕の場合はMAWPを読んだ際に悩んだという経験もあって、7章のmodの話にやたらと感動した。あと最後のオチも。
中学、高校当時の私に『数学ガール』を読ませてあげたいという読者の声がありましたが、それはかなわないので、数学ガールの二冊は娘が大きくなったら贈る本にしようかと。
05082008 chemoinformatics
最近、家に帰ると娘がyoutubeをせがむので、コードが書けない。あと部屋があちい。そんなわけで、寝転がって本を読んでいる事が多い。
今日も数年の間寝かせてあった、グラフィカルモデリングなどを読んで勉強中
一通り読んだが、分からない事だらけ。数学ガールシリーズでパターン認識関連のやつをカバーしてくれれば楽しく読めるのになどと考えるのは暑いゆえの妄想か。
グラフィカルモデリングって遺伝子ネットワークみたいなのだけじゃなくて、活性構造相関みたいな研究でも役に立つとおもうんだけどなぁ。なんか適当なサンプルに適用して眺めてみたいところ。
あと、そろそろビショップ本読み始めないと。
05082008 music drum'n'bass
いまさら感たっぷりだがJenna G
急に欲しくなった
沼津のタップルームでビール三昧。行きはタクシー、帰りは風にあたりながらぶらりと歩いて駅まで。
沼津港が見える。そして昼時のアンニュイな空間を楽しみつつ。
ビールは季節ものを中心に、飲む、飲む、飲む。
柑橘のフレーバーを入れてるのが好きだね。
最後に黒い系で〆。夏の間に後一回くらいいく。
Problem Statement for BirthdayReminders
素直に書いたら、タイムアウトで撃沈された。システムテストの３個目でも落とされる。
数学ガール
数学ガール/フェルマーの最終定理
グラフィカルモデリング (統計ライブラリー)
For Lost Friendsclass BirthdayReminders {
public:
vector <string> remind(vector <string> friendNames, vector <int> birthDates, int currentDate, vector <string> occasions, vector <int> days, int k) {
vector <string> rem;
vector <int> times;
stringstream ss;
int fs = friendNames.size();
int os = occasions.size();
for(int l=0;l<fs*os;l++) times.push_back(0);
for(int i=1;i<1000001;++i){
for(int j=0;j<occasions.size();++j){
for(int m=0;m<friendNames.size();++m){
int n = m*os+j;
if(i-birthDates[m]>0 && (i-birthDates[m])%days[j] == 0) {
times[n]++;
if(i >= currentDate) {
ss << i << ". " << friendNames[m] << " " << occasions[j] << " (" << times[n] << ")";
rem.push_back(ss.str());
if(rem.size() == k) return rem;
ss.str("");
ss.clear();
}
}
}
}
}
return rem;
}
};
最初にテーブルを作っておいて最小の日を探しつつ更新していく。
教訓:安直にforをまわさない。
01082008 chemoinformatics
Andrew Dalke's most recent diary entriesをplanet chemoinfromaticsに追加した。
bioinformaticsもchemoinformaticsも一緒にやっているので、特に自分の仕事をインフォマティクスと読んでいたのだけど、最近はインフォマティクスがやりたいがために、インフラ整備ばっかりしているので、そろそろ仕事なんですか？と問われたら
インフラマティクスっす
と答えようかなと思っている。あと、IUPAC名をカバーする正規表現とか、テキストからIUPAC名を抽出するモジュールを探してるが見つかりません。誰か知ってたら教えください、プリーズ。
と思ったら、Oscar3を調べれば良い感じだった。
31072008 chemoinformatics cpp
ここ何日か早起きしてはopenbabelのソースコード読んでた。
31072008 life
30072008 sake
数学ガール フェルマーの最終定理 (数学ガールシリーズ 2)
