ARC016

0
前へ 1 ・・ 14 15 次へ
hogeover30 @hogeover30

んで、(1)+(2.1)+(2.2)=6015.789 ってこと?

2013-11-05 15:49:33
hogeover30 @hogeover30

@sune232002 なんとなくわかったような気がします。ありがとうございます。

2013-11-05 15:50:05
hirokazu @hirokazu1020

期待値弱者なのでC解けない

2013-11-05 15:50:10
agw @masashinakata

あら、クソ長い回答書いてたらもう質問閉じられてた orz > http://t.co/qJZJ7RT3tc

2013-11-05 15:57:00
agw @masashinakata

@hogeover30 Advent Calendarで作図しまくります! ARC006 Cも超良問だったので盛り込みたいです

2013-11-05 16:03:26
laycrs @laycrs

@chokudai ほえー.ああ,そうか,行き止まりのノードは使い回せば良いのね・・・.25^74は大変そうですね

2013-11-05 16:05:53
agw @masashinakata

@hogeover30 期待しておいてくれたまえ(合ってる?)

2013-11-05 16:08:08
agw @masashinakata

@hogeover30 ごめんなさい。大きく出てしまいました。恐らくいつもの作図と変わらないです ((((;゚Д゚))))ガクガクブルブル

2013-11-05 16:08:57
大堀龍一 (Ryuichi OHORI) @__DaLong

@teporz 各くじに対し、それを最初に引いたときの現在のコレクションからコンプリートまでの (最適戦略下) コスト期待値を変数とし、コレクションが現在より多い場合の期待値がわかっているとした一次方程式を立てます。条件つき期待値のあたりは注意していないとはまりそうです。

2013-11-05 22:29:44
大堀龍一 (Ryuichi OHORI) @__DaLong

C問題は解けたのに解説を読んでもわからない…… RT @chokudai: AtCoder Regular Contest 016、解説アップロードしました! http://t.co/JTNgwXmjhq

2013-11-05 22:38:22
@teporzは衰退しました @tepor2

@__DaLong おおおありがとうございます!参考に勉強します・・・!

2013-11-05 22:46:59
大堀龍一 (Ryuichi OHORI) @__DaLong

@teporz 公式の解説を読んでもわからなかったので気が向いたら書くかもしれません (忘れそう)

2013-11-05 22:50:57
@teporzは衰退しました @tepor2

@__DaLong 某知恵袋で質問したらわかりやすい答えを頂きました(小声

2013-11-05 22:51:37
大堀龍一 (Ryuichi OHORI) @__DaLong

@teporz それはよかったですね (URL ください

2013-11-05 22:52:55
大堀龍一 (Ryuichi OHORI) @__DaLong

ARC016C の解法である bitDP の概念は知っていたが名前は最近まで知らなかった。固定された可算集合の有限部分集合を自然数にエンコードすることと DP とを組み合わせただけなら、仰々しい名前なんてつけない方がいいと思うけど。

2013-11-05 22:56:52
大堀龍一 (Ryuichi OHORI) @__DaLong

@teporz うーん、なぜ両回答ともに「特定の1つを当てるまでにかかる回数の期待値」を既知としているのでしょう。そのままコードにすると、余分な場合分けを作り出してしまいます。素直に一般の場合で一次方程式を書きたいですね。

2013-11-05 23:03:02
chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

@__DaLong 今回は使わないけど、for(int j=i; j>0; j= ((j-1)&i))みたいな感じで参照するパターンとかあるから、なんか名前ついてた方が色々テクニックとして覚えやすい印象。まぁそれ言うなら桁DPとかも桁ごとにやってるだけで本質的に同じやんとか色々

2013-11-05 23:03:49
大堀龍一 (Ryuichi OHORI) @__DaLong

@chokudai 「どうやって解くの?」「bitDP です」「ふえぇ、そんなの知らないよう……」より「どうやって解くの?」「あなたも知ってる DP ですよ」「集合を添字にしなきゃいけないよ?」「自然数で集合を表せます」の方が学習者にとって有益だと思うのです。

2013-11-05 23:12:48
chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

@nijinoryu for(j = 1; j < N+1; j++){ってあるんですが、jがN==100まで行くのに対し、string x[9][100];で、0-99までしかないので、長さ100の入力が与えられた時に配列外参照してそうですねー・・・。

2013-11-05 23:12:50
大堀龍一 (Ryuichi OHORI) @__DaLong

@chokudai 桁DPというのは言葉も初耳なのですが、例題パッと出ますか?

2013-11-05 23:19:46
前へ 1 ・・ 14 15 次へ