-
masashinakata
- 2321
- 0
- 0
- 0
-
- いいね！0
chokudai(高橋 直大)🍆@AtCoder社長
@chokudai
@__DaLong むずいのだとこのへん？http://t.co/hNvxJimzkY
2013-11-05 23:23:27
大堀龍一 (Ryuichi OHORI)
@__DaLong
@chokudai そういえば ARC016C の問題には「手に入れることのできないアイドルは存在しない」を書いておいた方がよいと思います。
2013-11-05 23:30:20
ＳＫＹ/sky58🍊
@skyaozora
bitDPは、自分は最初に知ったのはSRM430Medで、指数の底が2~4で可変だったからいちいちmod取らなきゃいけなくて重いイメージだったけど、底が2固定ならbit演算を使えて楽に書ける上に爆速だなと感じた。どこまでbitDPと呼ぶかは人次第かな
2013-11-05 23:34:15
大堀龍一 (Ryuichi OHORI)
@__DaLong
ARC016C の解説っぽいものを書いてみました > http://t.co/l9khwY6kLp
2013-11-06 00:06:05
大堀龍一 (Ryuichi OHORI)
@__DaLong
nested function を memoize すると、意図と異なる挙動になった。親の呼び出しごとに独立した memoize を期待していた。> http://t.co/JyP7j5RPlV issue 6662, 8743 あたりと関係していそうだがわからない。#DLang
2013-11-06 11:32:22
大堀龍一 (Ryuichi OHORI)
@__DaLong
もちろん親の呼び出しパラメータを引数に含めれば解決する。しかし美しくないしパラメータが大きいときはコストが大きくなりそう? それともパラメータは向こうでハッシュしてくれるから問題ない?
2013-11-06 11:44:30
Codelogy
@codelogy
@__DaLong std.funcional.memoizeは、関数内のstaticな変数にメモを持つという単純な実装なので、親の呼び出しごとにメモを独立させるのは難しそうです https://t.co/90uzVj5W1y
2013-11-06 13:33:24
大堀龍一 (Ryuichi OHORI)
@__DaLong
@codelogy たぶん http://t.co/0oJVRAQkSP みたいに mixin template 使えばできるんですかね。ちょっとやってみますね。ところで「親の呼び出し」って悪いことした子供みたいですよね。
2013-11-06 17:57:58
大堀龍一 (Ryuichi OHORI)
@__DaLong
関数内再帰関数を適切に memo するためには struct を作ってそのメソッドを使うみたいな感じでいくべきなのかな
2013-11-06 19:22:29
大堀龍一 (Ryuichi OHORI)
@__DaLong
これを簡単に書けるような memoize を作り出さなくてはならない。> http://t.co/lkAJ0I0FjD
2013-11-06 19:37:10
大堀龍一 (Ryuichi OHORI)
@__DaLong
@codelogy 少し試そうとしたところ、再帰関数を (f 内で memoize!f を呼ぶことによって) memoize できるようにするには「親の呼び出しによらない」必要がある気がしてます。
2013-11-06 20:01:24
大堀龍一 (Ryuichi OHORI)
@__DaLong
@__DaLong @codelogy そして単純な再帰関数なら再帰しない条件を判定せざるを得ないので、書くのと同時に memoize を自分でやっても実はあまり手間が増えないようです。
2013-11-06 20:03:28