https://twitter.com/kinaba のログ (twilog の方が便利です。)
| Xを有限集合とする。S1,...,Sn⊆X と S⊆X^n に対して S1×...×Sn ∩ S ≠ Φ かどうかの判定ってどんくらいの計算量でできるんだっけ。SiやSは適当に賢いデータ構造で表現されてるものとする | |
| @uwitenpen 各S_iがハッシュセットになってるとして O(|S|) = O(|X|^n)、くらい使ってもいいです | |
| http://uwi.blog110.fc2.com/blog-entry-48.html かんがえる | |
| Pi mod 20 で考えられそうだからPARTITIONの擬多項式時間アルゴリズムみたいなのでなんかないかな。寝起きで頭回ってないのであれだけど | |
| @uwitenpen ナップサックとかビンパッキングになりそうでならなそうでなりそうですね。。。 | |
| 少なくとも NP-hard ではあるような気がする | |
| Piは全部%20しておく。mod20ではなく普通の和で19になる組をgreedyに一つのカゴに入れる→18になる組をgreedyに→17→16→ で最適解になったりしないか | |
| @uwitenpen すべてについて洗うんじゃなくて、19になる組を見つけたらそれ確定しちゃって大丈夫じゃないでしょうか、という | |
| http://twitter.com/uwitenpen/statuses/914503662 そうか、そりゃそうだ | |
| @keno42 1, 2 (17,18,19,19) より (18,1) (17,2) (19,19) の方がベターだと思うけど、これって出せます？ | |
| @keno42 消費税額が \0 \0 \3 → \0 \0 \1 になると思う | |
| あんどれーが完全にイテレータをやめてRangeベースでstd.algorithmを設計し直すと言い出した。 http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html 素晴らしい | |
| ただDの配列スライスをRangeと見なそうとすると、RandomAccessとかBidirectionalでスライスを「広げる」操作がまともに書けなくて往生した覚えがあるんだけどどうすんのかな。 | |
| うわーleftUnionとかキモいなー | |
| @nagise (遅レス)C++/Dのイテレータって「要素を列挙するもの」ってよりはむしろ「ポインタ（要素を指すもの）」で、例えばjava.util.collections.binarySearchのような関数はintではなくイテレータを返す、というような抽象化に使われるんですが | |
| @nagise その手の処理って引数としてはイテレータのペア（ここからここまでを処理）を取るものがとても多くて、それだったらいっそ「こっからここまで」を表すオブジェクト（= Range）を基本としてできるだけ単体のイテレータを廃した方が処理のパイプラインがうまく繋がるだろう | |
| @nagise みたいな議論があったりしてそういう流れです、たぶん＞Dのstd.rangeの云々 |