脳log[20110925] Problem 205, Problem 300

最終更新: 2013-05-18T14:03+0900

♪ [ProjectEuler] Problem 205, Problem 300

 Problem 205

行き詰まっている。新しくなった Progress画面でテキトーに問題をクリックしたら勝率の高い(正答者数の多い)問題だったでござる。

# さいころふりふり
total4 = [0,1,1,1,1] + [0]*32 # サイコロを 1回振って出目(o)の合計が i(=1,2,3,4,...,36)である場合の数を total4[i]。0番目は単なるプレースホルダ。
8.times{ # 2-9回目
	(total4.size-1).downto(1){|i|
		total4[i] = (1..([4,i].min)).inject(0){|sum,o| sum + total4[i-o] }
	}
}
total6 = [0,1,1,1,1,1,1] + [0]*30
5.times{
	(total6.size-1).downto(1){|i|
		total6[i] = (1..([6,i].min)).inject(0){|sum,o| sum + total6[i-o] }
	}
}
# 集計
win4 = 0
sum4, sum6 = 0, 0
1.upto(36){|total|
	win4 += total4[total] * sum6
	sum4, sum6 = sum4 + total4[total], sum6 + total6[total]
}
p 1.0*win4/sum6/sum4

 Problem 300

5時間以上かかった……(実行に)。

Process.times: #<struct Struct::Tms utime=20471.855, stime=8.268, cutime=0.0, cstime=0.0>

どうすれば……。

1. すべての折りたたみパターンを列挙。(点対称は除いたつもり。鏡像はそのまま。593611通り)
2. パターンをコンタクトポイント(インデックスのペア)列に変換|sort|uniq。(12495通り)
3. すべてのタンパク(2^{15}通り)をさっき求めたコンタクトポイントの列(12495通り)に当てはめて(約408701758通り)、最良の H-Hコンタクトポイント数の合計を得る。

何の工夫もないナイーブなやり方だから手を付ける余地はあり余ってるんだろうけど、どういうやり方をしたらいいのか途方に暮れる。

スレッドを見たら先頭から 3つ 4つ立て続けに「brute force」の文字。それでも 20秒やら 3分で終わるらしい。バブルソートと同じくバカの代名詞(※ごく少数を対象にするなら妥当な選択肢)みたいに思ってるけど、その中でもさらに利口なのとバカなのとがあるのね。最低限のたしなみとして作業領域の大量コピーはしてないんだけど。

最初は 6時間かかったけど 12分に縮まったという人もいた。そういうことならもう少し手を入れてみよう。

 @2011-09-27

 1.折りたたみパターンの列挙

• 団子(直線や突起を含む)か、1つ以上の連結したドーナツ状になるしかない。
• 団子がコンタクトポイント数を稼ぐのに一番有利。

というあたりでひとつ(どうにかならないか？)。

おっと、ドーナツになるとコンタクトポイントにボーナス(+1)が付くのだった。

 2. 12495通りのコンタクトポイント列

• 頭としっぽの区別をなくしたら、半分とはいかないまでも減る。不可
• 他ののサブセットになってるのがあったら除外できる。12495→3409通り

 3. すべてのタンパク(2^{15}通り)をコンタクトポイントの列(12495通り)に当てはめる。(408701758通り)

手立てなし。

ステップ2でサブセットを除去したら 2分。ただし C++で。

最適化オプションを目に付いただけくっつけただけで 15秒になるんだもんな。>PE300.cpp C++で 3秒だという人がいるけど、これ以上の悪足掻きをするかは微妙。

しかしまあ、投稿されたコードを眺めると、アホな人間は自分から問題を難しくしてそれに四苦八苦してるような印象を受ける。自虐してるの？ 要するに、上にアップロードしたコードはもっとシンプルに書けるはずだ、と。HとPの長さ15の配列としてのタンパクを 0から 2^{15}未満の整数のビットパターンで表したり……。手立てなしとしたステップ3こそが実行時間の大半を占めてるので高速化のメインステージなのだ。再帰してる場合でも vectorをループで回してる場合でもないのだ。こういう筋トレっぽいトレーニングをしてくれる問題は貴重。これまで考えたことがないから。

 2011-10-17

優れた人々は無意識にやっているので、あまりこういうことは教えてもらえない(というか当然やっていますよねJK、などと思われていたりする)ので本書のように、あらためて書いてくれている本は大変貴重だと思った次第。すごい人達が「ナイーブな手法でいいんじゃね」という時は「本書で書いてあるようなことを当然踏まえた上で適切にナイーブな手法を組み合わせて使っている」という意味だったりするので十分注意したい。

ナイーブという単語に反応した。上の方で「何の工夫もないナイーブなやり方だから手を付ける余地はあり余ってるんだろうけど」と書いたときのナイーブはもちろん……。練習問題、やります。

 @2012-03-03

C++で３秒だという人のコードを読んでいた。自分でコードできるほど十分には理解してないけど見つけたアイディアだけ書いてみる。

for (auto a = s.begin(); a != s.end(); ++a) {
    bitset<64> _t = t & *a;
    m = max(m, (int)_t.count());
}

タンパク質(t)とコンタクトポイント列(a)が long long intで、sはコンタクトポイント列の集合。コンタクトポイント列とタンパク質の照合が bitwise andで済んでしまっている。

俺が vector<pair<char,char> >としたコンタクトポイント列がどのように long long intにパッキングされているのか。

 ペアの大小。

pair<char,char>は、タンパク質の先頭からのインデックス(0..14)を使って、(4,9)も (9,4)も表現できるが両者は同じなので (9,4)だけ表せればいい。インデックス iの(i+1番目の)アミノ酸とペアになりうるインデックスは全部で i種類。これなら必要ビット数は \sum_{i=0}^{14}i = 105。

 ペアの偶奇。

チェス盤の黒白を考えるとわかりやすいけど、黒いマスの隣には白いマスしかない。インデックスが奇数のアミノ酸(H,P)の隣にはインデックスが偶数のアミノ酸しかこない。これで情報を失わずに表現形を半分に減らせる。\sum_{i=0}^{14}\lceil\frac{i}{2}\rceil = \sum_{i=0}^{14}\lfloor\frac{i+1}{2}\rfloor = 56ビット(→床関数)。long long intに収まるサイズになった。

と、ここまで読んだ*んだけど、15ビット以上の整数型で表されるタンパク質を照合用の56ビット表現に変換するところの解読がまだ。プログラム全体としては無駄がなくて、そういう意味ではわかりやすいんだけど。(L=15; int hを long long int tに変換)

long long int t = 0;
for (int i = 0; i < L; ++i) {
    t <<= ((i + 1) / 2);
    if (h & (1 << i))
        for (int j = (i + 1) % 2; j < i; j += 2)
            if (h & (1 << j))
                t |= 1 << (j / 2);
}